[SDOI2009]区间不同数个数 （在线主席树）

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
template <class T>
inline bool scan(T &ret) {
	char c;
	int sgn;
	if(c=getchar(),c==EOF) return 0; //EOF
	while(c!='-'&&(c<'0'||c>'9')) c=getchar();
	sgn=(c=='-')?-1:1;
	ret=(c=='-')?0:(c-'0');
	while(c=getchar(),c>='0'&&c<='9') ret=ret*10+(c-'0');
	ret*=sgn;
	return 1;
}
inline void outt(int x) {
	if(x>9) outt(x/10);
	putchar(x%10+'0');
}
const int N = 1000010, INF = 1e9;
struct SegmentTree {
	int lc, rc; // 左右子节点编号
	int sum;
} tree[N * 30];
int n, m, t, tot,a[N], root[N];
int build(int l, int r) {
	int p = ++tot; // 新建一个节点，编号为p，代表当前区间[l,r]
	tree[p].sum = 0;
	if (l == r) return p;
	int mid = (l + r) >> 1;
	tree[p].lc = build(l, mid);
	tree[p].rc = build(mid + 1, r);
	return p;
}

int insert(int now, int l, int r, int x, int delta) {
	int p = ++tot;
	tree[p] = tree[now]; // 新建一个副本
	if (l == r) {
		tree[p].sum += delta; // 在副本上修改
		return p;
	}
	int mid = (l + r) >> 1;
	if (x <= mid) tree[p].lc = insert(tree[now].lc, l, mid, x, delta);
	else tree[p].rc = insert(tree[now].rc, mid + 1, r, x, delta);
	tree[p].sum = tree[tree[p].lc].sum + tree[tree[p].rc].sum;
	return p;
}

int ask(int p,int q,int l,int r,int L,int R) {
	if(l>=L&&r<=R)return tree[p].sum - tree[q].sum;
	int mid = (l+r)>>1;
	int sum=0;
	if(R<=mid)sum += ask(tree[p].lc,tree[q].lc,l,mid,L,R);
	else if(L>mid)sum += ask(tree[p].rc,tree[q].rc,mid+1,r,L,R);
	else sum+= ask(tree[p].rc,tree[q].rc,mid+1,r,L,R) + ask(tree[p].lc,tree[q].lc,l,mid,L,R);
	//L R
	return sum;
}

int lst[N];
int vis[N];
int b[N];

int main() {
	scanf("%d", &n);
	tot=0;
	memset(root,0,sizeof(root));
	memset(vis,0,sizeof(vis));
	for (int i = 1; i <= n; i++) {
		scan(a[i]);
		lst[i]=vis[a[i]];
		b[i]=lst[i];
		vis[a[i]]=i;
	}
	sort(lst + 1, lst + n + 1); // 离散化
	t = unique(lst + 1, lst + n + 1) - (lst + 1);
	root[0] = build(1, t); // 关于离散化后的值域建树
	for (int i = 1; i <= n; i++) {
		int x = lower_bound(lst + 1, lst + t + 1, b[i]) - lst; // 离散化后的值
		root[i] = insert(root[i - 1], 1, t, x, 1); // 值为x的数增加1个
	}
	scanf("%d", &m);
	for (int i = 1; i <= m; i++) {
		int l,r;
		scan(l);
		scan(r);
		int x = lower_bound(lst + 1, lst + t + 1, l-1) - lst;
		if(lst[x]>l-1)--x;
		if(x==t+1)--x;
		outt(ask(root[r], root[l-1], 1, t, 1,x));
		putchar('\n');
	}
	return 0;
}