KD树水过这道可持久化树套树…其实就是个三维偏序 题解戳这里
CODE
#include <bits/stdc++.h>
using namespace std;
#define ls (t[o].ch[0])
#define rs (t[o].ch[1])
const int MAXN = 100005;
const int inf = 1e9;
inline void read(int &num) {
char ch; int flg=1;
while((ch=getchar())<'0'||ch>'9')if(ch=='-')flg=-flg;
for(num=0;ch>='0'&&ch<='9';num=num*10+ch-'0',ch=getchar());
num*=flg;
}
int D, rt;
struct Node {
int d[3], v;
inline bool operator <(const Node &o)const {
return d[D] < o.d[D];
}
}arr[MAXN];
struct KD_node {
int ch[2], mn[3], mx[3], val;
Node a;
inline void clear() {
ch[0]=ch[1]=val=a.v=0;
for(int l = 0; l < 3; ++l)
mn[l]=mx[l]=a.d[l]=0;
}
}t[MAXN];
struct Query {
int mn[3], mx[3];
};
int bin[MAXN], top, tot, cur;
inline int NewNode() {
if(!top) return ++tot;
t[bin[top]].clear();
return bin[top--];
}
inline void chkmin(int &x, int y) { if(y < x) x = y; }
inline void chkmax(int &x, int y) { if(y > x) x = y; }
inline void mt(int x, int y) {
for(int l = 0; l < 3; ++l)
chkmin(t[x].mn[l], t[y].mn[l]),
chkmax(t[x].mx[l], t[y].mx[l]);
chkmax(t[x].val, t[y].val);
}
inline void upd(int o) {
for(int l = 0; l < 3; ++l)
t[o].mn[l] = t[o].mx[l] = t[o].a.d[l];
t[o].val = t[o].a.v;
if(ls) mt(o, ls);
if(rs) mt(o, rs);
}
inline int build(int l, int r, int nd) {
int mid = (l + r) >> 1; D = nd;
nth_element(arr+l, arr+mid, arr+r+1);
int o = NewNode(); t[o].a = arr[mid];
if(l < mid) ls = build(l, mid-1, (nd+1)%3); else ls = 0;
if(r > mid) rs = build(mid+1, r, (nd+1)%3); else rs = 0;
upd(o); return o;
}
inline int judge(int o, Query q) {
if(q.mn[0] <= t[o].mn[0] && t[o].mx[0] <= q.mx[0]
&& q.mn[1] <= t[o].mn[1] && t[o].mx[1] <= q.mx[1]
&& q.mn[2] <= t[o].mn[2] && t[o].mx[2] <= q.mx[2]) return 1;
if(q.mn[0] > t[o].mx[0] || q.mx[0] < t[o].mn[0]
|| q.mn[1] > t[o].mx[1] || q.mx[1] < t[o].mn[1]
|| q.mn[2] > t[o].mx[2] || q.mx[2] < t[o].mn[2]) return -1;
return 0;
}
int lastans;
inline void query(int o, Query q) {
if(!o || t[o].val <= lastans) return;
int tmp = judge(o, q);
if(tmp == 1) chkmax(lastans, t[o].val);
else if(tmp == -1) return;
else {
if(q.mn[0] <= t[o].a.d[0] && t[o].a.d[0] <= q.mx[0]
&& q.mn[1] <= t[o].a.d[1] && t[o].a.d[1] <= q.mx[1]
&& q.mn[2] <= t[o].a.d[2] && t[o].a.d[2] <= q.mx[2])
chkmax(lastans, t[o].a.v);
int which = t[ls].val < t[rs].val;
query(t[o].ch[which], q);
query(t[o].ch[which^1], q);
}
}
int n, m;
int num[MAXN], pre[MAXN], suf[MAXN], lst[MAXN];
int main () {
read(n), read(m);
for(int i = 1; i <= n; ++i) lst[i] = 0, read(num[i]);
for(int i = 1; i <= n; ++i) pre[i] = lst[num[i]], lst[num[i]] = i;
for(int i = 1; i <= n; ++i) lst[i] = n+1;
for(int i = n; i >= 1; --i) suf[i] = lst[num[i]], lst[num[i]] = i;
for(int i = 1; i <= n; ++i) arr[i] = (Node){{i, pre[i], suf[i]}, num[i]};
rt=build(1, n, 0);
int x, y;
for(int i = 1; i <= m; ++i) {
read(x), read(y);
x = (lastans + x) % n + 1,
y = (lastans + y) % n + 1;
if(y < x) swap(x, y);
lastans = 0;
query(rt, (Query){{x, 0, y+1}, {y, x-1, n+1}});
printf("%d\n", lastans);
}
}