记录编号	600118	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	蒲公英	最终得分	100
用户昵称	djyqjy	是否通过	通过
代码语言	C++	运行时间	3.095 s
提交时间	2025-04-15 22:14:43	内存使用	6.84 MiB

#include<bits/stdc++.h>
#define int long long
using namespace std;
inline int re()
{
	int f=1,num=0;
	char c=getchar();
	while(c<'0'||c>'9'){if(c=='-') f=-1;c=getchar();}
	while(c>='0'&&c<='9') num=num*10+c-'0',c=getchar();
	return num*f;
}
const int N=40010,K=210;
int n,m,q,k=200,ks,ans,last;
int a[N],ys[N],L[K],R[K],z[K][K],s[K][N],bel[N],ls[N];
int cha(int x)
{
	int l=1,r=m,mid;
	while(l<r)
	{
		mid=(l+r)/2;
		if(ys[mid]>=x) r=mid;
		else l=mid+1;
	}
	return l;
}
int cnt(int l,int r,int z){return ls[z]+s[bel[r]-1][z]-s[bel[l]][z];}
signed main()
{
	freopen("Dandelion.in","r",stdin);
	freopen("Dandelion.out","w",stdout);
	n=re();q=re();ks=(n-1)/k+1;
	for(int i=1;i<ks;i++) L[i]=R[i-1]+1,R[i]=R[i-1]+k;
	L[ks]=R[ks-1]+1;R[ks]=n;
	for(int i=1;i<=n;i++) ys[i]=a[i]=re();
	sort(ys+1,ys+1+n);m=unique(ys+1,ys+1+n)-(ys+1);
	for(int i=1;i<=n;i++) a[i]=cha(a[i]);
	for(int i=1;i<=ks;i++)
	{
		for(int j=L[i];j<=R[i];j++)
		{
			bel[j]=i;
			s[i][a[j]]++;
		}
		for(int j=1;j<=m;j++) s[i][j]+=s[i-1][j];
	}
	for(int i=1;i<=ks;i++) 
	{
		for(int j=i;j<=ks;j++)
		{
			z[i][j]=z[i][j-1];
			for(int k=L[j];k<=R[j];k++)
			{
				ls[a[k]]++;
				if(ls[z[i][j]]<ls[a[k]]||(ls[z[i][j]]==ls[a[k]]&&z[i][j]>a[k])) z[i][j]=a[k];
			}
		}
		for(int k=L[i];k<=n;k++) ls[a[k]]--;
	}
	for(int i=1,l,r;i<=q;i++)
	{
		l=re();r=re();ans=0;
		l=(l+last-1)%n+1;
		r=(r+last-1)%n+1;
		if(l>r) swap(l,r);
		if(bel[l]==bel[r])
		{
			for(int j=l;j<=r;j++)
			{
				ls[a[j]]++;
				if(ls[ans]<ls[a[j]]||(ls[ans]==ls[a[j]]&&ans>a[j])) ans=a[j];
			}
			printf("%lld\n",last=ys[ans]);
			for(int j=l;j<=r;j++) ls[a[j]]--;
			continue;
		}
		for(int j=l;j<=R[bel[l]];j++) ls[a[j]]++;
		for(int j=L[bel[r]];j<=r;j++) ls[a[j]]++;
		for(int j=l;j<=R[bel[l]];j++) if(cnt(l,r,ans)<cnt(l,r,a[j])||(cnt(l,r,ans)==cnt(l,r,a[j])&&ans>a[j])) ans=a[j];
		if(cnt(l,r,ans)<cnt(l,r,z[bel[l]+1][bel[r]-1])||(cnt(l,r,ans)==cnt(l,r,z[bel[l]+1][bel[r]-1])&&ans>z[bel[l]+1][bel[r]-1])) ans=z[bel[l]+1][bel[r]-1];
		for(int j=L[bel[r]];j<=r;j++) if(cnt(l,r,ans)<cnt(l,r,a[j])||(cnt(l,r,ans)==cnt(l,r,a[j])&&ans>a[j])) ans=a[j];
		printf("%lld\n",last=ys[ans]);
		for(int j=l;j<=R[bel[l]];j++) ls[a[j]]--;
		for(int j=L[bel[r]];j<=r;j++) ls[a[j]]--;
	}
	return 0;
}