Chrysanthemum's Blog

Description

Input

Output

Sample Input

Sample Output

HINT

Source

大家可以先看一下陈立杰的论文《区间众数解题报告》，这道题是没有修改的情况。我们只要用分块大法做就可以了。

附：陈立杰论文截取

代码：

#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;
int n,q,m,x,y,ans,Max,L,R,len,num;
int a[40010],p[40010],b[40010],c[40010],le[40010],ri[40010],sum[40010];
int l[210],r[210],f[210][210],g[210][210];
int get(int l,int r,int x)
{return upper_bound(c+le[x],c+ri[x]+1,r)-lower_bound(c+le[x],c+ri[x]+1,l);}
void ask(int l,int r,int x,int y)
{
	for (int i=x;i<=y;i++)
	{
		int cnt=get(l,r,a[i]);
		if (cnt>Max||(cnt==Max&&a[i]<ans)){ans=a[i];Max=cnt;}
	}
}
int main()
{
	scanf("%d%d",&n,&q);
	for (int i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
		p[i]=a[i];
	}
	m=n;
	sort(p+1,p+m+1);
	m=unique(p+1,p+m+1)-p-1;
	for (int i=1;i<=n;i++)
		a[i]=lower_bound(p+1,p+m+1,a[i])-p;
	for (int i=1;i<=n;i++)
		b[a[i]]++;
	for (int i=1;i<=m;i++)
		b[i]+=b[i-1];
	for (int i=1;i<=m;i++){le[i]=b[i-1]+1;ri[i]=b[i-1];}
	for (int i=1;i<=n;i++) c[++ri[a[i]]]=i;
	len=(int)sqrt(n);
	num=n/len;if (n%len) num++;
	for (int i=1;i<=num;i++){l[i]=(i-1)*len+1;r[i]=min(i*len,n);}
	for (int i=1;i<=num;i++)
	{
		x=y=0;
		memset(sum,0,sizeof(sum));
		for (int j=i;j<=num;j++)
		{
			for (int k=l[j];k<=r[j];k++)
			{
				sum[a[k]]++;
				if (sum[a[k]]>y||(sum[a[k]]==y&&a[k]<x)){x=a[k];y=sum[a[k]];}
			}
			f[i][j]=x;g[i][j]=y;
		}
	}
	ans=0;
	while (q--)
	{
		scanf("%d%d",&x,&y);
		x=(x+ans-1)%n+1;y=(y+ans-1)%n+1;
		if (x>y) swap(x,y);
		L=x/len;if (r[L]<x) L++;
		R=y/len;if (r[R]<y) R++;
		ans=0;Max=0;
		if (L==R) {ask(x,y,x,y);ans=p[ans];printf("%d\n",ans);continue;}
		if (R-1>=L+1){ans=f[L+1][R-1];Max=g[L+1][R-1];}
		ask(x,y,x,r[L]);ask(x,y,l[R],y);
		ans=p[ans];
		printf("%d\n",ans);
	}
}