P4168

麻风清晰

#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define re register
#define int long long

using namespace std;
const int N=2e5+10,M=2e3+10,LM=8e4+10;
int n,Q,a[N],ql,qr,lsans;
int bnum,m,belong[N],L[N],R[N],bz[M][M],p[M][LM],num[M][M];

inline int read(){char cr=getchar();int x_=0,fui=1;while(cr<48){if(cr=='-')fui=-1;cr=getchar();}while(cr>47)x_=(x_*10)+(cr^48),cr=getchar();return x_*fui;}
inline void mwrite(int aq){if(aq>9)mwrite(aq/10);putchar((aq%10)|48);}
inline void write(int af,char cr){mwrite(af<0?(putchar('-'),af=-af):af);putchar(cr);}

struct Node{
	int v,id;
}A[N];
int tot,fac[N];
inline bool cmp(Node P,Node Q) {return P.v<Q.v;}
int cnt[N];
inline void init()
{
	sort(A+1,A+n+1,cmp);
	for(re int i=1;i<=n;++i) 
	{
		if(A[i].v!=A[i-1].v) ++tot;
		fac[tot]=a[A[i].id];
		a[A[i].id]=tot;
	}
	//
	m=sqrt(n),bnum=(n-1)/m+1;
	for(re int i=1;i<=n;++i) belong[i]=(i-1)/m+1;
	for(re int i=1;i<=bnum;++i) L[i]=(i-1)*m+1,R[i]=i*m;
	R[bnum]=n;
	memset(bz,0x3f3f3f3f,sizeof bz);
	for(re int i=1;i<=bnum;++i)
	{
		memset(cnt,0,sizeof cnt);
		for(re int j=i;j<=bnum;++j)
		{
			for(re int k=L[j];k<=R[j];++k)
			{
				++cnt[a[k]];
				if(cnt[a[k]]==num[i][j]&&a[k]<bz[i][j]) bz[i][j]=a[k];
				else if(cnt[a[k]]>num[i][j]) num[i][j]=cnt[a[k]],bz[i][j]=a[k]; 
			}
		}
	}
	memset(cnt,0,sizeof cnt);
	for(re int i=1;i<=bnum;++i)
	{
		for(re int j=1;j<=n;++j) p[i][a[j]]=p[i-1][a[j]];
		for(re int j=L[i];j<=R[i];++j) p[i][a[j]]++;
	}
}
inline int ask(int l,int r)
{
	int ans=1e9,res=0;
	if(belong[r]-belong[l]<=2) 
	//
	{
		//
		for(re int i=l;i<=r;++i) cnt[a[i]]=0;
		for(re int i=l;i<=r;++i)
		{
			cnt[a[i]]++;
			if(cnt[a[i]]==res&&a[i]<ans) ans=a[i];
			else if(cnt[a[i]]>res) res=cnt[a[i]],ans=a[i];
		}
		return ans;
	}
	ans=bz[belong[l]+1][belong[r]-1],res=num[belong[l]+1][belong[r]-1];
	for(re int i=l;i<=R[belong[l]];++i) cnt[a[i]]=0;
	for(re int i=L[belong[r]];i<=r;++i) cnt[a[i]]=0;
	for(re int i=l;i<=R[belong[l]];++i)
	{
		cnt[a[i]]++;
		if(cnt[a[i]]+p[belong[r]-1][a[i]]-p[belong[l]][a[i]]==res&&a[i]<ans) ans=a[i];
		else if(cnt[a[i]]+p[belong[r]-1][a[i]]-p[belong[l]][a[i]]>res) res=cnt[a[i]]+p[belong[r]-1][a[i]]-p[belong[l]][a[i]],ans=a[i];
	}
	for(re int i=L[belong[r]];i<=r;++i)
	{
		cnt[a[i]]++;
		if(cnt[a[i]]+p[belong[r]-1][a[i]]-p[belong[l]][a[i]]==res&&a[i]<ans) ans=a[i];
		else if(cnt[a[i]]+p[belong[r]-1][a[i]]-p[belong[l]][a[i]]>res) res=cnt[a[i]]+p[belong[r]-1][a[i]]-p[belong[l]][a[i]],ans=a[i];
	}
	return ans;
}
signed main()
{
	n=read(),Q=read();
	for(re int i=1;i<=n;++i) A[i].v=a[i]=read(),A[i].id=i;
	init();
	while(Q--)
	{
		ql=((read()+lsans-1)%n)+1,qr=((read()+lsans-1)%n)+1;
		if(ql>qr) swap(ql,qr);
		write(lsans=fac[ask(ql,qr)],'\n');
	}
	return 0;
}