Description
给出一个长度为n的序列，给出M个询问：在[l,r]之间找到一个在这个区间里只出现过一次的数，并且要求找的这个数尽可能大。如果找不到这样的数，则直接输出0。我会采取一些措施强制在线。N<=100000，M<=200000
先给出一种MLE做法：
假设询问离线，那么我们就是要找一个权值x使得在前缀[1，r]中最后一个的位置（设为now[x]），now[x]<=r&&now[x]>=l。并且倒数第二的位置（设为pre[x]），pre[x]< l。那么我们可以用树套树来维护。外层维护权值，内层维护区间，对于一个权值，我们在now的位置+1，pre的位置-1，那么当前权值有解当且仅当维护区间的线段树上的查询[l,r]的答案>0。那么对于now和pre对于前缀[1,r]的改变，我们发现每次只会改变一个权值，那么可以可持久化一下，每次在外层当前权值的路径上 pre[last] +1 pre[x] -2 now[x] +1。
然后，嘿嘿嘿，对于区间中每个位置，我们都需要的新开空间。【哭死在可持久化树套树MLE+RE的路上】
下面给出【正解】另一种可持久化树套树的方法：
对于一个点x，我们设
1.pre[x]：表示x位置之前最近的和x权值相等的位置。
2.nxt[x]：表示x位置之后最近的和x权值相等的位置。
那么x可选当且仅当：pre[x]< l nxt[x]> r l<= x <=r
对于所有的x，pre[x]，nxt[x]这样的三元组，我们先按照pre排序【可持久化】，外层线段树维护nxt，内层线段树维护关于位置x的区间对应的权值的最大值，nxt[x]到根节点的路径上都修改区间[l,r]的最大值。
发现区间位置至多只会当一次pre，那么每次只需要log^2n的空间。【对对对，是是是】
【另外，据说KD-tree可以轻松过掉这道题】
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
char nc()
{
static char buf[100000],*p1,*p2;
return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
void read(int &x)
{
x=0; char ch=nc();
while(!isdigit(ch)) ch=nc();
while(isdigit(ch)) x=x*10+ch-'0',ch=nc();
}
struct node
{
int pre,nxt,i,w;
}a[101000];
bool cmp(node x,node y){return x.pre<y.pre;}
int n,m,p[101000],rot[101000];
struct seg
{
int ls,rs,rt;
}tr[1800000];
struct dataseg
{
int ls,rs,mx;
}t[40000000];
int se,dse;
void fix(int &r1,int r2,int l,int r,int x,int y)
{
r1=++se; t[r1].mx=max(t[r2].mx,y);
if(l==r) return ; int mid=(l+r)>>1;
if(x<=mid) t[r1].rs=t[r2].rs,fix(t[r1].ls,t[r2].ls,l,mid,x,y);
else t[r1].ls=t[r2].ls,fix(t[r1].rs,t[r2].rs,mid+1,r,x,y);
}
void Fix(int &r1,int r2,int l,int r,int x,int y,int z)
{
r1=++dse; tr[r1].rt=tr[r2].rt;
fix(tr[r1].rt,tr[r1].rt,1,n,y,z);
if(l==r) return ; int mid=(l+r)>>1;
if(x<=mid) tr[r1].rs=tr[r2].rs,Fix(tr[r1].ls,tr[r2].ls,l,mid,x,y,z);
else tr[r1].ls=tr[r2].ls,Fix(tr[r1].rs,tr[r2].rs,mid+1,r,x,y,z);
}
int query(int r1,int l,int r,int x,int y)
{
if(x<=l&&y>=r) return t[r1].mx;
int mid=(l+r)>>1;
if(y<=mid) return query(t[r1].ls,l,mid,x,y);
else if(x>mid) return query(t[r1].rs,mid+1,r,x,y);
else return max(query(t[r1].ls,l,mid,x,y),query(t[r1].rs,mid+1,r,x,y));
}
int Query(int pos,int l,int r,int x,int y,int xx,int yy)
{
if(x<=l&&y>=r) return query(tr[pos].rt,1,n,xx,yy);
int mid=(l+r)>>1;
if(y<=mid) return Query(tr[pos].ls,l,mid,x,y,xx,yy);
else if(x>mid) return Query(tr[pos].rs,mid+1,r,x,y,xx,yy);
else return max(Query(tr[pos].ls,l,mid,x,y,xx,yy),Query(tr[pos].rs,mid+1,r,x,y,xx,yy));
}
int main()
{
read(n); read(m); int x;
for(int i=1;i<=n;++i)
{
read(x); a[i].nxt=n+1; a[i].i=i; a[i].w=x;
if(p[x]) a[p[x]].nxt=i;
a[i].pre=p[x]; p[x]=i;
}
sort(a+1,a+n+1,cmp);
int now=1;
for(int i=1;i<=n;++i)
{
rot[i]=rot[i-1];
while(now<=n&&a[now].pre<i)
{
Fix(rot[i],rot[i],1,n+1,a[now].nxt,a[now].i,a[now].w);
now++;
}
}
int y,l,r,ans=0;
while(m--)
{
read(x); read(y);
l=min((x+ans)%n+1,(y+ans)%n+1);
r=max((x+ans)%n+1,(y+ans)%n+1);
printf("%d\n",ans=Query(rot[l],1,n+1,r+1,n+1,l,r));
}
return 0;
}