题意：有A1 ~ An组成的数组，给你l r，L = min((l + ans[i - 1]) % n + 1, (r + ans[i - 1]) % n + 1)，R = max((l + ans[i - 1]) % n + 1, (r + ans[i - 1]) % n + 1)，你先需要的到L，R区间有k个不同的数字，然后问你L，R区间第（k + 1）/ 2个不同的数字下标是多少？
思路：显然是个在线询问。
我们之前已经会用主席树求区间内有多少不同数字了：从左到右把每个数字的位置存进每个操作的线段树，如果之前这个数已经出现，就在当前这棵线段树中删掉之前出现的位置，以保证每个数字出现的唯一性。显然每个区间保存的是某个数字最右边出现的位置。
但是这里显然我们不能去直接求第（k + 1）/ 2个不同的数字下标，因为我这里要求的是最早出现第（k + 1）/ 2个数的位置。那我直接从n往1建主席树，那我就变成了每个区间保存的是某个数字最左边出现的位置，显然我第i棵树并没有保存i前面的位置，那我就可以直接求i到后面任意位置的区间的第p个不相同数出现的位置。
代码：
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<cstdio>
#include<vector>
#include<cstring>
#include <iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int maxn = 2e5 + ;
const int M = maxn * ;
const ull seed = ;
const int INF = 0x3f3f3f3f;
const int MOD = ;
int a[maxn], root[maxn], tot;
int n, q;
struct node{
int lson, rson;
int sum;
}T[maxn * ];
int fa[maxn], ans[maxn];
void init(){
tot = ;
memset(fa, -, sizeof(fa));
memset(T, , sizeof(T));
}
void update(int l, int r, int &now, int pre, int pos, int v){
T[++tot] = T[pre], now = tot;
T[now].sum += v;
if(l == r) return;
int m = (l + r) >> ;
if(pos <= m)
update(l, m, T[now].lson, T[pre].lson, pos, v);
else
update(m + , r, T[now].rson, T[pre].rson, pos, v);
}
int query1(int l, int r, int L, int R, int now){
if(L <= l && R >= r){
return T[now].sum;
}
int m = (l + r) >> , sum = ;
if(L <= m)
sum += query1(l, m, L, R, T[now].lson);
if(R > m)
sum += query1(m + , r, L, R, T[now].rson);
return sum;
}
int query2(int l, int r, int now, int k){
if(l == r) return l;
int m = (l + r) >> ;
int sum = T[T[now].lson].sum;
if(sum >= k)
return query2(l, m, T[now].lson, k);
else
return query2(m + , r, T[now].rson, k - sum);
}
int main(){
int ca = , t;
scanf("%d" ,&t);
while(t--){
init();
scanf("%d%d", &n, &q);
root[n + ] = ;
for(int i = ; i <= n; i++)
scanf("%d", &a[i]);
for(int i = n; i >= ; i--){
if(fa[a[i]] == -){
update(, n, root[i], root[i + ], i, );
fa[a[i]] = i;
}
else{
update(, n, root[i], root[i + ], i, );
update(, n, root[i], root[i], fa[a[i]], -);
fa[a[i]] = i;
}
}
ans[] = ;
for(int i = ; i <= q; i++){
int l, r, L, R, k;
scanf("%d%d", &l, &r);
L = min((l + ans[i - ]) % n + , (r + ans[i - ]) % n + );
R = max((l + ans[i - ]) % n + , (r + ans[i - ]) % n + );
k = query1(, n, L, R, root[L]);
ans[i] = query2(, n, root[L], (k + ) / );
}
printf("Case #%d:", ca++);
for(int i = ; i <= q; i++)
printf(" %d", ans[i]);
printf("\n");
} return ;
}