链接：http://acm.hdu.edu.cn/showproblem.php?pid=5919
大致题意：
给你一个长度为n的序列，q个询问，每次询问是给你两个数x,y，经过与上一次的答案进行运算会得到一个区间[x,y]，假设这个区间内有k个数，对k个数第一次出现的位置进行排序取第(k+1)/2个数。
思路：
看题意可知要求的是区间不同数的个数和区间第k小，强制在线，
之前正好写过求区间不同数的个数的三种解法：离线树状数组，主席树，莫队，因为这道题是强制在线，莫队和离线树状数组都不能用，这里就直接用主席树了。
题目要求各个数第一次出现的位置，那么我们只要从后向前插入，重复出现的取消之前的标记，这样维护的标记就都是当前坐标i到n区间内第一次出现的，用主席树维护下就好了。
用主席树求出区间不同数的个数num后， 直接再求区间第(num+1)/2小就好了
注意数组要开大点。。之前数组开小了 超时了
实现代码：
#include<bits/stdc++.h>
using namespace std;
const int M = 2e5 + ;
#define mid int m = (l + r) >> 1
int ls[M*],rs[M*],sum[M*],root[M],a[M],vis[M],idx,ans[M],n; void init()
{
idx = ;root[n+] = ; ans[] = ;
memset(ls,,sizeof(ls));
memset(vis,,sizeof(vis));
memset(rs,,sizeof(rs));
memset(sum,,sizeof(sum));
} void update(int old,int &k,int l,int r,int p,int c){
k = ++idx;
ls[k] = ls[old]; rs[k] = rs[old];
sum[k] = sum[old] + c;
if(l == r) return ;
mid;
if(p <= m) update(ls[old],ls[k],l,m,p,c);
else update(rs[old],rs[k],m+,r,p,c);
} int query(int x,int L,int R,int l,int r){ //求区间不同数的个数
if(L <= l&&R >= r) return sum[x];
mid,ret = ;
if(L <= m) ret += query(ls[x],L,R,l,m);
if(R > m) ret += query(rs[x],L,R,m+,r);
return ret;
} int query1(int x,int l,int r,int k){ //求区间第k小
if(l == r) return l;
mid,ret = sum[ls[x]];
if(ret >= k) return query1(ls[x],l,m,k);
else return query1(rs[x],m+,r,k - ret);
} int main()
{
int t,cas = ,q,x,y;
scanf("%d",&t);
while(t--){
init();
scanf("%d%d",&n,&q);
for(int i = ;i <= n;i ++) scanf("%d",&a[i]);
for(int i = n;i >= ;i --){
int tmp = ;
if(vis[a[i]] == ) update(root[i+],root[i],,n,i,); //添加新标记
else{
update(root[i+],tmp,,n,vis[a[i]],-); //把之前的标记清掉
update(tmp,root[i],,n,i,); //添加新标记
}
vis[a[i]] = i;
}
for(int i = ;i <= q;i ++){
scanf("%d%d",&x,&y);
x = ((x + ans[i-])%n) + ;
y = ((y + ans[i-])%n) + ;
if(x > y) swap(x,y); //倒着输入的，所以取较小的
int num = (query(root[x],x,y,,n) + ) >> ; //得到中位数是区间内第num/2小的数
ans[i] = query1(root[x],,n,num); //求区间内第（num+1）/2小的数
}
printf("Case #%d: ",cas++);
for(int i = ;i < q;i ++) printf("%d ",ans[i]);
printf("%d\n",ans[q]);
}
return ;
}