Description
因为是OJ上的题，就简单点好了。给出一个长度为n的序列，给出M个询问：在[l,r]之间找到一个在这个区间里只出现过一次的数，并且要求找的这个数尽可能大。如果找不到这样的数，则直接输出0。我会采取一些措施强制在线。
Input
第一行为两个整数N,M。M是询问数，N是序列的长度（N<=100000，M<=200000)
第二行为N个整数，描述这个序列{ai}，其中所有1<=ai<=N
再下面M行，每行两个整数x，y，
询问区间[l,r]由下列规则产生（OIER都知道是怎样的吧>_<)：
l=min(（x+lastans)mod n+1,(y+lastans）mod n+1);
r=max(（x+lastans)mod n+1,(y+lastans）mod n+1);
Lastans表示上一个询问的答案，一开始lastans为0
Output
一共M行，每行给出每个询问的答案。
Sample Input
10 10
6 4 9 10 9 10 9 4 10 4
3 8
10 1
3 4
9 4
8 1
7 8
2 9
1 1
7 3
9 9
6 4 9 10 9 10 9 4 10 4
3 8
10 1
3 4
9 4
8 1
7 8
2 9
1 1
7 3
9 9
Sample Output
4
10
10
0
0
10
0
4
0
4
10
10
0
0
10
0
4
0
4
HINT
注意出题人为了方便，input的第二行最后多了个空格。
2015.6.24新加数据一组，2016.7.9放至40S,600M,但未重测
一开始不是很会做，看了一下路牌
KD-tree？？？好吧考虑不用高级数据结构用这个大暴力
首先转化下模型：pre[i]，next[i]分别表示第i位的数上一次和下面出现的位置
那问题就转化为求pre[i]<l&&next[i]>r&&在这段位置中的点的最大权值
然后跑KD-tree，加几个优化就过了感觉写这东西很顺手
//MT_LI #include<cmath> #include<cstdio> #include<cstdlib> #include<cstring> #include<algorithm> using namespace std; struct KDT{ int lc,rc,d[4],mn[4],mx[4]; }tr[410000]; int pre[410000],next[410000]; void update(int x) { int lc=tr[x].lc,rc=tr[x].rc; if(lc) { for(int i=0;i<=3;i++)tr[x].mn[i]=min(tr[x].mn[i],tr[lc].mn[i]); for(int i=0;i<=3;i++)tr[x].mx[i]=max(tr[x].mx[i],tr[lc].mx[i]); } if(rc) { for(int i=0;i<=3;i++)tr[x].mn[i]=min(tr[x].mn[i],tr[rc].mn[i]); for(int i=0;i<=3;i++)tr[x].mx[i]=max(tr[x].mx[i],tr[rc].mx[i]); } } int cmpd; bool cmp(KDT a,KDT b){return a.d[cmpd]<b.d[cmpd];} int build(int l,int r,int d) { int mid=(l+r)/2,now;cmpd=d;now=mid; nth_element(tr+l,tr+mid,tr+r+1,cmp); for(int i=0;i<=3;i++)tr[now].mn[i]=tr[now].mx[i]=tr[now].d[i]; if(l<mid)tr[now].lc=build(l,mid-1,d%3+1); if(mid<r)tr[now].rc=build(mid+1,r,d%3+1); update(now); return now; } int a[410000],pos[410000]; int ans=0; int n,m; void find(int x,int l,int r) { int lc=tr[x].lc,rc=tr[x].rc; if(tr[x].mx[0]<l&&tr[x].mn[1]>r&&tr[x].mn[2]>=l&&tr[x].mx[2]<=r) { ans=max(ans,tr[x].mx[3]); return ; } ans=max(ans,(tr[x].d[0]<l&&tr[x].d[1]>r&&l<=tr[x].d[2]&&tr[x].d[2]<=r)?tr[x].d[3]:0); if(tr[lc].mx[3]>tr[rc].mx[3]) { if((tr[lc].mn[0]<l&&tr[lc].mx[1]>r)&&tr[lc].mx[3]>ans&&(tr[lc].mx[2]>=l&&tr[lc].mn[2]<=r))find(lc,l,r); if((tr[rc].mn[0]<l&&tr[rc].mx[1]>r)&&tr[rc].mx[3]>ans&&(tr[rc].mx[2]>=l&&tr[rc].mn[2]<=r))find(rc,l,r); } else { if((tr[rc].mn[0]<l&&tr[rc].mx[1]>r)&&tr[rc].mx[3]>ans&&(tr[rc].mx[2]>=l&&tr[rc].mn[2]<=r))find(rc,l,r); if((tr[lc].mn[0]<l&&tr[lc].mx[1]>r)&&tr[lc].mx[3]>ans&&(tr[lc].mx[2]>=l&&tr[lc].mn[2]<=r))find(lc,l,r); } } int main() { scanf("%d%d",&n,&m); for(int i=1;i<=n;i++)scanf("%d",&a[i]); for(int i=1;i<=n;i++) { pre[i]=pos[a[i]]; next[pos[a[i]]]=i; pos[a[i]]=i; } pre[1]=0; for(int i=1;i<=n;i++)if(!next[i])next[i]=n+1; int root; for(int i=1;i<=n;i++)tr[i].d[3]=a[i],tr[i].d[0]=pre[i],tr[i].d[1]=next[i],tr[i].d[2]=i; root=build(1,n,0); while(m--) { int x,y,l,r; scanf("%d%d",&x,&y); l=min((x+ans)%n+1,(y+ans)%n+1); r=max((x+ans)%n+1,(y+ans)%n+1); ans=0;find(root,l,r); printf("%d ",ans); } return 0; }