记录编号	540475	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	蒲公英	最终得分	100
用户昵称	Hale	是否通过	通过
代码语言	C++	运行时间	3.734 s
提交时间	2019-08-24 15:54:35	内存使用	15.56 MiB

#include<bits/stdc++.h>

#define bl(x) (((x-1)/m)+1)
#define lb(x) (((x)-1)*m+1)
#define rb(x) min((x)*m,n)
using namespace std;
const int N=4e4+7;
const int K=221;

int s[K][K],cnt[K][K];//s[i][j]表示从第i块到第j块的众数,cnt表示此众数出现的次数 
int l,r,m,n,k,ans,out,Q,S;
int sum[N],p[N],lik[N],a[N];
vector<int> idx[N];
void init()
{
	scanf("%d%d",&n,&Q);m=ceil(sqrt(n));
	for (int i=1;i<=n;i++) scanf("%d",&a[i]),p[i]=a[i];
	sort(p+1,p+n+1);
	S=unique(p+1,p+n+1)-p-1;
	for (int i=1;i<=n;i++)
	{
		a[i]=lower_bound(p+1,p+S+1,a[i])-p;
		idx[a[i]].push_back(i);
		lik[i]=idx[a[i]].size()-1;
	}
	memset(s,0x3f3f,sizeof(s));
	for (int i=1;i<=m;i++)
	{
		memset(sum,0,sizeof(sum));
		for (int j=i;j<=m;j++)
		{
			s[i][j]=s[i][j-1];
			cnt[i][j]=cnt[i][j-1];
			for (int k=lb(j);k<=rb(j);k++)
			{
				sum[a[k]]++;
				if (sum[a[k]]>cnt[i][j]||sum[a[k]]==cnt[i][j]&&a[k]<s[i][j])
				{cnt[i][j]=sum[a[k]];s[i][j]=a[k];}
			}
		}
	}
}
int main()
{
	freopen("Dandelion.in","r",stdin);
	freopen("Dandelion.out","w",stdout);
	init();
	while (Q--)
	{
		int l,r;scanf("%d%d",&l,&r);
		l=(l+out-1)%n+1;r=(r+out-1)%n+1;
		if (l>r) swap(l,r);
		int L=bl(l),R=bl(r);
		ans=cnt[L+1][R-1];out=s[L+1][R-1];
		if (!ans) {ans=1,out=a[l];}
		for (int i=l;i<=min(rb(L),r);i++)
		{
			int pos=lik[i]+ans-1;
			if (0<=pos&&pos<idx[a[i]].size()&&
				l<=idx[a[i]][pos]&&idx[a[i]][pos]<=r&&a[i]<out)
			out=a[i];
			while (lik[i]+ans<idx[a[i]].size()&&idx[a[i]][lik[i]+ans]<=r)
			{out=a[i];ans++;}
		}
		if (L!=R)
		for (int i=lb(R);i<=r;i++)
		{
			int pos=lik[i]-ans+1;
			if (0<=pos&&pos<idx[a[i]].size()&&
				l<=idx[a[i]][pos]&&idx[a[i]][pos]<=r&&a[i]<out)
			out=a[i];
			while (lik[i]-ans>=0&&idx[a[i]][lik[i]-ans]>=l)
			{out=a[i];ans++;}
		}
		printf("%d\n",out=p[out]);
	}
	return 0;
}