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

本文主要是介绍【洛谷P4168】蒲公英【分块】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目大意：

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

---

思路：

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

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

• 方法1
  先暴力处理出所有的$cnt[i][i][j]$，然后用区间$dp$的思想，求出所有的$cnt[L][R][j]$，时间复杂度$O(T^{2}n)$
• 方法2
  预处理出$sum[R][i]$表示区间$1\sim 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-q\le 1$，那么这两个块中间就没有多余的整块，直接朴素求众数。
否则在$cnt[q+1][p-1]$的整块区间中，加上$[l,R[q]],[L[p],r]$之间的数字，然后求出答案。最后再减去加上的数就可以了。

---

算法时间复杂度为$O(n{T}^2+\frac{mT}{n})$，空间复杂度为$O(n{T}^2)$。为了平均时间，不妨设$n{T}^2=\frac{mT}{n}$，解得$T\approx \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\n",last);}return 0;
}

这篇关于【洛谷P4168】蒲公英【分块】的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---