题目
分析
莫队也能做，但我想练练主席树。
求k-th一样维护第i个时候的线段树，线段树来维护区间不同数。
然后查询时可以通过上下界小优化一波。
但是我的代码丑陋无比，常数巨大（捂脸
代码
#includeusing namespace std;const int maxn=50007;int ls[maxn<<6], rs[maxn<<6], sum[maxn<<6], newp, root[maxn<<6];int last[1000007];inline int in(){ int x=0;char ch=getchar(); while(ch<'0'||ch>'9'){ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x;}void add(int l,int r,int x,int& cur,int cur1,int val){ cur=++newp; ls[cur]=ls[cur1]; rs[cur]=rs[cur1];// root[i]=root[i-1] sum[cur]=sum[cur1]+val; if(l==r) return; int mid=l+r>>1; if(x<=mid) add(l,mid,x,ls[cur],ls[cur1],val); else add(mid+1,r,x,rs[cur],rs[cur1],val);}int query(int l,int r,int cnt,int cnt1,int L){ if(l>=L) return sum[cnt1]-sum[cnt]; int mid=l+r>>1,ans=0; if(mid>=L) ans+=query(l,mid,ls[cnt],ls[cnt1],L); ans+=query(mid+1,r,rs[cnt],rs[cnt1],L); return ans;}int main(){ int n=in(); for(int i=1;i<=n;i++) { int x,temp; x=in(); if(last[x]) { add(1,n,last[x],root[i],root[i-1],-1); add(1,n,i,root[i],root[i],1); } else { add(1,n,i,root[i],root[i-1],1); } last[x]=i; } int q; q=in(); for(int i=1;i<=q;i++) { int l,r; l=in(); r=in(); printf("%d\n",query(1,n,root[l-1],root[r],l)); }}
