先预处理出两个个数组pre，next。pre[i]表示上一个与i位置数字相同的位置，若不存在则设为0；next[i]表示下一个与i位置数字相同的位置，若不存在则设为n+1。那么一个满足在区间[L,R]中只出现一次的数字，其pre[i]<L,next[i]>R。
这样我们可以先将pre进行排序，然后将pre可持久化，外层线段树套的是当前数字的位置i，内层线段树套的是next[i]。外层线段树的节点总数是nlogn，内层线段树节点总数是nlogn^2。时间复杂度O(nlogn^2)。
代码
#include<cstdio>
#include<cstring>
#include<algorithm>
#define N 40000000
#define M 100010
#define Q 2000000
using namespace std;
int n,m,i,a[M],tmp[M],tt,stt,ls[Q],rs[Q],root[M],L,R,e[M];
int subroot[Q],u,v,ans;
struct ff
{
int next,pre,idx;
}f[M];
struct g
{
int ls,rs,s;
}sub[N];
inline void ll(int x,int y)
{
ls[x]=ls[y];
}
inline void rr(int x,int y)
{
rs[x]=rs[y];
}
inline void sl(int x,int y)
{
sub[x].ls=sub[y].ls;
}
inline void sr(int x,int y)
{
sub[x].rs=sub[y].rs;
}
bool cmp(ff a,ff b)
{
return a.pre<b.pre;
}
void subinsert(int &x,int y,int l,int r,int a,int b)
{
int m;
stt++;x=stt;
sub[x].s=max(sub[y].s,b);
if (r-l==) return;
m=(l+r)>>;
sl(x,y);
sr(x,y);
if (a-<m) subinsert(sub[x].ls,sub[y].ls,l,m,a,b);
if (m<a) subinsert(sub[x].rs,sub[y].rs,m,r,a,b);
}
void insert(int &x,int y,int l,int r,int a,int b,int c)
{
int m;
tt++;x=tt;
subinsert(subroot[x],subroot[y],,n+,b,c);
if (r-l==) return;
m=(l+r)>>;
ll(x,y);rr(x,y);
if (a-<m)
insert(ls[x],ls[y],l,m,a,b,c);
if (m<a)
insert(rs[x],rs[y],m,r,a,b,c);
}
int subquery(int x,int l,int r,int a,int b)
{
int m,ans=;
if (x==) return ;
if ((a<=l)&&(r<=b))
return sub[x].s;
m=(l+r)>>;
if (a<m) ans=max(ans,subquery(sub[x].ls,l,m,a,b));
if (m<b) ans=max(ans,subquery(sub[x].rs,m,r,a,b));
return ans;
}
int query(int x,int l,int r,int a,int b)
{
int m,ans=;
if (x==) return ;
if ((a<=l)&&(r<=b))
return subquery(subroot[x],,n+,b,n+);
m=(l+r)>>;
if (a<m) ans=max(ans,query(ls[x],l,m,a,b));
if (m<b) ans=max(ans,query(rs[x],m,r,a,b));
return ans;
}
int main()
{
scanf("%d%d",&n,&m);
for (i=;i<=n;i++)
scanf("%d",&a[i]);
for (i=;i<=n;i++)
{
f[i].pre=tmp[a[i]];
tmp[a[i]]=i;
}
for (i=;i<=n;i++)
tmp[i]=n+;
for (i=n;i>=;i--)
{
f[i].next=tmp[a[i]];
tmp[a[i]]=i;
f[i].idx=i;
}
sort(f+,f++n,cmp);
for (i=;i<=n;i++)
{
insert(root[i],root[i-],,n,f[i].idx,f[i].next,a[f[i].idx]);
}
for (i=;i<=n;i++)
e[f[i].pre]=i;
for (i=;i<=n;i++)
if (e[i]==)
e[i]=e[i-];
for (i=;i<=m;i++)
{
scanf("%d%d",&u,&v);
L=(u+ans)%n+;
R=(v+ans)%n+;
if (L>R) swap(L,R);
ans=query(root[e[L-]],,n,L-,R);
printf("%d\n",ans);
}
}