题目大意：有长度为 n 的序列，强制在线询问 [l,r] 这段区间中所有不同数出现的第一个位置，按照位置从小到大排完序以后的中间（向上取整）的那个位置是多少？
解题思路：把n个元素倒着插进主席树中，把上次出现的同一个值的元素的贡献值-1，新的这个值的贡献值+1，这样就可以把这个元素最左侧的位置的贡献保留。查询区间[L，R]时只要查询第L个版本的主席树就好了。
ps：前一篇博客由于记录的是前缀，所以不能在主席树上进行类似二分的跳跃。
#include <bits/stdc++.h> using namespace std; #define maxn 210000 int treesiz,sum[maxn*40],num,pre[maxn]; int ls[maxn*40],rs[maxn*40],root[maxn],n,m,seq[maxn]; void update(int l,int r,int x,int &y,int pos,int f) { treesiz++;y=treesiz;sum[y]=sum[x]+f; if(l==r) { return ; } ls[y]=ls[x];rs[y]=rs[x]; int mid=(l+r)>>1; if(pos<=mid) update(l,mid,ls[x],ls[y],pos,f); else update(mid+1,r,rs[x],rs[y],pos,f); } int query(int l,int r,int rt,int x,int y) { if(x<=l&&r<=y) return sum[rt]; int mid=(l+r)>>1; int s1=0,s2=0; if(x<=mid) s1=query(l,mid,ls[rt],x,y); if(y>mid) s2=query(mid+1,r,rs[rt],x,y); return s1+s2; } int solve(int l,int r,int rt,int num) { if(l==r) return l; int mid=(l+r)>>1; if(sum[ls[rt]]>=num) return solve(l,mid,ls[rt],num); else return solve(mid+1,r,rs[rt],num-sum[ls[rt]]); } void cn() { memset(ls,0,sizeof(ls)); memset(rs,0,sizeof(rs)); memset(sum,0,sizeof(sum)); memset(pre,0,sizeof(pre)); memset(root,0,sizeof(root)); treesiz=num=0; } int main() { int cas,a,b,c; cin>>cas; for(int ii=1;ii<=cas;ii++) { scanf("%d%d",&n,&m); cn(); for(int i=1;i<=n;i++) { scanf("%d",&seq[i]); } for(int i=n;i;i--) { if(pre[seq[i]]) { update(1,n,root[i+1],root[i],pre[seq[i]],-1); update(1,n,root[i],root[i],i,1); } else { update(1,n,root[i+1],root[i],i,1); } pre[seq[i]]=i; } int l,r,ans=0; printf("Case #%d:",ii); for(int i=1;i<=m;i++) { scanf("%d%d",&l,&r); l = (l+ans)%n+1; r = (r+ans)%n+1; if(l>r) swap(l,r); int len = ( query(1,n,root[l],l,r)+1) / 2; ans=solve(1,n,root[l],len); printf(" %d",ans); } printf("\n"); } return 0; } /* 2 5 2 3 3 1 5 4 2 2 4 4 5 2 2 5 2 1 2 2 3 2 4 1 5 2 2 5 2 1 2 2 3 2 4 */