SPOJ D-QUERY

以前主席树学  kungbin 最近看了网上的版本 终于发现和我以前学的线段树差不多的了 希望最近能够加强

#include<bits/stdc++.h>

using namespace std;

const int INF = 0x3f3f3f3f;

const int MOD = 1e9+7;

const int MAXN = 30005;

struct Node{

	int ls,rs, sum;

}tree[MAXN*25];

int tot;

int a[MAXN];

int vis[1000006];

int root[MAXN];

int Build(int l,int r) {

	int rt = tot++;

	tree[rt].sum = 0;

	if(l == r) return rt;

	int m = (l+r) >>1;

	tree[rt].ls = Build(l,m);

	tree[rt].rs = Build(m+1,r);

	return rt;

}

int Update(int pos,int num,int pre,int l,int r) {

	int rt = tot++;

	tree[rt] = tree[pre];

   	tree[rt].sum += num;

	if(l == r) return rt;

	int m = (l+r) >>1;

	if(pos <= m) tree[rt].ls = Update(pos,num,tree[pre].ls,l,m);

	else tree[rt].rs = Update(pos,num,tree[pre].rs,m+1,r);

	return rt;

}

int Query(int rt,int L,int R,int l,int r) {

	if(L <= l && r <= R) {

		return tree[rt].sum;

	}

	int m = (l+r)>>1;

	int ans = 0;

	if(L <= m) ans += Query(tree[rt].ls, L,R,l,m);

	if(R > m) ans += Query(tree[rt].rs, L,R,m+1,r);

	return ans;

}

int main(){

	int n,m;

	while(~scanf("%d",&n)) {

		tot = 0;

		memset(vis,0,sizeof(vis));

		for(int i = 1; i <= n; ++i) {

			scanf("%d",&a[i]);

		}

		root[0] = Build(1,n);

		for(int i = 1; i <= n; ++i) {

			int tt = Update(i,1,root[i-1],1,n);

			if(vis[a[i]]) {

				root[i] = Update(vis[a[i]],-1,tt,1,n);

			}else root[i] = tt;

			vis[a[i]] = i;

		}

		scanf("%d",&m);

		for(int i = 1; i <= m; ++i) {

			int a,b; scanf("%d %d",&a,&b);

			printf("%d\n", Query(root[b],a,b,1,n));

		}

	}

	return 0;

}