和向左密集比起来向右密集只需要进行小小的额修改，就是更新的时候从右往左更新。。
自己写的被卡死时间。不知道怎么回事，和网上博客的没啥区别。。
/*
给定一个n个数的序列a
每次询问区间[l,r],求出去重后区间中每个数的第一次出现的位置pi
pi构成一个新的升序，求这个新数组的中位数 要求强制在线，询问[l,r]根据上一个询问的答案进行加密，形成新的询问
t1=(l+ansi-1) % mod n + 1
t2=(r+ansi-1) % mod n + 1
l=min(t1,t2),r=max(t1,t2)
然后再进行询问即可 先求出a[i]在序列中上一次出现的位置pre[i]
从左往右进行一次扫描，用主席树来维护区间[1,i]的中不同数字的个数
询问[l,r]：
先求出区间出现的不同数字的个数k，具体操作见SPOJ D-QUERY
要求从左往右第k/2个数，很容易想到二分，在第r棵线段树上询问[mid,r]区间不同数字出现的个数，这样的复杂度是O(q*(logn)^2)
但这种做法是错的。。
出现这种情况是因为我们所有版本的线段树的点都是向后密集的，第i个棵线段树维护a[i]及之前的数最后出现的位置 所以只要每个版本的线段树中不同的数出现的位置能够向前密集，那么这个问题就转变成了求第k大的数
考虑如何将数据向前密集，即保存a[i]下一次出现的位置，扫到a[i]时将i+1，将下一次出现的位置-1即可
update:a[i]
所以从右往左更新主席树,nxt[i]-1,i+1
query:[l,r]
先在第l个版本的线段树上查询[1,r]区间的不同数字的个数l
在第l个版本的线段树上查询[1,r]范围内的第k/2大数的下标 可以发现这种主席树的查询其实退化成了线段树
*/
#include<bits/stdc++.h>
using namespace std;
#define maxn 200005
#define INF 0x3f3f3f3f
struct Node{int lc,rc,sum;}t[maxn*];
int n,a[maxn],rt[maxn],size,nxt[maxn],pos[maxn];
int build(int l,int r){
int now=++size;
t[now].lc=t[now].rc=t[now].sum=;
if(l==r)return now;
int mid=l+r>>;
t[now].lc=build(l,mid);
t[now].rc=build(mid+,r);
return now;
}
int update(int last,int pos,int val,int l,int r){
int now=++size;
t[now]=t[last];t[now].sum+=val;
if(l==r)return now;
int mid=l+r>>;
if(pos<=mid)t[now].lc=update(t[last].lc,pos,val,l,mid);
else t[now].rc=update(t[last].rc,pos,val,mid+,r);
return now;
}
int query1(int rt,int L,int R,int l,int r){//查询区间[L,R]的和
if(L<=l && R>=r)return t[rt].sum;
int mid=l+r>>,res=;
if(L<=mid) res+=query1(t[rt].lc,L,R,l,mid);
if(R>mid)res+=query1(t[rt].rc,L,R,mid+,r);
return res;
}
int query2(int rt,int k,int l,int r){//查询线段树第k大的值
if(l==r)return l;
int mid=l+r>>;
if(k<=t[t[rt].lc].sum)return query2(t[rt].lc,k,l,mid);
else return query2(t[rt].rc,k-t[t[rt].lc].sum,mid+,r);
} int main(){
int T,q;cin>>T;
for(int tt=;tt<=T;tt++){
size=;memset(rt,,sizeof rt);
memset(nxt,0x3f,sizeof nxt);
memset(pos,0x3f,sizeof pos); scanf("%d%d",&n,&q);
for(int i=;i<=n;i++)scanf("%d",&a[i]);
for(int i=n;i>=;i--){
nxt[i]=pos[a[i]];
pos[a[i]]=i;
}
rt[n+]=build(,n);
for(int i=n;i>=;i--){
if(nxt[i]==INF)rt[i]=update(rt[i+],i,,,n);//直接在点i增加1
else {
int tmp=update(rt[i+],nxt[i],-,,n);
rt[i]=update(tmp,i,,,n);
}
} printf("Case #%d:",tt);
int ans=,l,r;
while(q--){
scanf("%d%d",&l,&r);
int t1=(l+ans)%n+,t2=(r+ans)%n+;
l=min(t1,t2),r=max(t1,t2);
int k=query1(rt[l],,r,,n);
ans=query2(rt[l],k/+k%,,n);//求第k个数的下标
printf(" %d",ans);
}
puts("");
}
}
下面的是ac的。。
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<set>
#include<map>
#include<vector>
#include<queue>
using namespace std;
#define ll long long
#define RG register
#define MAX 222222
inline int read()
{
RG int x=,t=;RG char ch=getchar();
while((ch<''||ch>'')&&ch!='-')ch=getchar();
if(ch=='-')t=-,ch=getchar();
while(ch<=''&&ch>='')x=x*+ch-,ch=getchar();
return x*t;
}
int tot,rt[MAX];
struct Node
{
int ls,rs;
int v;
}t[MAX<<];
void Modify(int &x,int ff,int l,int r,int p,int w)
{
t[x=++tot]=t[ff];t[x].v+=w;
if(l==r)return;
int mid=(l+r)>>;
if(p<=mid)Modify(t[x].ls,t[ff].ls,l,mid,p,w);
else Modify(t[x].rs,t[ff].rs,mid+,r,p,w);
}
int Query(int r1,int l,int r,int L,int R)
{
if(L<=l&&r<=R)return t[r1].v;
int mid=(l+r)>>,ret=;
if(L<=mid)ret+=Query(t[r1].ls,l,mid,L,R);
if(R>mid)ret+=Query(t[r1].rs,mid+,r,L,R);
return ret;
}
int Kth(int r1,int l,int r,int K)
{
if(l==r)return l;
int mid=(l+r)>>,s=t[t[r1].ls].v;
if(s>=K)return Kth(t[r1].ls,l,mid,K);
else return Kth(t[r1].rs,mid+,r,K-s);
}
int ans,n,a[MAX],m;
int lst[MAX],pos[MAX];
int main()
{
int T=read();
for(int TTT=;TTT<=T;++TTT)
{
printf("Case #%d:",TTT);
memset(rt,,sizeof(rt));
memset(t,,sizeof(t));
memset(lst,,sizeof(lst));
memset(pos,,sizeof(pos));
tot=ans=;
n=read();m=read();
for(int i=;i<=n;++i)a[i]=read();
for(int i=n;i;--i)
if(!pos[a[i]])Modify(rt[i],rt[i+],,n,i,),pos[a[i]]=i;
else
{
Modify(rt[i],rt[i+],,n,i,);
Modify(rt[i],rt[i],,n,pos[a[i]],-);
pos[a[i]]=i;
}
while(m--)
{
int L=(read()+ans)%n+,R=(read()+ans)%n+;
if(L>R)swap(L,R);
int S=Query(rt[L],,n,L,R);
ans=Kth(rt[L],,n,(S+)/);
printf(" %d",ans);
}
puts("");
}
return ;
}