记录编号	251118	评测结果	WWWWWWWWWWWWWWWWWWWW
题目名称	数字查询	最终得分	0
用户昵称	咸鱼二号	是否通过	未通过
代码语言	C++	运行时间	6.017 s
提交时间	2016-04-16 21:38:34	内存使用	65.33 MiB

#include<iostream>
#include<cstring>
#include<cstdio>
#include<string>
#include<algorithm>
#include<cmath>
#include<utility>
#include<cstdlib>
#include<iomanip>	//cout<<setiosflags(ios::fixed)<<setprecision(2);
#include<ctime> //double a=(double)clock();	cout<<a<<endl;
#include<vector>
#include<queue>
using namespace std;
const int maxn=40010;
inline int read(){
	int x=0,ff=1;char ch=getchar();
	while(ch>'9'||ch<'0'){if(ch=='-')ff=-1; ch=getchar();}
	while(ch<='9'&&ch>='0'){x=x*10+ch-'0';ch=getchar();}
	return ff*x;
}
inline int mymin(int xx,int yy)
{if(xx<yy)return xx;return yy;}
inline int mymax(int xx,int yy)
{if(xx<yy)return yy;return xx;}
inline void myswap(int &xx,int &yy)
{xx^=yy,yy^=xx,xx^=yy;}
int N,M,cnt=0,len=200,block,L,R,x=0,maxx,now,k;
int a[maxn],s[210][40010],ans[210][40010],vis[40010],p[40010],check[40010],tim;
struct stru{
	int id,v;
}c[maxn];
inline bool mycmp1(const stru &A,const stru &B)
{return A.id<B.id;}
inline bool mycmp2(const stru &A,const stru &B)
{return A.v<B.v;}
void pre(){
	//len=(int)sqrt(1.0*N);
	k=N/len;
	if(N%len)k++;
	for(int i=1;i<=k;i++){
		for(int j=1;j<=cnt;j++)
			s[i][j]=s[i-1][j];
		L=(i-1)*len+1,R=mymin(i*len,N);
		for(int j=L;j<=R;j++)
			s[i][c[j].v]++;
	}
	for(int i=1;i<=k;i++){
		memset(vis,0,sizeof(vis));
		maxx=0,now=cnt+1;
		for(int j=i;j<=k;j++){
			L=(j-1)*len+1,R=mymin(i*len,N);
			for(int o=L;o<=R;o++){
				vis[c[o].v]++;
				if(vis[c[o].v]>maxx||(vis[c[o].v]==maxx&&c[o].v<now))
					maxx=vis[c[o].v],now=c[o].v;
			}
			ans[i][j]=now;
		}
	}
}
void query(int X,int Y){
	int A=(X-1)/len+1,B=(Y-1)/len+1;
	tim++;
	if(A==B||A==B-1){
		maxx=0,now=cnt+1;
		for(int i=X;i<=Y;i++){
			if(check[c[i].v]!=tim)check[c[i].v]=tim,vis[c[i].v]=0;
			vis[c[i].v]++;
			if(vis[c[i].v]>maxx||(vis[c[i].v]==maxx&&now>c[i].v))
				maxx=vis[c[i].v],now=c[i].v;
		}
	}
	else{
		now=ans[A+1][B-1];
		maxx=s[B-1][now]-s[A][now];//不计算L和R
		L=A*len,R=(B-1)*len+1;
		for(int i=X;i<=L;i++){
			if(check[c[i].v]!=tim)check[c[i].v]=tim,vis[c[i].v]=0;
			vis[c[i].v]++;
		}
		for(int i=R;i<=Y;i++){
			if(check[c[i].v]!=tim)check[c[i].v]=tim,vis[c[i].v]=0;
			vis[c[i].v]++;
		}
		for(int i=X;i<=L;i++){
			int cur=vis[c[i].v]+s[B-1][c[i].v]-s[A][c[i].v];
			if(cur>maxx||(cur==maxx&&now>c[i].v))
				maxx=cur,now=c[i].v;
		}
		for(int i=R;i<=Y;i++){
			int cur=vis[c[i].v]+s[B-1][c[i].v]-s[A][c[i].v];
			if(cur>maxx||(cur==maxx&&now>c[i].v))
				maxx=cur,now=c[i].v;
		}
	}
	x=p[c[now].v];
	printf("%d\n",x);
}
int main(){
	freopen("numquery.in","r",stdin);
	freopen("numquery.out","w",stdout);
	N=read(),M=read();
	for(int i=1;i<=N;i++)
		c[i].v=a[i]=read(),c[i].id=i;
	sort(c+1,c+1+N,mycmp2);
	for(int i=1;i<=N;i++){
		if(c[i].v!=c[i-1].v)
			c[i].v=++cnt;
		else c[i].v=cnt;
		p[cnt]=c[i].v;
	}
	sort(c+1,c+1+N,mycmp1);
	pre();
	while(M--){
		L=read(),R=read();
		L=(L+x-1)%N+1,R=(R+x-1)%N+1;
		if(L>R)
			myswap(L,R);
		query(L,R);
	}
	return 0;
}