【洛谷P4168】蒲公英【分块】

题目大意：

题目链接：https://www.luogu.org/problemnew/show/P4168
给出一个长度为 $n$ 的序列， $m$ 次询问，求区间 $[l,r]$ 中的众数。强制在线。

思路：

以下内容参考 $lyd$ 《算法竞赛进阶指南》。

先离散化不解释。
分块算法一般都是以“暴力+区间预处理+暴力”的方法做的。所以，我们把 $n$ 分成 $T$ 块，每块长度 $⌊frac{T}{n}⌋$ 。
然后预处理出对于任意两个区间内的数字个数。也就是说，对于任意的 $1leq lleq rleq T$ ，我们用 $cnt[L][R][i]$ 表示块 $Lsim R$ 内数字 $i$ 的个数。
如何预处理出这一部分？

方法1
先暴力处理出所有的 $cnt[i][i][j]$ ，然后用区间 $dp$ 的思想，求出所有的 $cnt[L][R][j]$ ，时间复杂度 $O(T^2n)$
方法2
预处理出 $sum[R][i]$ 表示区间 $1sim R$ 之间 $i$ 的个数。然后用前缀和思想， $cnt[L][R][i]=sum[R][i]-sum[L][i]$ 。时间复杂度 $O(T^2)$

同时在预处理 $cnt$ 的时候顺便处理出 $Max[L][R]$ ，表示区间众数，然后记录众数的个数。
接下来就是如何处理答案了。
对于任意一组询问，设询问区间 $[l,r]$ ，那么先记录 $q,p$ 分别表示 $l,r$ 所在的块。如果 $p-qleq 1$ ，那么这两个块中间就没有多余的整块，直接朴素求众数。
否则在 $cnt[q+1][p-1]$ 的整块区间中，加上 $[l,R[q]],[L[p],r]$ 之间的数字，然后求出答案。最后再减去加上的数就可以了。

算法时间复杂度为 $O(nT^2+frac{mT}{n})$ ，空间复杂度为 $O(nT^2)$ 。为了平均时间，不妨设 $nT^2=frac{mT}{n}$ ，解得 $T≈sqrt[3]{n}$ 。此时时间复杂度约为 $O(n^{frac{5}{3}})$ 。

代码：

#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
using namespace std;

const int N=50010;
int a[N],b[N],cnt[40][40][N],L[40],R[40],pos[N],sum[N],Max[40][40][2],be[N];
int n,m,T,x,y,len,tot,last;

int ask(int l,int r)
{
	int ans=0,maxn=0;
	int q=pos[l],p=pos[r];
	if (p-q<=1)
	{
		memset(sum,0,sizeof(sum));
		for (int i=l;i<=r;i++)
		{
			sum[a[i]]++;
			if (sum[a[i]]>maxn||(sum[a[i]]==maxn&&a[i]<ans))
				maxn=sum[a[i]],ans=a[i];
		}
		return ans;
	}
	maxn=Max[q+1][p-1][0];
	ans=Max[q+1][p-1][1];
	for (int i=l;i<=R[q];i++)
	{
		cnt[q+1][p-1][a[i]]++;
		if (cnt[q+1][p-1][a[i]]>maxn||(cnt[q+1][p-1][a[i]]==maxn&&a[i]<ans))
			maxn=cnt[q+1][p-1][a[i]],ans=a[i];
	}
	for (int i=L[p];i<=r;i++)
	{
		cnt[q+1][p-1][a[i]]++;
		if (cnt[q+1][p-1][a[i]]>maxn||(cnt[q+1][p-1][a[i]]==maxn&&a[i]<ans))
			maxn=cnt[q+1][p-1][a[i]],ans=a[i];
	}
	for (int i=l;i<=R[q];i++) cnt[q+1][p-1][a[i]]--;
	for (int i=L[p];i<=r;i++) cnt[q+1][p-1][a[i]]--;
	return ans;
}

int main()
{
	scanf("%d%d",&n,&m);
	for (int i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
		b[i]=a[i];
	}
	sort(b+1,b+1+n);
	tot=unique(b+1,b+1+n)-b-1;
	for (int i=1;i<=n;i++)
	{
		x=lower_bound(b+1,b+1+tot,a[i])-b;
		be[x]=a[i];
		a[i]=x;
	}
	T=(int)pow((double)n,1.0/3.0);
	len=n/T;
	if (T*len<n) T++;
	for (int i=1;i<=T;i++)
	{
		L[i]=R[i-1]+1;
		R[i]=min(i*len,n);
		for (int j=L[i];j<=R[i];j++)
		{
			cnt[i][i][a[j]]++;
			if (cnt[i][i][a[j]]>Max[i][i][0]||(cnt[i][i][a[j]]==Max[i][i][0]&&a[j]<Max[i][i][1]))
			{
				Max[i][i][0]=cnt[i][i][a[j]];
				Max[i][i][1]=a[j];
			}
			pos[j]=i;
		}
	}
	for (int k=1;k<T;k++)
		for (int i=1;i<=T-k;i++)
		{
			int j=i+k;
			int mid=(i+j)/2;
			for (int l=1;l<=tot;l++)
			{
				cnt[i][j][l]=cnt[i][mid][l]+cnt[mid+1][j][l];
				if (cnt[i][j][l]>Max[i][j][0])
				{
					Max[i][j][0]=cnt[i][j][l];
					Max[i][j][1]=l;
				}
			}
		}
	while (m--)
	{
		scanf("%d%d",&x,&y);
		x=(x+last-1)%n+1;
		y=(y+last-1)%n+1;
		if (x>y) swap(x,y);
		last=be[ask(x,y)];
		printf("%d
",last);
	}
	return 0;
}