洛谷P4168 蒲公英分块处理区间众数模板 _生活百科

题面。
许久以前我还不怎么去机房的时候，一位大佬好像一直在做这道题，他称这道题目为“大分块” 。
其实这道题目的思想不只可以用于处理区间众数，还可以处理很多区间数值相关问题。
让我们在线处理区间众数。
数据范围1e5，考虑分块。
先对蒲公英种类离散化。

预处理

预处理出两个数组。
【洛谷P4168 蒲公英分块处理区间众数模板】一个数组sum[ i ][ j ]表示第j种颜色到第i个分块的前缀和。
另一个数组 zhongshu[ i ][ j ]表示第i个分块到第j个分块这个区间内的众数。
维护这两个操作时间复杂度都不能超过n3/2 。
第一个数组很好维护，输入的时候将输入位置对应分块的相应种类加一，然后跑一遍前缀和即可，时间复杂度n*n1/2 。
维护第二个数组，我们需要先枚举起始分块。
从起始分块开始，枚举终点分块，每枚举一个终点分块，更新这个分块内元素对于区间众数的贡献。
建立一个数组tmp[ i ]作为辅助数组表示颜色i出现次数。
for(int i=1;i<=get_pos(n);i++){//枚举起始分块 int mx=0;//从当前这个起始分块开始，到终点分块位置的众数for(int j=i;j<=get_pos(n);j++)//枚举终点分块 for(int k=(j-1)*len+1;k<=min(j*len,n);k++){ tmp[a[k]]++;//当前元素出现次数加一 if(tmp[a[k]]>tmp[mx])//若当前元素出现次数大于当前处理区间众数的出现次数，则将众数修改为当前元素 mx=a[k]; if(!(tmp[a[k]]^tmp[mx]))//若当前元素与当前处理区间众数出现次数相等，则取编号小的为众数 mx=min(mx,a[k]); } b_mos[i][j]=mx;//从分块i到分块j的众数就是mx } for(int j=0;j<=ntot;j++)//清空辅助数组 tmp[j]=0; }时间复杂度为n1/2 *（n+n1/2*n1/2），即n3/2 。

处理询问

对于询问的l，r，算出其所处分块lb,rb 。
若l与r在同一分块或在相邻块内，可以暴力求出众数，时间复杂度n1/2 。
int get_vio(){//vio指violent int mx=0; for(int i=l;i<=r;i++){ tmp[a[i]]++; if(tmp[a[i]]>tmp[mx])//按比较规则进行更新。 mx=a[i]; if(!(tmp[a[i]]^tmp[mx])) mx=min(mx,a[i]); } for(int i=l;i<=r;i++) tmp[a[i]]--; return mx;}若l与r所在分块中间相隔了至少一个分块，那么所询问区间的众数只有两种可能。

中间那一段分块的众数
左端点所在块与右端点所在块内的数

不难理解。
对于中间那一段分块内的数，如果它们的出现次数要超过中间那一段分块内的众数，那么它们必须要在左端点所在块和右端点所在块内出现。
先将中间那一段分块的众数设为答案，再对左端点和右端点所在块内的数统计出现次数并更新答案即可。
int get_tim(int x){ return tmp[x]+b_sum[rb-1][x]-b_sum[lb][x];//计算某数的总出现次数}int get_q(){ int mx=b_mos[lb+1][rb-1];//先将答案设为中间那一段分块内的众数 for(int i=l;i<=lb*len;i++){ tmp[a[i]]++; if(get_tim(a[i])>get_tim(mx))//按照比较规则更新答案 mx=a[i]; if(get_tim(a[i])==get_tim(mx)) mx=min(mx,a[i]); } for(int i=(rb-1)*len+1;i<=r;i++){ tmp[a[i]]++; if(get_tim(a[i])>get_tim(mx)) mx=a[i]; if(get_tim(a[i])==get_tim(mx)) mx=min(mx,a[i]); } for(int i=l;i<=lb*len;i++)//清空辅助数组 tmp[a[i]]--; for(int i=(rb-1)*len+1;i<=r;i++) tmp[a[i]]--; return mx;}