思路：主席树维护区间种类数。 需要注意：区间种类数不能由区间端点做差得到； 那，倒着建主席树就可以在树上二分找位置了。 因为如果正着建树的话，在树上找位置的时候，就会有不在询问区间却产生影响的一些数。
#pragma GCC optimize(2) #pragma GCC optimize(3) #include <bits/stdc++.h> using namespace std; const int N=2e5+3; int n,q,tot; int T,cas,ans[N],vis[N],a[N]; int t[N*40]; int ls[N*40],rs[N*40]; int root[N]; #define fi(n) FastIO::read(n) inline void update(int &rt,int pre,int pos,int c,int l,int r){ if(l>pos||r<pos)return ; t[rt=++tot]=t[pre]; ls[rt]=ls[pre],rs[rt]=rs[pre]; t[rt]+=c; if(l==r){ return; } int m =(l+r)>>1; if(pos<=m)update(ls[rt],ls[pre],pos,c,l,m); else update(rs[rt],rs[pre],pos,c,m+1,r); } inline int get(int rt,int x,int y,int l,int r){ if(l>=x&&r<=y)return t[rt]; int m=l+r>>1,z=0; if(x<=m)z+=get(ls[rt],x,y,l,m); if(y>m)z+=get(rs[rt],x,y,m+1,r); return z; } inline int ge(int rt,int l,int r,int k){ if(l==r)return l; int lss=t[ls[rt]]; int mid=l+r>>1; if(lss>=k)return ge(ls[rt],l,mid,k); else return ge(rs[rt],mid+1,r,k-t[ls[rt]]); } inline void pu(int x){ if(x<10){ putchar(x%10+'0'); return; } pu(x/10); putchar(x%10+'0'); } void read(int &x){ scanf("%d",&x); } int main(){ for(read(T);T;T--){ if(T>2)return -1; read(n);read(q); tot=0; for(int i=1;i<=200001;i++)vis[i]=0; for(int i=1;i<=n;i++)read(a[i]); for(int i=n;i>=1;i--){ a[i]++; if(vis[a[i]]){ int k=0; update(k,root[i+1],vis[a[i]],-1,1,n); update(root[i],k,i,1,1,n); }else{ update(root[i],root[i+1],i,1,1,n); } vis[a[i]]=i; } for(int i=1;i<=q;i++){ int l,r; read(l);read(r); l=(l+ans[i-1])%n+1; r=(r+ans[i-1])%n+1; if(l>r)swap(l,r); int cnt=get(root[l],l,r,1,n); int k=(cnt+1)/2; ans[i]=ge(root[l],1,n,k); } printf("Case #%d: ",++cas); for(int i=1;i<=q;i++){ pu(ans[i]); if(i==q)puts(""); else putchar(' '); } if(T==2){ memset(t,0,sizeof t); memset(ls,0,sizeof ls); memset(rs,0,sizeof rs); memset(root,0,sizeof root); } } return 0; }