题意：
给一串数字，每个数字的位置是这个数第一次出现的位置。
每个询问对于序列的一个子区间，设一共有k个不同的数，求第ceil(k/2)个数的位置。
因为强制在线，所以离线乱搞pass掉。
主席树可解。
考虑一个数列：
p 1 2 3 4 5 6 // 原序列标号
a : 1 2 1 2 3 4 // 原序列
p1 1 2 1 2 5 6 // 子序列开始下标为1
p2 2 3 1 5 6
p3 3 4 5 6
p4 4 5 6
p5 5 6
p6 6
有一个规律就是对于以L为开始的子序列来说，只要求出[L, N]的子区间，R是不影响P(L)数组的。
那么就想到将数组倒过来建主席树。
树里存的是什么呢？？？？
存的是…【此处想了10分钟……】…区间内不同数的个数（只考虑第一次出现的）
那么在用一个数组记录每个数第一个出现的位置，每添加一个数，该位置+1，如果一个数之前出现过，那么就要更改之前第一次出现的位置-1。
不是很会主席树，之前就写过一道模板题= = 强行没看题解，一顿乱搞还是搞出来了，但是估计写的很麻烦
#include <bits/stdc++.h>
using namespace std; const int N = ; struct node {
int l, r, v;
} T[N*]; int a[N];
int pos[N];
int root[N], cnt;
int ans;
// y is x previous version
void update(int l, int r, int &x, int y, int p, int v) {
T[++cnt] = T[y], T[cnt].v += v; x = cnt;
if (l == r) return ;
int mid = (l+r) >> ;
if (mid >= p) update(l, mid, T[x].l, T[y].l, p, v);
else update(mid+, r, T[x].r, T[y].r, p, v);
} // p1 > p2
void update(int l, int r, int &x, int y, int p1, int v1, int p2, int v2) {
T[++cnt] = T[y]; x = cnt;
if (l == r) return ;
int mid = (l+r) >> ;
// three conditions
// p1 > mid >= p2, p1 > p2 > mid, mid >= p1 > p2
if (p1 > mid && p2 <= mid) {
update(mid+, r, T[x].r, T[y].r, p1, v1);
update(l, mid, T[x].l, T[y].l, p2, v2);
} else if (p2 > mid) {
update(mid+, r, T[x].r, T[y].r, p1, v1, p2, v2);
} else {
update(l, mid, T[x].l, T[y].l, p1, v1, p2, v2);
}
} void query(int l, int r, int x, int k) {
if (l == r) {
ans = l; return ;
}
int mid = (l+r) >> ;
if (T[T[x].r].v >= k) {
ans = mid+;
query(mid+, r, T[x].r, k);
} else {
query(l, mid, T[x].l, k-T[T[x].r].v);
}
} int query(int l, int r, int x, int L, int R) {
if (l >= L && r <= R) return T[x].v;
int mid = (l+r) >> ;
int ans = ;
if (mid >= L) ans += query(l, mid, T[x].l, L, R);
if (mid < R) ans += query(mid+, r, T[x].r, L, R);
return ans;
} int main()
{
//freopen("in.txt", "r", stdin);
int t, cas = ;
scanf("%d", &t); while (t--) {
printf("Case #%d:", ++cas);
ans = ;
int n, q, l_, r_, l, r, k;
scanf("%d%d", &n, &q);
memset(pos, , sizeof pos); cnt = ;
for (int i = ; i <= n; ++i) scanf("%d", &a[n-i+]);
for (int i = ; i <= n; ++i) {
if (pos[a[i]]) update(, n, root[i], root[i-], i, , pos[a[i]], -);
else update(, n, root[i], root[i-], i, );
pos[a[i]] = i;
}
while (q--) {
scanf("%d%d", &l_, &r_);
l_ = (l_ + ans) % n + ;
r_ = (r_ + ans) % n + ;
l = min(l_, r_);
r = max(l_, r_);
l = n-l+, r = n-r+; swap(l, r);
k = query(, n, root[r], l, r);
query(, n, root[r], ceil(k/2.0));
ans = n-ans+;
printf(" %d", ans);
}
printf("\n");
}
return ;
}