算法进阶指南（李煜东）上的方法一，80 pts $wa$

#include<bits/stdc++.h>
using namespace std;
int n,m,pqr,len,lslen;
int a[40005],ls[40005];
int cnt[55][55][40005],zs[55][55];
int l[1005],r[1005],tot[40005];
int last;
int query(int x,int y)
{
	int p=tot[x],q=tot[y],ans=0;
	if(q-p==0)
	{
		for(int i=x;i<=y;++i)
		{
			cnt[0][0][a[i]]++;
			if(cnt[0][0][a[i]]>cnt[0][0][ans]||(cnt[0][0][a[i]]==cnt[0][0][ans]&&a[i]<ans))
			{
				ans=a[i];
			}
		}
		for(int i=x;i<=y;++i)
		{
			cnt[0][0][a[i]]--;
		}
	}
	else
	{
		ans=zs[p+1][q-1];
		for(int i=x;i<=r[p];++i)
		{
			cnt[p+1][q-1][a[i]]++;
			if(cnt[p+1][q-1][a[i]]>cnt[p+1][q-1][ans]||(cnt[p+1][q-1][a[i]]==cnt[p+1][q-1][ans]&&a[i]<ans))
			{
				ans=a[i];
			}
		}
		for(int i=l[q];i<=y;++i)
		{
			cnt[p+1][q-1][a[i]]++;
			if(cnt[p+1][q-1][a[i]]>cnt[p+1][q-1][ans]||(cnt[p+1][q-1][a[i]]==cnt[p+1][q-1][ans]&&a[i]<ans))
			{
				ans=a[i];
			}
		}
		for(int i=x;i<=r[p];++i)
		{
			cnt[p+1][q-1][a[i]]--;
		}
		for(int i=l[q];i<=y;++i)
		{
			cnt[p+1][q-1][a[i]]--;
		}
	}
	return ls[ans];
}
int main()
{
//	freopen("P4168_1.in","r",stdin);
//	freopen("1.out","w",stdout); 
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;++i)
	{
		scanf("%d",&a[i]);
		ls[i]=a[i];
	}
	sort(ls+1,ls+n+1);
	lslen=unique(ls+1,ls+n+1)-ls;
	for(int i=1;i<=n;++i)
	{
		int ch=lower_bound(ls+1,ls+lslen+1,a[i])-ls;
		a[i]=ch;
	}
	for(;len*len*len<=n;++len);
	len--;
	pqr=n/len;
	for(int i=1;i<=len;++i)
	{
		l[i]=(i-1)*pqr+1;
		r[i]=i*pqr;
	}
	if(len*pqr!=n)
	{
		l[len+1]=len*pqr+1;
		r[len+1]=n;
		len++;
	}
	for(int i=1;i<=len;++i)
	{
		for(int j=l[i];j<=r[i];++j)
		{
			tot[j]=i;
		}
	}
	for(int i=1;i<=len;++i)
	{
		for(int j=i;j<=len;++j)
		{
			for(int k=l[i];k<=r[j];++k)
			{
				cnt[i][j][a[k]]++;
			}
			int tot=0;
			for(int k=1;k<=lslen;++k)
			{
				if(cnt[i][j][k]>tot)
				{
					tot=cnt[i][j][k];
					zs[i][j]=k;
				}
			}
		}
	}
	while(m--)
	{
		int l0,r0;
		scanf("%d%d",&l0,&r0);
		int p=(l0+last-1)%n+1,q=(r0+last-1)%n+1;
		if(p>q)
		swap(p,q);
		last=query(p,q);
		printf("%d\n",last);
	}
}