题目链接：https://www.lydsy.com/JudgeOnline/problem.php?id=3489
题意概述：
给出一个序列，每次询问一个序列区间中仅出现了一次的数字最大是多少，如果没有的话输出0。
N<=100000,M<=200000.
分析：
考试的时候YY了一个可持久化KDtree可惜没有打完（一开始想着一维做最后发现自己真是太天真了hahahaha），最后把它改对了。
把两种方法都介绍一下：
持久化KDtree：
首先我们令last[i]表示A[i]在i的左边最靠右的出现位置，那么显然对于询问[l,r]，如果我们当前计算出的last是基于[1,r]的数据的，那么我们要找的实际上是(last[A[i]],i]中包含l的最大的A[i]，转化一下就变成了last[A[i]]<l<=i，如果我们把它做成平面上的点(i,last[A[i]])，权值为A[i]，并且序列中每个值仅有最后一次出现的位置对应的i做成的点有值，我们每一次询问[l,r]实际上询问的是基于[1,r]中的信息做成的点在平面范围{ (x,y) | x>=i,y<l }的点中的最大权值，这可以用KDtree来做。
因此我们只要先把所有的点预处理出来建成KDtree，修改的时候可持久化一下就可以了。（如果您执意认为三维KDtree更好的话我只能说它太容易被卡啦......）
期望时间复杂度O((N+M)sqrt(N))
二维线段树：
我们令Last[i]表示i左边第一个和i权值相同的点的下标（没有的话为0），Next[i]表示i右边第一个和i权值相同的点的下标（没有的话为N+1），那么对于询问[l,r]满足Last[i]<l<=i,i<=r<Next[i]来说，A[i]就可能成为它的解，可以发现我们把l当成平面的横坐标，r当成平面的纵坐标，i可以影响到的区域正好是平面上的一个矩形！因此只要用二维线段树动态开点+标记永久化就可以做了。
时间复杂度O(M*logN^2)
这两种做法的话，随机数据KDtree0.4s+吊打二维线段树2.8s+，而把询问构造成几乎全部接近于单点询问的时候KDtree到了极限大概3.6s的样子，这个时候二维线段树很开心1.8s+，三维KDtree就更不要说了5s+......（4s的时限干不死我的KDtreehahahahahaha如果您卡掉了我请不要怼我）
最后，我发现数据结构这种东西不同结构体写常数会小一些，尤其是当需要卡极限的时候不写在结构体里面效果就很显著......还有为什么把变量ans当成参数带到query里面去居然变快了？！是引用地址的原因吗......
论常数优化的重要性！
KDtree：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<queue>
#include<set>
#include<map>
#include<vector>
#include<cctype>
#define inf (1e8+5)
using namespace std;
const int MAXN=;
const int maxn=;
const int maxm=; int N,M,A[MAXN],last[MAXN],cnt,D;
struct XY{
int d[];
friend bool operator < (XY a,XY b){
return a.d[D]<b.d[D];
}
friend bool operator == (XY a,XY b){
return a.d[]==b.d[]&&a.d[]==b.d[];
}
}p[MAXN],pp[MAXN],node[maxn],mn[maxn],mx[maxn];
int root[maxm],np,lc[maxn],rc[maxn],maxv[maxn],w[maxn],ver[maxn];
int copynode(int p,int t){
np++,maxv[np]=maxv[p],w[np]=w[p];
lc[np]=lc[p],rc[np]=rc[p],ver[np]=t;
node[np]=node[p],mx[np]=mx[p],mn[np]=mn[p];
return np;
}
void pushup1(int now){
for(int i=;i<;i++){
mn[now].d[i]=min(node[now].d[i],min(mn[lc[now]].d[i],mn[rc[now]].d[i]));
mx[now].d[i]=max(node[now].d[i],max(mx[lc[now]].d[i],mx[rc[now]].d[i]));
}
}
void pushup2(int now){
maxv[now]=max(w[now],max(maxv[lc[now]],maxv[rc[now]]));
}
void build(int &now,int L,int R,XY *a,int k){
if(L>R) return;
now=++np,lc[now]=rc[now]=;
int m=L+R>>; D=k;
nth_element(a+L,a+m,a+R+);
node[now]=mx[now]=mn[now]=a[m];
maxv[now]=w[now]=;
build(lc[now],L,m-,a,k^);
build(rc[now],m+,R,a,k^);
pushup1(now);
}
bool isoutside(XY p,int now){
return p.d[]<mn[now].d[]||p.d[]>mx[now].d[]
||p.d[]<mn[now].d[]||p.d[]>mx[now].d[];
}
int update(int now,XY p,int v,int t){
if(!now) return ;
if(isoutside(p,now)) return ;
if(node[now]==p){
if(ver[now]!=t) now=copynode(now,t);
w[now]=v; pushup2(now);
return now;
}
int re=;
if(re=update(lc[now],p,v,t)){
if(ver[now]!=t) now=copynode(now,t);
lc[now]=re; pushup2(now);
return now;
}
if(re=update(rc[now],p,v,t)){
if(ver[now]!=t) now=copynode(now,t);
rc[now]=re; pushup2(now);
return now;
}
return ;
}
void query(int now,int l,int &ret){
if(mx[now].d[]<l||mn[now].d[]>=l) return;
if(mn[now].d[]>=l&&mx[now].d[]<l){
if(maxv[now]>ret) ret=maxv[now];
return;
}
if(node[now].d[]>=l&&node[now].d[]<l&&w[now]>ret) ret=w[now];
if(maxv[lc[now]]>ret) query(lc[now],l,ret);
if(maxv[rc[now]]>ret) query(rc[now],l,ret);
} void _scanf(int &x)
{
x=;
char ch=getchar();
while(ch<''||ch>'') ch=getchar();
while(ch>=''&&ch<='') x=x*+ch-'',ch=getchar();
}
int out_cnt; char out[];
void _printf(int x)
{
out[++out_cnt]=x%+'',x/=;
while(x) out[++out_cnt]=x%+'',x/=;
while(out_cnt) putchar(out[out_cnt--]);
putchar('\n');
}
void data_in()
{
_scanf(N);_scanf(M);
for(int i=;i<=N;i++) _scanf(A[i]);
for(int i=;i<=N;i++){
p[i].d[]=i,p[i].d[]=last[A[i]];
last[A[i]]=i;
}
for(int i=;i<=N;i++) pp[i]=p[i];
mx[].d[]=mx[].d[]=,mn[].d[]=mn[].d[]=inf;
build(root[],,N,p,);
for(int i=;i<=N;i++){
root[i]=root[i-];
if(pp[i].d[]) root[i]=update(root[i],pp[pp[i].d[]],,i);
root[i]=update(root[i],pp[i],A[i],i);
}
}
void work()
{
int l,r,x,y,ans;
for(int i=;i<=M;i++){
_scanf(x);_scanf(y);
l=min((x+ans)%N+,(y+ans)%N+);
r=max((x+ans)%N+,(y+ans)%N+);
ans=; query(root[r],l,ans);
_printf(ans);
}
}
int main()
{
data_in();
work();
return ;
}
二维线段树：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<queue>
#include<set>
#include<map>
#include<vector>
#include<cctype>
using namespace std;
const int maxn=;
const int maxnode=; int N,M,a[maxn],Last[maxn],Next[maxn],last[maxn];
int root,np,rt[maxnode],lc[maxnode],rc[maxnode],mx[maxnode];
void inupdate(int &now,int L,int R,int A,int B,int v){
if(!now) now=++np;
if(A<=L&&R<=B){
if(v>mx[now]) mx[now]=v;
return;
}
int m=L+R>>;
if(B<=m) inupdate(lc[now],L,m,A,B,v);
else if(A>m) inupdate(rc[now],m+,R,A,B,v);
else inupdate(lc[now],L,m,A,B,v),inupdate(rc[now],m+,R,A,B,v);
}
int inquery(int now,int L,int R,int p){
if(!now) return ;
if(L==R) return mx[now];
int m=L+R>>;
if(p<=m) return max(mx[now],inquery(lc[now],L,m,p));
return max(mx[now],inquery(rc[now],m+,R,p));
}
void update(int &now,int L,int R,int A,int B,int AA,int BB,int v){
if(!now) now=++np;
if(A<=L&&R<=B){
inupdate(rt[now],,N,AA,BB,v);
return;
}
int m=L+R>>;
if(B<=m) update(lc[now],L,m,A,B,AA,BB,v);
else if(A>m) update(rc[now],m+,R,A,B,AA,BB,v);
else update(lc[now],L,m,A,B,AA,BB,v),update(rc[now],m+,R,A,B,AA,BB,v);
}
int query(int now,int L,int R,int p1,int p2){
if(!now) return ;
if(L==R) return inquery(rt[now],,N,p2);
int m=L+R>>;
int re=inquery(rt[now],,N,p2);
if(p1<=m) return max(re,query(lc[now],L,m,p1,p2));
return max(re,query(rc[now],m+,R,p1,p2));
} void _scanf(int &x)
{
x=;
char ch=getchar();
while(ch<''||ch>'') ch=getchar();
while(ch>=''&&ch<='') x=x*+ch-'',ch=getchar();
}
int out_cnt; char out[];
void _printf(int x)
{
out[++out_cnt]=x%+'',x/=;
while(x) out[++out_cnt]=x%+'',x/=;
while(out_cnt) putchar(out[out_cnt--]);
putchar('\n');
}
void data_in()
{
_scanf(N);_scanf(M);
for(int i=;i<=N;i++) _scanf(a[i]);
for(int i=;i<=N;i++)
Last[i]=last[a[i]],last[a[i]]=i;
for(int i=;i<=N;i++) last[i]=N+;
for(int i=N;i>=;i--)
Next[i]=last[a[i]],last[a[i]]=i;
for(int i=;i<=N;i++)
update(root,,N,Last[i]+,i,i,Next[i]-,a[i]);
}
void work()
{
int x,y,l,r,ans=;
for(int i=;i<=M;i++){
_scanf(x);_scanf(y);
l=min((x+ans)%N+,(y+ans)%N+);
r=max((x+ans)%N+,(y+ans)%N+);
ans=query(root,,N,l,r);
_printf(ans);
}
}
int main()
{
data_in();
work();
return ;
}