P4168 [Violet]蒲公英(分块魔术)

给出一个序列。

每次询问区间最小的众数

强制在线

预处理出两个数组:

(a[i][j]):表示第i个块到第j个块的最小的众数。

(b[i][j]):表示前i个块中值j出现了几次,这里j需要先离散化。

预处理出a数组和b数组。

预处理a:枚举i和j,用数组暴力维护同一个i的所有j的答案。(从前往后遍历,暴力更新)。

预处理b:对每个块统计答案,然后前缀和搞一下。

对于一个询问[l,r],设l在第pl个块中,r在第pr个块中。

如果l和r在同一个块,直接暴力统计一遍就行。

如果l和r不在同一个块,(a[l][r])肯定可以作为答案候选。

然后我们只需要枚举除了整块以外,零散的元素。

他们的出现次数就是我们枚举出来的次数加上b数组区间求和的答案。

和候选答案比较,取更优的即可。

原文地址:https://www.cnblogs.com/zhanglichen/p/15075520.html