题目链接 2016年长春ccpc I 题
题目大意 ：
给你n(n≤2∗105n≤2∗105)个数，每个数的大小 0<Ai≤2∗10^5 0<Ai≤2∗10^5。
再给你m(m≤2∗105≤2∗105)个询问。对于每个询问输入l,r,表示Al...ArAl...Ar这个区间我们得到每个数第一次出现的位置下标的排列，
假设这个区间有k个不同的数，我们得到的排列是p1<p2<p3<...<pkp1<p2<p3<...<pk，叫你求第(k+1)/2这个数是所在的位置是哪个？
主席树正着插能得到每个区间不同数最后一次出现的位置，反着插的话可以得到每个不同数第一次出现的位置
然后就是查找区间k值
#include<bits/stdc++.h> using namespace std; #define maxn 200005 struct ac{ int va,l,r; }tre[40*maxn]; int a[maxn],root[maxn],tot,fa[maxn]; void init(){ memset(root,0,sizeof(root)); memset(tre,0,sizeof(tre)); memset(fa,0,sizeof(fa)); tot=0; } void updata(int l,int r,int &x,int y,int z,int va){ tre[++tot]=tre[y]; tre[tot].va+=va; x=tot; if(l==r) return ; int mid=(l+r)/2; if(z<=mid) updata(l,mid,tre[x].l,tre[y].l,z,va); else updata(mid+1,r,tre[x].r,tre[y].r,z,va); } int query(int l,int r,int x,int k){ if(l==r) return l; int s=tre[tre[x].l].va; int mid=(l+r)/2; if(k<=s){ return query(l,mid,tre[x].l,k); } return query(mid+1,r,tre[x].r,k-s); } int getsum(int l,int r,int x,int y,int z){ if(l==x&&y==r) return tre[z].va; int mid=(l+r)/2; if(y<=mid){ return getsum(l,mid,x,y,tre[z].l); }else if(x>mid){ return getsum(mid+1,r,x,y,tre[z].r); }else{ return getsum(l,mid,x,mid,tre[z].l)+getsum(mid+1,r,mid+1,y,tre[z].r); } } int main(){ int t,cnt=1; cin>>t; while(t--){ init(); int n,m; cin>>n>>m; for(int j=1;j<=n;j++){ scanf("%d",&a[j]); } for(int j=n;j>=1;j--){ if(fa[a[j]]){ updata(1,n,root[j],root[j+1],fa[a[j]],-1); updata(1,n,root[j],root[j],j,1); }else{ updata(1,n,root[j],root[j+1],j,1); } fa[a[j]]=j; } int ans=0; printf("Case #%d:",cnt++); for(int j=0;j<m;j++){ int x,y,l,r; scanf("%d%d",&x,&y); x=(x+ans)%n+1; y=(y+ans)%n+1; l=min(x,y);r=max(x,y); int s=getsum(1,n,l,r,root[l]); s=(s+1)/2; ans=query(1,n,root[l],s); printf(" %d",ans); } printf(" "); } }