记录编号	250662	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	数字查询	最终得分	100
用户昵称	Aglove	是否通过	通过
代码语言	C++	运行时间	1.992 s
提交时间	2016-04-15 16:55:16	内存使用	33.60 MiB

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<cmath>
using namespace std;
 
const int maxn=40010;
int n,m,cnt,u,v,blo,k,Ans;
int a[maxn],p[maxn];
int pos[maxn],vis[maxn];
int check[maxn],tim;
int ans[210][210];
int S[210][maxn];
struct Num{
	int v,id;
}c[maxn];
 
bool cmpv(const Num &A,const Num &B){return A.v<B.v;}
bool cmpid(const Num &A,const Num &B){return A.id<B.id;}
void read(int &num){
	num=0;char ch=getchar();
	while(ch<'!')ch=getchar();
	while(ch>='0'&&ch<='9')num=num*10+ch-'0',ch=getchar();
}
void Get_Pre(){
	for(int i=1;i<=k;++i){
		memset(vis,0,sizeof(vis));
		int mx=0,now=cnt+1;
		for(int j=i;j<=k;++j){
			int L=(j-1)*blo+1,R=min(j*blo,n);
			for(int o=L;o<=R;++o){
				vis[c[o].v]++;
				if(vis[c[o].v]>mx||(vis[c[o].v]==mx&&c[o].v<now)){
					mx=vis[c[o].v];now=c[o].v;
				}
			}ans[i][j]=now;
		}
	}
	for(int i=1;i<=k;++i){
		for(int j=1;j<=cnt;++j)S[i][j]=S[i-1][j];
		int L=(i-1)*blo+1,R=min(i*blo,n);
		for(int j=L;j<=R;++j)S[i][c[j].v]++;
	}return;
}
void Get_ans(int a,int b){
	int u=pos[a],v=pos[b];
	tim++;
	if(u==v||u+1==v){
		int mx=0,now=cnt+1;
		for(int i=a;i<=b;++i){
			if(check[c[i].v]!=tim)check[c[i].v]=tim,vis[c[i].v]=0;
			vis[c[i].v]++;
			if(mx<vis[c[i].v]||(mx==vis[c[i].v]&&now>c[i].v)){
				mx=vis[c[i].v];now=c[i].v;
			}
		}Ans=p[now];printf("%d\n",Ans);
	}else{
		int now=ans[u+1][v-1];
		int mx=S[v-1][now]-S[u][now];
		int R=u*blo,L=(v-1)*blo+1;
		for(int i=a;i<=R;++i){
			if(check[c[i].v]!=tim)check[c[i].v]=tim,vis[c[i].v]=0;
			vis[c[i].v]++;
		}
		for(int i=L;i<=b;++i){
			if(check[c[i].v]!=tim)check[c[i].v]=tim,vis[c[i].v]=0;
			vis[c[i].v]++;
		}
		for(int i=a;i<=R;++i){
			int cur=vis[c[i].v]+S[v-1][c[i].v]-S[u][c[i].v];
			if(cur>mx||(cur==mx&&now>c[i].v)){
				mx=cur;now=c[i].v;
			}
		}
		for(int i=L;i<=b;++i){
			int cur=vis[c[i].v]+S[v-1][c[i].v]-S[u][c[i].v];
			if(cur>mx||(cur==mx&&now>c[i].v)){
				mx=cur;now=c[i].v;
			}
		}Ans=p[now];printf("%d\n",Ans);
	}return;
}
 
int main(){
	freopen("numquery.in","r",stdin);
	freopen("numquery.out","w",stdout);
	read(n);read(m);blo=(int)(sqrt(n));k=(n%blo==0?n/blo:n/blo+1);
	for(int i=1;i<=n;++i){read(a[i]);c[i].id=i;c[i].v=a[i];}
	sort(a+1,a+n+1);sort(c+1,c+n+1,cmpv);
	for(int i=1;i<=n;++i){
		if(i==1||a[i]!=a[i-1])p[cnt+1]=c[i].v,c[i].v=++cnt;
		else c[i].v=cnt;
	}
	sort(c+1,c+n+1,cmpid);
	for(int i=1;i<=n;++i)pos[i]=(i-1)/blo+1;
	Get_Pre();
	while(m--){
		read(u);read(v);
		u=(u+Ans-1)%n+1;v=(v+Ans-1)%n+1;
		if(u>v)swap(u,v);
		Get_ans(u,v);
	}return 0;
}