(kdt)就是数点神器
我们先扫两遍处理出每个数上一次出现的位置(pre_i,nxt_i)，之后变成((i,pre_i,nxt_i))这样一个三维空间上的点
就变成了求一个立方体的最大值了
随便剪剪枝就过了
代码
#include<bits/stdc++.h>
#define re register
#define max(a,b) ((a)>(b)?(a):(b))
inline int read() {
char c=getchar();int x=0;while(c<'0'||c>'9') c=getchar();
while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+c-48,c=getchar();return x;
}
const int maxn=100005;
struct Point{int v,x[3];}p[maxn];
int a[maxn],pre[maxn],nxt[maxn],st[maxn];
int n,m,op,L[3],R[3],cnt,lst;
int mn[maxn][3],mx[maxn][3],pos[maxn],l[maxn],r[maxn],d[maxn];
inline int cmp(const Point &A,const Point &B) {return A.x[op]<B.x[op];}
inline void pushup(int k) {
mx[k][0]=mn[k][0]=p[pos[k]].x[0];
mx[k][1]=mn[k][1]=p[pos[k]].x[1];
mx[k][2]=mn[k][2]=p[pos[k]].x[2];
d[k]=max(d[l[k]],d[r[k]]);d[k]=max(d[k],p[pos[k]].v);
for(re int i=0;i<3;i++) {
if(mx[l[k]][i]>mx[k][i]) mx[k][i]=mx[l[k]][i];
if(mx[r[k]][i]>mx[k][i]) mx[k][i]=mx[r[k]][i];
if(l[k]&&mn[l[k]][i]<mn[k][i]) mn[k][i]=mn[l[k]][i];
if(r[k]&&mn[r[k]][i]<mn[k][i]) mn[k][i]=mn[r[k]][i];
}
}
int build(int x,int y,int o) {
if(x>y) return 0;
int mid=x+y>>1,k=++cnt;
op=o%3;std::nth_element(p+x,p+mid,p+y+1,cmp);
l[k]=build(x,mid-1,o+1),r[k]=build(mid+1,y,o+1);
pos[k]=mid;pushup(k);return k;
}
inline int chk(int k) {
return p[k].x[0]>=L[0]&&p[k].x[0]<=R[0]&&p[k].x[1]>=L[1]&&p[k].x[1]<=R[1]&&p[k].x[2]>=L[2]&&p[k].x[2]<=R[2];
}
inline int out(int k) {
return R[0]<mn[k][0]||L[0]>mx[k][0]||R[1]<mn[k][1]||L[1]>mx[k][1]||R[2]<mn[k][2]||L[2]>mx[k][2];
}
inline int in(int k) {
return L[0]<=mn[k][0]&&R[0]>=mx[k][0]&&L[1]<=mn[k][1]&&R[1]>=mx[k][1]&&L[2]<=mn[k][2]&&R[2]>=mx[k][2];
}
void query(int k) {
if(in(k)) {lst=max(lst,d[k]);return;}
if(chk(pos[k])) lst=max(lst,p[pos[k]].v);
if(l[k]&&!out(l[k])&&lst<d[l[k]]) query(l[k]);
if(r[k]&&!out(r[k])&&lst<d[r[k]]) query(r[k]);
}
int main() {
n=read(),m=read();
for(re int i=1;i<=n;i++) a[i]=read();
for(re int i=1;i<=n;i++)
pre[i]=st[a[i]],st[a[i]]=i;
for(re int i=1;i<=n;i++) st[i]=n+1;
for(re int i=n;i;--i)
nxt[i]=st[a[i]],st[a[i]]=i;
for(re int i=1;i<=n;i++)
p[i].x[0]=i,p[i].x[1]=pre[i],p[i].x[2]=nxt[i],p[i].v=a[i];
build(1,n,0);int x,y;
L[1]=0,R[2]=n+1;
while(m--) {
x=read()+lst,y=read()+lst;
x%=n,y%=n,++x,++y;
if(x>y) std::swap(x,y);
L[0]=x,R[0]=y;R[1]=x-1,L[2]=y+1;
lst=0;query(1);printf("%d
",lst);
}
return 0;
}