题目：https://www.lydsy.com/JudgeOnline/problem.php?id=3489
题解：http://www.itdaan.com/blog/2017/11/24/9bc46b690756fe252e17fc3ca90aa01.html
所以就没写KD-tree、树套堆、分块，而是写了树套树。
限制条件是：pr<L；nt>R；L<= i <=R。
对pr排序后建主席树，调用1~L-1的主席树就能限制好第一个条件；主席树里维护 nt 的值域，调用R+1~n+1的部分就能限制好第二个条件；因为有第三个条件，所以每个点上带一个线段树，维护 i 的位置，记录max值，就行了。
调了半天原来是读入理解错了；1A好高兴。
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int N=1e5+5,M=N*20,M2=M*20; int n,m,tot,tt2,pre[N],rt[N],ans; struct Node{ int pr,i,nt,c; }a[N]; struct Tr{ int ls,rs,rt; }tr[M]; struct T{ int ls,rs,mx; }t[M2]; int rdn() { int ret=0;bool fx=1;char ch=getchar(); while(ch>'9'||ch<'0'){if(ch=='-')fx=0;ch=getchar();} while(ch>='0'&&ch<='9') ret=(ret<<3)+(ret<<1)+ch-'0',ch=getchar(); return fx?ret:-ret; } bool cmpl(Node u,Node v){return u.pr<v.pr;} void insert(int &cr,int pre,int l,int r,Node k) { cr=++tt2; t[cr].ls=t[pre].ls; t[cr].rs=t[pre].rs; t[cr].mx=max(t[pre].mx,k.c); // printf(" bdin: l=%d r=%d mx=%d ",l,r,t[cr].mx); if(l==r) return; int mid=l+r>>1; if(k.i<=mid) insert(t[cr].ls,t[pre].ls,l,mid,k); else insert(t[cr].rs,t[pre].rs,mid+1,r,k); } void build(int &cr,int pre,int l,int r,Node k) { cr=++tot; tr[cr].ls=tr[pre].ls; tr[cr].rs=tr[pre].rs; insert(tr[cr].rt,tr[pre].rt,1,n,k); // printf("bdout: l=%d r=%d rt=%d ",l,r,tr[cr].rt); if(l==r) return; int mid=l+r>>1; if(k.nt<=mid) build(tr[cr].ls,tr[pre].ls,l,mid,k); else build(tr[cr].rs,tr[pre].rs,mid+1,r,k); } int find(int x) { int l=1,r=n,ret=0; while(l<=r) { int mid=l+r>>1; if(a[mid].pr<=x)ret=mid,l=mid+1; else r=mid-1; } return ret; } int query(int cr,int l,int r,int L,int R) { if(!cr) return 0; // printf(" qin: l=%d r=%d(L=%d R=%d) ",l,r,L,R); if(l>=L&&r<=R) return t[cr].mx; int mid=l+r>>1,ret=0; if(L<=mid) ret=query(t[cr].ls,l,mid,L,R); if(mid<R) ret=max(ret,query(t[cr].rs,mid+1,r,L,R)); // printf(" qin: l=%d r=%d ret=%d ",l,r,ret); return ret; } int query(int cr,int l,int r,int L,int R,int ql,int qr) { if(!cr)return 0; // printf("qout: l=%d r=%d rt=%d(L=%d R=%d) ", // l,r,tr[cr].rt,L,R); if(l>=L&&r<=R) return query(tr[cr].rt,1,n,ql,qr); int mid=l+r>>1,ret=0; if(L<=mid) ret=query(tr[cr].ls,l,mid,L,R,ql,qr); if(mid<R) ret=max(ret,query(tr[cr].rs,mid+1,r,L,R,ql,qr)); // printf("qout: l=%d r=%d ret=%d ",l,r,ret); return ret; } int main() { n=rdn(); m=rdn(); for(int i=1,d;i<=n;i++) { d=rdn(); a[i].pr=pre[d]; a[i].i=i; a[i].c=d; pre[d]=i; } for(int i=1;i<=n;i++) pre[i]=n+1; for(int i=n;i;i--) a[i].nt=pre[a[i].c],pre[a[i].c]=i; sort(a+1,a+n+1,cmpl); for(int i=1;i<=n;i++) build(rt[i],rt[i-1],1,n+1,a[i]); for(int i=1,l,r,x,y,k;i<=m;i++) { x=rdn(); y=rdn(); l=min((x+ans)%n+1,(y+ans)%n+1); r=max((x+ans)%n+1,(y+ans)%n+1); k=find(l-1); // printf("st: l=%d r=%d k=%d ",l,r,k); ans=query(rt[k],1,n+1,r+1,n+1,l,r); printf("%d ",ans); } return 0; }