分块95求卡常

#include<bits/stdc++.h>
using namespace std;
#define int unsigned long long
int n,q,block,tot,last_ans,a[40005],b[205][40005],to_back[40005],res[40005];unordered_map<int,int>lsh;
int query(int l,int r){
	int lb=(l-1)/block+1,rb=(r-1)/block+1;
	for(int i=1;i<=tot;i++)res[i]=0;
	if(lb==rb)for(int i=l;i<=r;i++)res[a[i]]++;
	else{
		for(int i=l;i<=lb*block;i++)res[a[i]]++;
		for(int i=(rb-1)*block+1;i<=r;i++)res[a[i]]++;
		for(int i=1;i<=tot;i++)res[i]=res[i]+b[rb-1][i]-b[lb][i];
	}int mx=0;for(int i=1;i<=tot;i++){
		if(res[i]==res[mx]){if(to_back[i]<to_back[mx])mx=i;}
		else if(res[i]>res[mx])mx=i;
	}return mx;
}void build(){
	for(int i=1;i<=n;i++)b[(i-1)/block+1][a[i]]++;
	for(int i=1;i<=(n-1)/block+1;i++)for(int j=1;j<=tot;j++)b[i][j]+=b[i-1][j];
}
signed main(){
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	cin>>n>>q;block=sqrt(n)*2;
	for(int i=1;i<=n;i++){
		int x;cin>>x;
		if(lsh[x])a[i]=lsh[x];
		else  a[i]=lsh[x]=++tot,to_back[tot]=x;
	}build();while(q--){
		int l,r;cin>>l>>r;l=(l+last_ans-1)%n+1,r=(r+last_ans-1)%n+1;
		if(l>r)swap(l,r);last_ans=to_back[query(l,r)];
		cout<<last_ans<<'\n';
	}return 0;
}