SPOJ - DQUERY D-query (主席树)

Given a sequence of n numbers a1, a2, ..., an and a number of d-queries. A d-query is a pair (i, j) (1 ≤ i ≤ j ≤ n). For each d-query (i, j), you have to return the number of distinct elements in the subsequence ai, ai+1, ..., aj.

Input

• Line 1: n (1 ≤ n ≤ 30000).
• Line 2: n numbers a1, a2, ..., an (1 ≤ ai ≤ 106).
• Line 3: q (1 ≤ q ≤ 200000), the number of d-queries.
• In the next q lines, each line contains 2 numbers i, j representing a d-query (1 ≤ i ≤ j ≤ n).

Output

• For each d-query (i, j), print the number of distinct elements in the subsequence ai, ai+1, ..., aj in a single line.

   

Example

Input
5
1 1 2 1 3
3
1 5
2 4
3 5

Output
3
2
3 

       查找给定区间内有多少不同的数。

       以每个数最后出现的坐标为点建立主席树。这样的话对于【L,R】区间内的不同的数的数量就是主席树【R】中大于等于L的点的数量是多少。

#include<bits/stdc++.h>
using namespace std;
const int maxn = 30010;
const int M = maxn * 200;
int n, q, tot;
int a[maxn];
int T[maxn], lson[maxn], rson[maxn], c[M];
int build(int l, int r) {
	int root = tot++;
	c[root] = 0;
	if (l != r) {
		int mid = (l + r) >> 1;
		lson[root] = build(l, mid);
		rson[root] = build(mid + 1, r);
	}
	return root;
}
int update(int root, int pos, int val) {
	int newroot = tot++, tmp = newroot;
	c[newroot] = c[root] + val;
	int l = 1, r = n;
	while (l < r) {
		int mid = (l + r) >> 1;
		if (pos <= mid) {
			lson[newroot] = tot++; rson[newroot] = rson[root];
			newroot = lson[newroot]; root = lson[root];
			r = mid;
		}
		else {
			rson[newroot] = tot++; lson[newroot] = lson[root];
			newroot = rson[newroot]; root = rson[root];
			l = mid + 1;
		}
		c[newroot] = c[root] + val;
	}
	return tmp;
}
int query(int l, int r, int rt, int L) {
	if (l >= L) {
		return c[rt];
	}
	int mid = (l + r) >> 1, sum = 0;
	if (L <= mid) {
		sum += query(l, mid, lson[rt], L);
		sum += c[rson[rt]];
	}
	else sum += query(mid + 1, r, rson[rt], L);
	return sum;
}
int main() {
	while (~scanf("%d", &n)) {
		tot = 0;
		for (int i = 1; i <= n; i++)
			scanf("%d", &a[i]);
		T[0] = build(1, n);
		map<int, int>G;
		for (int i = 1; i <= n; i++) {
			if (G.find(a[i]) == G.end()) {
				T[i] = update(T[i - 1], i, 1);
			}
			else {
				int tmp = update(T[i - 1], G[a[i]], -1);
				T[i] = update(tmp, i, 1);
			}
			G[a[i]] = i;
		}
		scanf("%d", &q);
		while (q--) {
			int l, r;
			scanf("%d%d", &l, &r);
			printf("%d\n", query(1, n, T[r], l));
		}
	}
	return 0;
}