bzoj3489 -- 可持久化树套树

令 lasti 表示 ai 前一个出现的位置（没出现过为 0 ）， nexti 表示 ai 后一个出现的位置（没出现过为 n+1 ）。
那么要满足的条件是： lasti<l,nexti>r,l≤i≤r
将 ai 按 lasti 排序，对 nexti 建一棵主席树，每一个节点存一个线段树记录区间内 ai 的最大值。
更新时先更新主席树上的一条链，然后更新链上每个节点存的线段树的一条链。
查询时先二分出 k ，使 lastk<l≤lastk+1 ，然后在主席树第 k 个状态下查询就可以了。
时间复杂度 O(mlog2n) ，空间复杂度 O(nlog2n)

代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define N 100010
inline char nc(){
static char buf[100000],*p1=buf,*p2=buf;
if(p1==p2){
        p2=(p1=buf)+fread(buf,1,100000,stdin);
if(p1==p2)return EOF;
    }
return *p1++;
}
inline void Read(int& x){
char c=nc(),b=1;
for(;c<'0'||c>'9';c=nc())if(c=='-')b=-1;
for(x=0;c>='0'&&c<='9';x=(x<<3)+(x<<1)+c-48,c=nc());x*=b;
}
struct A{
int Last,Next,w,f;
}a[N];
struct Node{
int l,r,w;
}c[N*500];
int Rt[N],i,j,k,n,m,p,f[N],x,y,Cnt,Ans;
inline int Max(int x,int y){
return x<y?y:x;
}
inline int Min(int x,int y){
return x<y?x:y;
}
inline bool Cmp(A a,A b){
return a.Last<b.Last;
}
inline void Update(int& x,int A,int l,int r,int y,int z){
    x=++Cnt;c[x]=c[A];
if(l==r){
        c[x].w=z;
return;
    }
int Mid=l+r>>1;
if(y<=Mid)Update(c[x].l,c[A].l,l,Mid,y,z);else Update(c[x].r,c[A].r,Mid+1,r,y,z);
    c[x].w=Max(c[c[x].l].w,c[c[x].r].w);
}
inline void Insert(int& x,int y,int l,int r,int b,int z,int a){
    x=++Cnt;c[x]=c[y];
    Update(c[x].w,c[x].w,1,n,z,a);
if(l==r)return;
int Mid=l+r>>1;
if(b<=Mid)Insert(c[x].l,c[y].l,l,Mid,b,z,a);else Insert(c[x].r,c[y].r,Mid+1,r,b,z,a);
}
inline int Find(int x){
int l=1,r=n,Mid,Ans=0;
while(l<=r){
        Mid=l+r>>1;
if(a[Mid].Last<x)Ans=Mid,l=Mid+1;else r=Mid-1;
    }
return Ans;
}
inline int Query2(int x,int l,int r,int L,int R){
if(!x||l>R||r<L)return 0;
if(l>=L&&r<=R)return c[x].w;
int Mid=l+r>>1;
return Max(Query2(c[x].l,l,Mid,L,R),Query2(c[x].r,Mid+1,r,L,R));
}
inline int Query1(int x,int l,int r,int L,int R,int y,int z){
if(!x||l>R||r<L)return 0;
if(l>=L&&r<=R)return Query2(c[x].w,1,n,y,z);
int Mid=l+r>>1;
return Max(Query1(c[x].l,l,Mid,L,R,y,z),Query1(c[x].r,Mid+1,r,L,R,y,z));
}
int main(){
    Read(n);Read(m);
for(i=1;i<=n;i++)Read(a[i].w),a[i].f=i,a[i].Last=f[a[i].w],f[a[i].w]=i;
for(i=1;i<=n;i++)f[i]=n+1;
for(i=n;i;i--)a[i].Next=f[a[i].w],f[a[i].w]=i;
    sort(a+1,a+n+1,Cmp);
for(i=1;i<=n;i++)Insert(Rt[i],Rt[i-1],1,n+1,a[i].Next,a[i].f,a[i].w);
while(m--){
        Read(x);Read(y);
        k=x;x=Min((x+Ans)%n+1,(y+Ans)%n+1);
        y=Max((k+Ans)%n+1,(y+Ans)%n+1);
        k=Find(x);
if(!k)Ans=0;else Ans=Query1(Rt[k],1,n+1,y+1,n+1,x,y);
printf("%d\n",Ans);
    }
return 0;
}