题目链接：http://www.spoj.com/problems/DQUERY/en/
题目大意：
给一段序列，每次询问l ， r之间有多少个不同的数。
解题思路：
这道题以前做的时候用的是离线+线段树或者树状数组，最近学了主席树，就可以用主席树来在线解题了。而且貌似感觉自己用莫队解过这道题23333，反正解法很多，这里主要说主席树的解法，主席树的解法主要是记录每个数最右边的位置对答案的贡献。拿样例举例子，画个图应该很容易明白。
这个图呢就是对应样例画出来的对应1 1 2 1 3 的图，其实这里面每个1就是代表我这个位置对答案有1的贡献，而且只记录每个数字最后出现的位置，那么这样之后我们查询l r区间的时候 就直接在 root[r] l,n查询即可，
而且我感觉自己代码写的挺好看的2333
Ac代码：
#include<bits/stdc++.h> #define lson rt<<1 #define rson rt<<1|1 using namespace std; typedef long long ll; const int N=1e5+5; const int maxn=1e6+10; const int INF=1e9+7; int dx[4]={0,1,0,-1}; int dy[4]={1,0,-1,0}; int n,m,cnt; int a[N],root[N],last[maxn]; //last数组记录位置 因为数不大 不需要离散化 struct node { int l,r,sum; }t[N*40]; void update(int l,int r,int &x,int y,int val,int pos) //主席树更新操作 val对应+1 -1 { t[++cnt]=t[y],t[cnt].sum+=val,x=cnt; if(l==r) return ; int m=(l+r)>>1; if(pos<=m) update(l,m,t[x].l,t[y].l,val,pos); if(pos>m) update(m+1,r,t[x].r,t[y].r,val,pos); } int query(int l,int r,int x, int L,int R) //主席树简单的查询操作 { int ans=0; if(L<=l&&r<=R) return t[x].sum; int m=(l+r)>>1; if(L<=m) ans+=(query(l,m,t[x].l,L,R)); if(R>m) ans+=(query(m+1,r,t[x].r,L,R)); return ans; } int main() { while(scanf("%d",&n)!=EOF) { cnt=0; memset(root,0,sizeof root); memset(last,-1,sizeof last); for(int i=1;i<=n;i++) scanf("%d",&a[i]); for(int i=1;i<=n;i++) { if(last[a[i]]==-1) update(1,n,root[i],root[i-1],1,i); //如果这个数第一次出现 将它所在位置贡献+1 else { int sk; update(1,n,sk,root[i-1],1,i); //不是第一次出现 将上次出现的位置贡献消去 update(1,n,root[i],sk,-1,last[a[i]]); //当前位置贡献+1 } last[a[i]]=i; } scanf("%d",&m); while(m--) { int l,r; scanf("%d%d",&l,&r); printf("%d\n",query(1,n,root[r],l,n)); } } //system("pause"); }
