先预处理出两个个数组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)。
代码
1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 #define N 40000000 5 #define M 100010 6 #define Q 2000000 7 using namespace std; 8 int n,m,i,a[M],tmp[M],tt,stt,ls[Q],rs[Q],root[M],L,R,e[M]; 9 int subroot[Q],u,v,ans; 10 struct ff 11 { 12 int next,pre,idx; 13 }f[M]; 14 struct g 15 { 16 int ls,rs,s; 17 }sub[N]; 18 inline void ll(int x,int y) 19 { 20 ls[x]=ls[y]; 21 } 22 inline void rr(int x,int y) 23 { 24 rs[x]=rs[y]; 25 } 26 inline void sl(int x,int y) 27 { 28 sub[x].ls=sub[y].ls; 29 } 30 inline void sr(int x,int y) 31 { 32 sub[x].rs=sub[y].rs; 33 } 34 bool cmp(ff a,ff b) 35 { 36 return a.pre<b.pre; 37 } 38 void subinsert(int &x,int y,int l,int r,int a,int b) 39 { 40 int m; 41 stt++;x=stt; 42 sub[x].s=max(sub[y].s,b); 43 if (r-l==1) return; 44 m=(l+r)>>1; 45 sl(x,y); 46 sr(x,y); 47 if (a-1<m) subinsert(sub[x].ls,sub[y].ls,l,m,a,b); 48 if (m<a) subinsert(sub[x].rs,sub[y].rs,m,r,a,b); 49 } 50 void insert(int &x,int y,int l,int r,int a,int b,int c) 51 { 52 int m; 53 tt++;x=tt; 54 subinsert(subroot[x],subroot[y],0,n+1,b,c); 55 if (r-l==1) return; 56 m=(l+r)>>1; 57 ll(x,y);rr(x,y); 58 if (a-1<m) 59 insert(ls[x],ls[y],l,m,a,b,c); 60 if (m<a) 61 insert(rs[x],rs[y],m,r,a,b,c); 62 } 63 int subquery(int x,int l,int r,int a,int b) 64 { 65 int m,ans=0; 66 if (x==0) return 0; 67 if ((a<=l)&&(r<=b)) 68 return sub[x].s; 69 m=(l+r)>>1; 70 if (a<m) ans=max(ans,subquery(sub[x].ls,l,m,a,b)); 71 if (m<b) ans=max(ans,subquery(sub[x].rs,m,r,a,b)); 72 return ans; 73 } 74 int query(int x,int l,int r,int a,int b) 75 { 76 int m,ans=0; 77 if (x==0) return 0; 78 if ((a<=l)&&(r<=b)) 79 return subquery(subroot[x],0,n+1,b,n+1); 80 m=(l+r)>>1; 81 if (a<m) ans=max(ans,query(ls[x],l,m,a,b)); 82 if (m<b) ans=max(ans,query(rs[x],m,r,a,b)); 83 return ans; 84 } 85 int main() 86 { 87 scanf("%d%d",&n,&m); 88 for (i=1;i<=n;i++) 89 scanf("%d",&a[i]); 90 for (i=1;i<=n;i++) 91 { 92 f[i].pre=tmp[a[i]]; 93 tmp[a[i]]=i; 94 } 95 for (i=1;i<=n;i++) 96 tmp[i]=n+1; 97 for (i=n;i>=1;i--) 98 { 99 f[i].next=tmp[a[i]]; 100 tmp[a[i]]=i; 101 f[i].idx=i; 102 } 103 sort(f+1,f+1+n,cmp); 104 for (i=1;i<=n;i++) 105 { 106 insert(root[i],root[i-1],0,n,f[i].idx,f[i].next,a[f[i].idx]); 107 } 108 for (i=1;i<=n;i++) 109 e[f[i].pre]=i; 110 for (i=1;i<=n;i++) 111 if (e[i]==0) 112 e[i]=e[i-1]; 113 for (i=1;i<=m;i++) 114 { 115 scanf("%d%d",&u,&v); 116 L=(u+ans)%n+1; 117 R=(v+ans)%n+1; 118 if (L>R) swap(L,R); 119 ans=query(root[e[L-1]],0,n,L-1,R); 120 printf("%d ",ans); 121 } 122 }