I used my RedBlack tree to solve it,
but WA T.T

There is any critical input data for my source?
(assume my RBTree class is right.. I tested it several times...)



int n, m;
int a[100000];
struct query {
	int num;
	int l, r, rank;
};
bool operator < (const query& a, const query& b)
{
	if (a.l == b.l) {
		return (a.r < b.r);
	}
	return (a.l < b.l);
}
query q[50000];
int answer[50000];

int main()
{
	scanf("%d%d", &n, &m);
	for (int i = 0; i < n; i++) {
		scanf("%d", &a[i]);
	}

	for (int i = 0; i < m; i++) {
		scanf("%d%d%d", &q[i].l, &q[i].r, &q[i].rank);
		if (q[i].l > q[i].r) {
			int temp = q[i].l; q[i].l = q[i].r; q[i].r = temp;
		}
		q[i].l--, q[i].r--;
		q[i].num = i;
		//printf("%d %d %d\n", q[i].l, q[i].r, q[i].rank);
	}
	sort(q, q + m);

	RedBlack rb;

	for (int i = q[0].l; i <= q[0].r; i++) {
		rb.insert(a[i]);
	}
	answer[q[0].num] = rb.rank(q[0].rank);

	for (int i = 1; i < m; i++) {
		if (q[i - 1].r >= q[i].r) {
			(* (int *)0) = 0;
		}
		if (q[i - 1].r < q[i].l) {
			for (int j = q[i - 1].l; j <= q[i - 1].r; j++) rb.erase(a[j]);
			for (int j = q[i].l; j <= q[i].r; j++) rb.insert(a[j]);
		}
		else {
			for (int j = q[i - 1].l; j < q[i].l; j++) rb.erase(a[j]);
			for (int j = q[i - 1].r + 1; j <= q[i].r; j++) rb.insert(a[j]);
		}
		answer[q[i].num] = rb.rank(q[i].rank);
	}

	for (int i = 0; i < m; i++) {
		printf("%d\n", answer[i]);
	}

	return 0;
}

• Did you initialize array answer[...]? (1711) C6H6 2006-03-14 22:47:54
  • Re:Did you initialize array answer[...]? (10359) insany 2006-03-15 09:36:41
    • ~~-_-|', Long... 13K.(Inside) (11651) C6H6 2006-03-15 14:20:06
      • Re:~~-_-|', Long... 13K.(Inside) (442) insany 2006-03-15 16:55:46
      • Re:~~-_-|', Long... 13K.(Inside) (442) insany 2006-03-15 17:32:27
      • Finally, I got accepted (537) insany 2006-03-15 17:33:49