题意：
求区间出现的不同数字的种类数
思路：
方法有很多，莫队分块树状数组
对于主席树：
如果该元素第一次出现，直接将对应线段树的位置+ 1
反之，先将上一次出现的位置− 1，再将该位置+ 1
代码：
const int maxn=3e5+7,mod=1e9+7,inf=0x3f3f3f3f; int a[maxn],n,q; int root[maxn],idx; struct node{ int l,r,cnt; }tr[maxn*40]; void pushup(int u){ tr[u].cnt=tr[tr[u].l].cnt+tr[tr[u].r].cnt; } int build(int l,int r){ int p=++idx; if(l==r){ tr[p].cnt=0; return p; } int mid=(l+r)/2; tr[p].l=build(l,mid); tr[p].r=build(mid+1,r); pushup(p); return p; } int nsert(int k,int l,int r,int u,int val){ int p=++idx; tr[p]=tr[u]; if(l==k&&k==r){ tr[p].cnt+=val;return p; } int mid=(l+r)/2; if(k<=mid) tr[p].l=nsert(k,l,mid,tr[p].l,val); else tr[p].r=nsert(k,mid+1,r,tr[p].r,val); pushup(p); return p; } int query(int l,int r,int u,int pos){ if(l==r) return tr[u].cnt; int mid=(l+r)/2; if(pos<=mid) return tr[tr[u].r].cnt+query(l,mid,tr[u].l,pos); else return query(mid+1,r,tr[u].r,pos); } int main(){ n=read; rep(i,1,n) a[i]=read; root[0]=build(1,n); map<int,int>mp; rep(i,1,n){ if(!mp[a[i]]){ mp[a[i]]=i; root[i]=nsert(i,1,n,root[i-1],1); } else{ int tmp=nsert(mp[a[i]],1,n,root[i-1],-1); root[i]=nsert(i,1,n,tmp,1); } mp[a[i]]=i; } q=read; while(q--){ int l=read,r=read; printf("%d\n",query(1,n,root[r],l)); } } /** * root[i]维护的是数组[1,i]中每个数的最后位置 这样查询 [ l , r ] 内的答案就是查询第 r 个版本的主席树中 [ l , r ] 的 sum * */
