rtqwq

你在那个城市里面过得好吗？

#include<bits/stdc++.h>
#include<bits/extc++.h>
using namespace std;
using namespace __gnu_pbds;
int n,m;
const int N=40000+520;
const int block_size=(int)sqrt(N)+5;
int tag[N],cl[N],cr[N],f[block_size][block_size],sum[block_size][N],cn[block_size][N];
int a[N];
int x;
vector<int> val;
unordered_map<int,int> mp_rnk;
inline void build(){
	int B=sqrt(n);
	sort(val.begin(),val.end());
	val.erase(unique(val.begin(),val.end()),val.end());
	int cnt=0;
	for(auto v:val){
		mp_rnk[v]=cnt++;
	}
	for(int i=1;i<=(n%B==0?n/B:n/B+1);i++){
		for(int j=(i-1)*B+1;j<=min(n,i*B);j++){
			tag[j]=i;
			cl[j]=(i-1)*B+1;
			cr[j]=min(n,i*B);
			cn[i][mp_rnk[a[j]]]++;
		}
		for(auto v:val)		sum[i][mp_rnk[v]]=sum[i-1][mp_rnk[v]]+cn[i][mp_rnk[v]];
	}
	for(int i=1;i<=B;i++){
		for(int j=i;j<=B;j++){
			int zs=f[i][j-1];
			for(int k=(j-1)*B+1;k<=min(j*B,n);k++){
				if(/*sum[j][mp_rnk[a[k]]]-sum[i-1][mp_rnk[a[k]]]>=2&&*/sum[j][mp_rnk[a[k]]]-sum[i-1][mp_rnk[a[k]]]>=sum[j][mp_rnk[zs]]-sum[i-1][mp_rnk[zs]]){
					if(sum[j][mp_rnk[a[k]]]-sum[i-1][mp_rnk[a[k]]]>=sum[j][mp_rnk[zs]]-sum[i-1][mp_rnk[zs]])	zs=min(zs,a[k]);
					else zs=a[k];
				}
			}
			f[i][j]=zs;
		}
	}
}
unordered_map<int,int> tmp;
inline int query(int l,int r){
	int ans=0,res=0;
	if(tag[r]-tag[l]<=1){
		for(int i=l;i<=r;i++){
			if(++tmp[a[i]]>ans){
				ans=tmp[a[i]];
				res=a[i];
			}
			else if(tmp[a[i]]==ans){
				res=min(res,a[i]);
			}
		}
		tmp.clear();
		return res;
	}
	else{
		res=f[tag[l]+1][tag[r]-1];
		for(int i=l;i<=cr[l];i++){
			tmp[a[i]]++;
		}
		for(int i=cl[r];i<=r;i++){
			tmp[a[i]]++;
		}
		ans=sum[tag[r]-1][mp_rnk[f[tag[l]+1][tag[r]-1]]]-sum[tag[l]][mp_rnk[f[tag[l]+1][tag[r]-1]]];
		for(auto v:val){
			if(tmp[v]){
				if(sum[tag[r]-1][mp_rnk[v]]-sum[tag[l]][mp_rnk[v]]+tmp[v]==ans){
					res=min(res,v);
				}
				else if(sum[tag[r]-1][mp_rnk[v]]-sum[tag[l]][mp_rnk[v]]+tmp[v]>ans){
					ans=sum[tag[r]-1][mp_rnk[v]]-sum[tag[l]][mp_rnk[v]]+tmp[v];
					res=v;
				}
			}
		}
		tmp.clear();
		return res;
	}
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(NULL),cout.tie(NULL);
	cin>>n>>m;
	for(int i=1;i<=n;i++)	cin>>a[i],val.push_back(a[i]);
	build();
	for(int i=1;i<=m;i++){
		int l,r;
		cin>>l>>r;
		l=(l+x-1)%n;
		l++;
		r=(r+x-1)%n;
		r++;
		if(l>r)	swap(l,r);
		cout<<query(l,r)<<endl;
	}
	return 0;
}