题目说了要在[l,r]中找只出现过一次的数，那么就可以转换成是说上一次这个数出现在l之前，下一次这个数出现在r之后，且最大，那么就可以转化成一个K-D Tree问题。
设(pre[i])为上一次(a[i])出现的位置，(nxt[i])为下一次(a[i])出现的位置，那一个结构体({i，pre[i],nxt[i]})，建三维K-D Tree，在K-D Tree中查询最大即可。
三个判断函数：
bool inside(int hao)//全部在里面
{
if(tr[hao].minn[0]>=l&&tr[hao].maxn[0]<=r&&tr[hao].maxn[1]<l&&tr[hao].minn[2]>r)
{
return 1;
}
return 0;
}
bool jiao(int hao)//至少中位数那个点在里面
{
if(tr[hao].dian.x[0]>=l&&tr[hao].dian.x[0]<=r&&tr[hao].dian.x[1]<l&&tr[hao].dian.x[2]>r)
{
return 1;
}
return 0;
}
bool outside(int hao)//全部在外面
{
if(tr[hao].maxn[0]<l||tr[hao].minn[0]>r||tr[hao].minn[1]>=l||tr[hao].maxn[2]<=r)
{
return 1;
}
return 0;
}
程序：
#include<bits/stdc++.h>
#define N 100010
using namespace std;
struct node
{
int x[4];
}p[N];
struct data
{
int ls,rs,maxn[3],minn[3],val;
node dian;
}tr[N*20];
int D,l,r,x,y,lastans,n,m,a[N],pre[N],wh[N],nxt[N],rt;
bool operator < (node a,node b)
{
return a.x[D]<b.x[D];
}
void up(int hao)
{
for(int i=0;i<=2;i++)
{
tr[hao].minn[i]=tr[hao].maxn[i]=tr[hao].dian.x[i];
if(tr[hao].ls)
{
tr[hao].minn[i]=min(tr[hao].minn[i],tr[tr[hao].ls].minn[i]);
tr[hao].maxn[i]=max(tr[hao].maxn[i],tr[tr[hao].ls].maxn[i]);
}
if(tr[hao].rs)
{
tr[hao].minn[i]=min(tr[hao].minn[i],tr[tr[hao].rs].minn[i]);
tr[hao].maxn[i]=max(tr[hao].maxn[i],tr[tr[hao].rs].maxn[i]);
}
}
tr[hao].val=max(tr[tr[hao].ls].val,max(tr[tr[hao].rs].val,tr[hao].dian.x[3]));
}
int build(int l,int r,int du)
{
if(l>r)
{
return 0;
}
int mid=(l+r)>>1;
D=du;
nth_element(p+l,p+mid,p+r+1);
tr[mid].dian=p[mid];
tr[mid].ls=build(l,mid-1,(du+1)%3);
tr[mid].rs=build(mid+1,r,(du+1)%3);
up(mid);
return mid;
}
bool inside(int hao)//全部在里面
{
if(tr[hao].minn[0]>=l&&tr[hao].maxn[0]<=r&&tr[hao].maxn[1]<l&&tr[hao].minn[2]>r)
{
return 1;
}
return 0;
}
bool jiao(int hao)//至少中位数那个点在里面
{
if(tr[hao].dian.x[0]>=l&&tr[hao].dian.x[0]<=r&&tr[hao].dian.x[1]<l&&tr[hao].dian.x[2]>r)
{
return 1;
}
return 0;
}
bool outside(int hao)//全部在外面
{
if(tr[hao].maxn[0]<l||tr[hao].minn[0]>r||tr[hao].minn[1]>=l||tr[hao].maxn[2]<=r)
{
return 1;
}
return 0;
}
void query(int hao)//查询
{
if(inside(hao))
{
lastans=max(lastans,tr[hao].val);
return;
}
if(outside(hao))
{
return;
}
if(jiao(hao))
{
lastans=max(lastans,tr[hao].dian.x[3]);
}
int disl=tr[tr[hao].ls].val,disr=tr[tr[hao].rs].val;
if(disl>disr)
{
if(disl>lastans)
{
query(tr[hao].ls);
if(disr>lastans)
{
query(tr[hao].rs);
}
}
}else{
if(disr>lastans)
{
query(tr[hao].rs);
if(disl>lastans)
{
query(tr[hao].ls);
}
}
}
}
int main()
{
// freopen("1.txt","r",stdin);
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)//找前后的位置
{
scanf("%d",&a[i]);
pre[i]=wh[a[i]];
wh[a[i]]=i;
}
for(int i=1;i<=n;i++)//后面没有就是n+1
{
wh[i]=n+1;
}
for(int i=n;i>=1;i--)
{
nxt[i]=wh[a[i]];
wh[a[i]]=i;
}
for(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].x[3]=a[i];
}
rt=build(1,n,0);
for(int i=1;i<=m;i++)
{
scanf("%d%d",&x,&y);
l=min((x+lastans)%n+1,(y+lastans)%n+1);
r=max((x+lastans)%n+1,(y+lastans)%n+1);
lastans=0;
query(rt);
printf("%d
",lastans);
}
return 0;
}