https://www.zybuluo.com/ysner/note/1298153
题面
给出一个长度为(n)的序列，给出(M)个询问：
在([l,r])之间找到一个在这个区间里只出现过一次的数，并且要求找的这个数尽可能大。
如果找不到这样的数，则直接输出(0)。我会采取一些措施强制在线。
- (nleq10^5,mleq2*10^5,a_ileq n)
解析
只出现过一次，就是上一次出现在位置(l)之前，下一次出现在位置(r)之后。
这个有点像三维偏序，但这里有一维是区间啊。
树套树续一下应该能过。
然而，对于维数较高的范围计数问题，(kd-tree)是更佳选择。
其复杂度稳定(O(kn^{1-frac{1}{k}}))（(k)为维数），而且空间线性。
一般框架：
- 如果当前节点存的点被询问范围包括,用这个点贡献答案
- 如果当前节点的范围完全被询问范围包括,直接用整个节点贡献答案
- 如果当前节点的范围(一个超立方体)和询问范围没有交,返回
- 否则,递归进入左右儿子
对一个新加入的点，先自己更新自己的范围，再用儿子更新自己的范围。
把上一次，这一次，下一次这个数出现的位置看作三个维度就可以了。
#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#define ll long long
#define re register
#define il inline
#define ls t[k].l
#define rs t[k].r
#define fp(i,a,b) for(re int i=a;i<=b;i++)
#define fq(i,a,b) for(re int i=a;i>=b;i--)
using namespace std;
const int N=2e5+100;
int n,m,b[N],R[N],L[N],now,app[N],rt,ans;
il ll gi()
{
re ll x=0,t=1;
re char ch=getchar();
while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
if(ch=='-') t=-1,ch=getchar();
while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
return x*t;
}
il void cmin(re int &x,re int y){x=min(x,y);}
il void cmax(re int &x,re int y){x=max(x,y);}
struct dat
{
int d[3],w,max;
il bool operator < (const dat &o) const{return d[now]<o.d[now];}
}a[N];
struct node
{
dat a;
int l,r,mn[3],mx[3];
}t[N];
struct kd_tree
{
il void upd(re int k,re int p)
{
fp(i,0,2) cmin(t[k].mn[i],t[p].mn[i]),cmax(t[k].mx[i],t[p].mx[i]);
t[k].a.max=max(t[k].a.max,t[p].a.max);
}
il void pushup(re int k)
{
fp(i,0,2) t[k].mn[i]=t[k].mx[i]=t[k].a.d[i];
if(ls) upd(k,ls);if(rs) upd(k,rs);
}
il void Build(re int &k,re int l,re int r,re int tag)
{
re int mid=l+r>>1;now=tag;
nth_element(a+l,a+mid,a+r+1);k=mid;
t[k].a=a[mid];
if(l<mid) Build(ls,l,mid-1,(tag+1)%3);else ls=0;
if(mid<r) Build(rs,mid+1,r,(tag+2)%3);else rs=0;
pushup(k);
}
il void Query(re int k,re int l,re int r)
{
if(!k||t[k].a.max<ans) return;
if(t[k].a.d[1]>=l&&t[k].a.d[1]<=r&&t[k].a.d[0]<l&&t[k].a.d[2]>r) ans=max(ans,t[k].a.w);
if(t[k].mn[1]>=l&&t[k].mx[1]<=r&&t[k].mx[0]<l&&t[k].mn[2]>r) ans=max(ans,t[k].a.max);
if(t[k].mn[1]>r||t[k].mx[1]<l||t[k].mn[0]>=l||t[k].mx[2]<=r) return;
Query(ls,l,r);Query(rs,l,r);
}
}kd;
int main()
{
n=gi();m=gi();
fp(i,1,n) b[i]=gi(),L[i]=app[b[i]],app[b[i]]=i,R[i]=n+1;
fp(i,0,n) app[i]=n+1;
fq(i,n,1) R[i]=app[b[i]],app[b[i]]=i;
fp(i,1,n) a[i].d[0]=L[i],a[i].d[1]=i,a[i].d[2]=R[i],a[i].max=a[i].w=b[i];
kd.Build(rt,1,n,0);
while(m--)
{
re int l=gi(),r=gi();
l=(l+ans)%n+1,r=(r+ans)%n+1;
if(l>r) swap(l,r);
ans=0;kd.Query(rt,l,r);
printf("%d
",ans);
}
return 0;
}