给定一列数，查询给定区间内数的种类数。

这题可以分块做：

但是我们不想分块而且垃圾SPOJ可能会卡时间同时又想练主席树，所以选择主席树。

参考：

这种题的主席树建法并不是权值线段树，而是正常线段树。

当我们建树过程中碰到的重复的数的时候，显然让该重复的数接近r是最好的，所以我们把前面的数删掉，放到后面。

查询的时候就是查询rt[0]~rt[r]，并且查询的范围在l~r的数的个数即可。

PS：rt[0]相当于没有，范围的上限r也可以省略。

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           using namespace std;const int N=1e6+5;inline int read(){ int x=0,w=1;char ch=0; while(ch<'0'||ch>'9'){ if(ch=='-')w=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();} return x*w;}struct tree{ int l,r,sum;}tr[N*20];int n,m,rt[N],pool,in[N];inline void insert(int y,int &x,int l,int r,int p,int v){ tr[x=++pool]=tr[y]; tr[x].sum+=v; if(l==r)return; int mid=(l+r)>>1; if(p<=mid)insert(tr[y].l,tr[x].l,l,mid,p,v); else insert(tr[y].r,tr[x].r,mid+1,r,p,v);}inline int query(int x,int l,int r,int p){ if(p<=l)return tr[x].sum; if(r
           
            >1; return query(tr[x].l,l,mid,p)+query(tr[x].r,mid+1,r,p);}int main(){ n=read(); for(int i=1;i<=n;i++){ int a=read(),tmp; if(!in[a]){ insert(rt[i-1],rt[i],1,n,in[a]=i,1); }else{ insert(rt[i-1],tmp,1,n,in[a],-1); insert(tmp,rt[i],1,n,in[a]=i,1); } } m=read(); for(int i=1;i<=m;i++){ int l=read(),r=read(); printf("%d\n",query(rt[r],1,n,l)); } return 0;}
           
          
         
        
       
      
     

+++++++++++++++++++++++++++++++++++++++++++

+本文作者：luyouqi233。 　　　　　　　　　　　　　　+

+欢迎访问我的博客：

+++++++++++++++++++++++++++++++++++++++++++