蒲公英(bzoj2724)(分块+区间众数)

Input

Output

Sample Input

6 3

1 2 3 2 1 2

1 5

3 6

1 5

Sample Output

1

2

1

HINT

\(n <= 40000\),$ m <= 50000$

题意：

求区间众数

题解：

见代码

//解决本题的重要性质：

//对于两个区间a,b,其中已知a区间的众数k

//则众数一定为k或是b区间的任意一个数

#include<bits/stdc++.h>

#define re register int

using namespace std;

const int N=40010,M=410;

int n,q,m,blen,bsum;

int a[N],b[N];//b为离散数组

int bl[M][M];//bl[i][j]表示第i个块中的第j个数，bl[i][0]表示第i个块的长度

int bk[N];//bk[i]表示第i个数（在原数列中）在第bk[i]个块中

int f[M][M];//f[i][j]表示第i块到第j块之间的众数

int g[N][M];//g[i][j]表示i在前j个块中出现的次数

void init(){//初始化

	for(int i=1,j=1;i<=n;++j){

		int k;

		for(k=1;k<=blen&&i<=n;++i,++k){

			bk[i]=j;

			bl[j][k]=a[i];

		}k--;

		bl[j][0]=k;

		bsum=j;

	}//处理块

	for(int i=1;i<=bsum;++i){

		for(int j=1;j<=m;++j){

			g[j][i]=g[j][i-1];

		}

		for(int j=1;j<=bl[i][0];++j){

			g[bl[i][j]][i]++;

		}

	}//预处理g数组

	for(int i=1;i<=bsum;++i){

		for(int j=i;j<=bsum;++j){

			int num=f[i][j-1];int mx=g[num][j]-g[num][i-1];

			for(int k=1;k<=bl[j][0];++k){

				int now=g[bl[j][k]][j]-g[bl[j][k]][i-1];

				if(now>mx||(now==mx&&bl[j][k]<num))num=bl[j][k],mx=now;

			}

			f[i][j]=f[j][i]=num;

		}

	}//预处理f数组

}

void read(){//读入

	cin>>n>>q;blen=sqrt(n);

	for(int i=1;i<=n;++i)scanf("%d",a+i),b[i]=a[i];

}

void lsh(){

	sort(b+1,b+n+1);

	m=unique(b+1,b+n+1)-b-1;

	for(int i=1;i<=n;++i)a[i]=lower_bound(b+1,b+m+1,a[i])-b;

}

void work(){

	int last=0;

	while(q--){

		int l,r;

		scanf("%d%d",&l,&r);

		l=(l+last-1)%n+1;

		r=(r+last-1)%n+1;

		if(l>r)swap(l,r);

		static int bj[M],cnt,v[N];cnt=0;//bj记录边角的数据,cnt为边角数据的数量

		int L,R,num,mx;

		if(bk[l]==bk[r]){//在同一块内暴力求众数

			for(int i=l;i<=r;++i)bj[++cnt]=a[i],v[a[i]]++;

			mx=0;

			for(int i=l;i<=r;++i){

				if(v[a[i]]>mx||(v[a[i]]==mx&&a[i]<num))num=a[i],mx=v[a[i]];

			}

			printf("%d\n",last=b[num]);

		}else{//在不同块时，将中间当成一大块和边角比较

		      //根据性质，众数只有可能是中间这一块的众数或是边角上的数

			  //所以暴力枚举再判断就行了

			re i;

			for(i=l;bk[i]==bk[i-1];++i){

				bj[++cnt]=a[i];v[a[i]]++;

			}L=bk[i];

			for(i=r;bk[i]==bk[i+1];--i){

				bj[++cnt]=a[i];v[a[i]]++;

			}R=bk[i];

		    num=f[L][R],mx=v[num]+g[num][R]-g[num][L-1];

		    for(i=1;i<=cnt;++i){

		    	int now=v[bj[i]]+g[bj[i]][R]-g[bj[i]][L-1];

		    	if(now>mx||(now==mx&&bj[i]<num))num=bj[i],mx=now;

			}

			printf("%d\n",last=b[num]);

		}

		for(re i=1;i<=cnt;++i)--v[bj[i]];//v数组要这样清空，复杂度O(cnt)，不能用memset，那样是O(n)

	}

}

int main(){

	read();

	lsh();

	init();

	work();

}