题目描述
因为是OJ上的题，就简单点好了。给出一个长度为n的序列，给出M个询问：在[l,r]之间找到一个在这个区间里只出现过一次的数，并且要求找的这个数尽可能大。如果找不到这样的数，则直接输出0。我会采取一些措施强制在线。
输入
第一行为两个整数N,M。M是询问数，N是序列的长度（N<=100000，M<=200000)
第二行为N个整数，描述这个序列{ai}，其中所有1<=ai<=N
再下面M行，每行两个整数x，y，
询问区间[l,r]由下列规则产生（OIER都知道是怎样的吧>_<)：
l=min(（x+lastans)mod n+1,(y+lastans）mod n+1);
r=max(（x+lastans)mod n+1,(y+lastans）mod n+1);
Lastans表示上一个询问的答案，一开始lastans为0
输出
一共M行，每行给出每个询问的答案。
样例输入
10 10
6 4 9 10 9 10 9 4 10 4
3 8
10 1
3 4
9 4
8 1
7 8
2 9
1 1
7 3
9 9
样例输出
4
10
10
0
0
10
0
4
0
4
题解
三维KD-tree
一个数在区间[l,r]内仅出现过一次，当且仅当：它在[l,r]之间，它的上一个位置在[0,l-1]之间，它的下一个位置在[r+1,n+1]之间。
于是我们可以处理出一个数的上一个出现位置和下一个出现位置，把它的位置与这两个位置放在一起，看作三维空间的点。每次查询就是查区域内点的权值的最大值。
用三维KD-tree维护一下就好。
注意剪枝，如果一个空间内的点的权值的最大值<=ans，那么直接跳出。
再也不丧心病狂的把cmp函数写错了QAQ
#include <cstdio>
#include <cstring>
#include <algorithm>
#define N 100010
#define rep for(int i = 0 ; i < 3 ; i ++ )
using namespace std;
int v[N] , last[N] , next[N] , pos[N] , d , root , l , r , ans;
struct data
{
int p[3] , maxn[3] , minn[3] , w , val , c[2];
bool operator <(data b)const
{
return p[d] == b.p[d] ? p[(d + 1) % 3] == b.p[(d + 1) % 3] ? p[(d + 2) % 3] < b.p [(d + 2) % 3] : p[(d + 1) % 3] < b.p[(d + 1) % 3] : p[d] < b.p[d];
}
}a[N];
inline int read()
{
int ret = 0; char ch = getchar();
while(ch < '0' || ch > '9') ch = getchar();
while(ch >= '0' && ch <= '9') ret = (ret << 3) + (ret << 1) + ch - '0' , ch = getchar();
return ret;
}
void pushup(int x , int k)
{
rep a[x].maxn[i] = max(a[x].maxn[i] , a[k].maxn[i]) , a[x].minn[i] = min(a[x].minn[i] , a[k].minn[i]);
a[x].val = max(a[x].val , a[k].val);
}
int build(int l , int r , int now)
{
int mid = (l + r) >> 1;
d = now , nth_element(a + l , a + mid , a + r + 1);
rep a[mid].maxn[i] = a[mid].minn[i] = a[mid].p[i];
a[mid].val = a[mid].w;
if(l < mid) a[mid].c[0] = build(l , mid - 1 , (now + 1) % 3) , pushup(mid , a[mid].c[0]);
if(r > mid) a[mid].c[1] = build(mid + 1 , r , (now + 1) % 3) , pushup(mid , a[mid].c[1]);
return mid;
}
bool judge(int x)
{
return a[x].val > ans && a[x].maxn[0] >= l && a[x].minn[0] <= r && a[x].minn[1] < l && a[x].maxn[2] > r;
}
void query(int x)
{
if(!x || !judge(x)) return;
if(a[x].p[0] >= l && a[x].p[0] <= r && a[x].p[1] < l && a[x].p[2] > r) ans = max(ans , a[x].w);
query(a[x].c[0]) , query(a[x].c[1]);
}
int main()
{
int n , m , i;
n = read() , m = read();
for(i = 1 ; i <= n ; i ++ ) v[i] = read() , last[i] = pos[v[i]] , next[pos[v[i]]] = i , pos[v[i]] = i;
for(i = 1 ; i <= n ; i ++ ) a[i].p[0] = i , a[i].p[1] = last[i] , a[i].p[2] = next[i] ? next[i] : n + 1 , a[i].w = v[i];
root = build(1 , n , 0);
while(m -- )
{
l = read() , r = read() , l = (l + ans) % n + 1 , r = (r + ans) % n + 1;
if(l > r) swap(l , r);
ans = 0 , query(root) , printf("%d
" , ans);
}
return 0;
}