提交链接

#include<bits/stdc++.h>
#define na putchar('\n')
using namespace std;
inline int read();
inline void write(long long n);
const int MAXN=4e4+5;
int n,m,k,a[MAXN],b[MAXN],cnt[MAXN][222],cobe[MAXN],last,x,aft[MAXN][222],i1;
vector<int>q;
vector<int>g;
int slove_easy(int l,int r){
	int ans,maxn=0;
	q.clear(),g.clear();
	q.resize(k+1);
	for(int i=l;i<=r;i++){
		q[a[i]]++;
		if(q[a[i]]==1)g.push_back(a[i]);
	}
	for(int i=0;i<(int)g.size();i++){
		if(q[g[i]]>maxn){
			maxn=q[g[i]];
			ans=g[i];
		}else if(q[g[i]]==maxn&&g[i]<ans){
			ans=g[i];
		}
	}
	return ans;
}
int slove_hard(int l,int r,int lk,int rk){
	int ans,maxn=0;
	q.clear(),g.clear();
	q.resize(k+1);
	for(int i=l;i<=min(n,lk*i1);i++){
		q[a[i]]++;
		if(q[a[i]]==1)g.push_back(a[i]);
	}
	for(int i=(rk-1)*i1+1;i<=r;i++){
		q[a[i]]++;
		if(q[a[i]]==1)g.push_back(a[i]);
	}
	for(int i=0;i<(int)g.size();i++){
		int s=g[i];
		int sum=q[s]+aft[s][rk-1]-aft[s][lk];
		if(sum>maxn){
			ans=s;
			maxn=sum;
		}else if(sum==maxn&&s<ans){
			ans=s;
		}
	}
	for(int i=lk+1;i<=rk-1;i++){
		int s=cobe[i];
		int sum=q[s]+aft[s][rk-1]-aft[s][lk];
		if(sum>maxn){
			ans=s;
			maxn=sum;
		}else if(sum==maxn&&s<ans){
			ans=s;
		}
	}
	return ans;
}
int main(){
//	freopen("P4168_1.in","r",stdin);
//	freopen("P4168_hack.txt","w",stdout);
	n=read(),m=read();
//	m=1;
	for(int i=1;i<=n;i++){
		a[i]=read();
		b[i]=a[i];
	}
	sort(b+1,b+n+1);
	k=unique(b+1,b+n+1)-b-1;
	for(int i=1;i<=n;i++){
		a[i]=lower_bound(b+1,b+k+1,a[i])-b;
	}
	/*
	printf("check 1:\n");
	for(int i=1;i<=n;i++){
		printf("%d ",a[i]);
	}
	na;
 	*/
	i1=sqrt(n);
	q.resize(k+1);
	for(int i=1;i<=n;i++){
		int s=a[i];
		q[s]++;
		if(i%i1==0){
			int maxn=0;
			for(int j=1;j<=k;j++){
				if(q[j]>maxn){
					cobe[i/i1]=j;
					maxn=q[j];
				}
			}
			for(int j=1;j<=k;j++){
				cnt[j][i/i1]=q[j];
			}
			q.clear();
			q.resize(k+1);
		}
	}
	last=n/i1;
	if(n%i1!=0){
		last++;
		int maxn=0;
		for(int j=1;j<=k;j++){
			cobe[n/i1+1]=j;
			maxn=q[j];
		}
		for(int j=1;j<=k;j++){
			cnt[j][n/i1+1]=q[j];
		}
	}
	q.clear();
	/* 
	printf("check 2:\n");
	for(int i=1;i<=last;i++){
		for(int j=1;j<=k;j++){
			printf("%d ",cnt[j][i]);
		}
		printf("\n");
	}
	*/
	/*
	printf("check 3:\n");
	for(int i=1;i<=last;i++){
		printf("i=%d ans=%d",i,cobe[i]);
		printf("\n");
	}
	*/
	for(int i=1;i<=k;i++){
		for(int j=1;j<=last;j++){
			aft[i][j]=aft[i][j-1]+cnt[i][j];
		}
	}
	while(m--){
		int l,r;
		l=read(),r=read();
//		l=282,r=428;
		l=((l+x-1)%n)+1,r=((r+x-1)%n)+1;
		if(l>r)swap(l,r);
		int ls=(l-1)/i1+1,rs=(r-1)/i1+1;
		printf("check 4: true input:\nl=%d r=%d\nblock into:\nlk=%d rk=%d\n",l,r,ls,rs);
		if(rs-ls<2){
			x=slove_easy(l,r);
		}else{
			x=slove_hard(l,r,ls,rs);
		}
		x=b[x];
		write(x);
		na;
//		na;
	}
	return 0;
}
/*
  cobe->块内众数编号
  cnt->块中数字出现数
  aft->cnt前缀和
  slove_easy->无完整块解法
  slove_hard->有完整块解法
*/
inline int read(){
	int s=0,w=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
	while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
	return s*w;
}
inline void write(long long n){
	if(n<0){putchar('-');n=-n;}
	if(n>9){write(n/10);}
	putchar(n%10+'0');
}