本文共 3726 字，大约阅读时间需要 12 分钟。

Mr. Frog has an integer sequence of length n, which can be denoted as a1,a2,⋯,ana1,a2,⋯,an There are m queries.

In the i-th query, you are given two integers lili and riri. Consider the subsequence ali,ali+1,ali+2,⋯,ariali,ali+1,ali+2,⋯,ari.

We can denote the positions(the positions according to the original sequence) where an integer appears first in this subsequence as p(i)1,p(i)2,⋯,p(i)kip1(i),p2(i),⋯,pki(i) (in ascending order, i.e.,p(i)1<p(i)2<⋯<p(i)kip1(i)<p2(i)<⋯<pki(i)).

Note that kiki is the number of different integers in this subsequence. You should output p(i)⌈ki2⌉p⌈ki2⌉(i)for the i-th query.

Input In the first line of input, there is an integer T (T≤2T≤2) denoting the number of test cases.

Each test case starts with two integers n (n≤2×105n≤2×105) and m (m≤2×105m≤2×105). There are n integers in the next line, which indicate the integers in the sequence(i.e., a1,a2,⋯,an,0≤ai≤2×105a1,a2,⋯,an,0≤ai≤2×105).

There are two integers lili and riri in the following m lines.

However, Mr. Frog thought that this problem was too young too simple so he became angry. He modified each query to l‘i,r‘i(1≤l‘i≤n,1≤r‘i≤n)li‘,ri‘(1≤li‘≤n,1≤ri‘≤n). As a result, the problem became more exciting.

We can denote the answers as ans1,ans2,⋯,ansmans1,ans2,⋯,ansm. Note that for each test case ans0=0ans0=0.

You can get the correct input li,rili,ri from what you read (we denote them as l‘i,r‘ili‘,ri‘)by the following formula:

li=min{(l‘i+ansi−1) mod n+1,(r‘i+ansi−1) mod n+1} li=min{(li‘+ansi−1) mod n+1,(ri‘+ansi−1) mod n+1}

ri=max{(l‘i+ansi−1) mod n+1,(r‘i+ansi−1) mod n+1}

ri=max{(li‘+ansi−1) mod n+1,(ri‘+ansi−1) mod n+1} Output You should output one single line for each test case.

For each test case, output one line “Case #x: p1,p2,⋯,pmp1,p2,⋯,pm”, where x is the case number (starting from 1) and p1,p2,⋯,pmp1,p2,⋯,pm is the answer.

Sample Input 2 5 2 3 3 1 5 4 2 2 4 4 5 2 2 5 2 1 2 2 3 2 4 Sample Output Case #1: 3 3 Case #2: 3 1 题意：长度为n的序列和m次询问，每次询问是l到r之间按每个数第一次出现的位置排序，问中位数的位置是什么。 思路：因为我们要记录每个数第一次出现的位置。之前bzoj有一个类似的题， 但是这个题需要记录第一次出现的位置，所以我们要从后往前遍历数组，如果之前出现过，就将之前的位置清空，在当前位置记录下来。这个操作在主席树里操作。对于l~r，我们可以算出来这段区间里有多少个数，然后就在转化成了求区间l ~r内第k个数的位置。 代码如下：

#include
   
    #define ll long longusing namespace std;const int maxx=2e5+100;struct node{
   	int l;	int r;	int sum;}p[maxx*40];int a[maxx];int n,m,tot,root[maxx];inline int build(int l,int r){
   	int cur=++tot;	p[cur].sum=0;	if(l==r) return cur;	int mid=l+r>>1;	p[cur].l=build(l,mid);	p[cur].r=build(mid+1,r);	return cur;}inline int update(int rot,int l,int r,int pos,int v){
   	int cur=++tot;	p[cur]=p[rot];	p[cur].sum+=v;	if(l==r) return cur;	int mid=l+r>>1;	if(pos<=mid) p[cur].l=update(p[rot].l,l,mid,pos,v);	else p[cur].r=update(p[rot].r,mid+1,r,pos,v);	return cur;}inline int queryI(int rot,int l,int r,int L,int R)//求区间l~r的数字种类数{
   	if(l<=L&&R<=r) return p[rot].sum;	int mid=L+R>>1;	int sum=0;	if(l<=mid) sum+=queryI(p[rot].l,l,r,L,mid);	if(mid
    
     >1;	if(num<=ret) return queryII(p[rot].l,L,mid,num);	else return queryII(p[rot].r,mid+1,R,num-ret);}int main(){
   	int t,k=0,l,r;	scanf("%d",&t);	while(t--)	{
   		tot=0;		scanf("%d%d",&n,&m);		map
     
       mp;		for(int i=1;i<=n;i++) scanf("%d",&a[i]);		root[n+1]=build(1,n);		for(int i=n;i>=1;i--)		{
   			if(mp.find(a[i])==mp.end()) root[i]=update(root[i+1],1,n,i,1);			else			{
   				int x=update(root[i+1],1,n,mp[a[i]],-1);//x是将之前标记消了的版本，第i个版本在x的基础上建立起来				root[i]=update(x,1,n,i,1);			}			mp[a[i]]=i;		}		printf("Case #%d:",++k);		int ans=0;		while(m--)		{
   			scanf("%d%d",&l,&r);			l=(l+ans)%n+1;			r=(r+ans)%n+1;			if(l>r) swap(l,r);			int kk=(queryI(root[l],l,r,1,n)+1)>>1;			ans=queryII(root[l],1,n,kk);			printf(" %d",ans);		}		printf("\n");	}	return 0;}
     
    
   

努力加油a啊，(^o)/~

转载地址：http://iktvi.baihongyu.com/