众数问题

Published: July 15, 2021 by Daltao

• Categories:
• algorithm 101

• Tags:

• 区间众数
• 存在众数的连续子序列计数

区间众数

题目1：给定一个序列$a_1,\ldots,a_n$，要求回答$q$个请求，第$i$个请求给定三个参数$l_i,r_i,k_i$，要求找出区间$a_l,\ldots,a_r$中出现次数超过$\frac{r_i-l_i+1}{k_i}$的最小的数，如果不存在则输出$-1$。其中$n,q\leq 10^5$，$1\leq k\leq 5$

这个问题有很多做法。

第一种就是用莫队。莫队内部维护一个统计表，统计每个数在区间中出现的次数。且由于每次每个数出现次数变化最多为$1$，因此对于每个分块，分配一个链表数组，第$i$个元素记录该分块中所有出现次数为$i$的元素组成的链表。很显然这样我们不管某个数出现次数是加$1$还是减$1$，都可以$O(1)$完成，且最重要的是我们可以实时统计每个分块中的最大值。在回答请求的时候，我们可以利用分块中的最大值先找满足条件的编号最小的分块，之后在分块中暴力查找。因此总的时间复杂度为$O((n+q)\sqrt{n})$。

莫队的做法优点是与$k$无关，缺点是常数比较大，且必须离线请求。

第二种做法就是发现，对于某个回答，我们可以不断从区间中选择$k$个不同的数，之后删除。最后留下来的数不超过$k-1$个，我们可以证明结果一定在这留下来的数中。这种区间消除的方式，我们可以用线段树实现，这样每次线段树的查询和修改的时间复杂度都是$O(k^2\log_2n)$。之后如果验证结果呢，这个我们可以通过持久化技术加差分或者直接上倍增完成，校验一个数的时间复杂度为$O(\log_2n)$，总的时间复杂度为$O((q+n)k^2\log_2n)$。

第二种做法的优点是支持在线（我们可以为每个数都开一个稀疏线段树），缺点就是$k$不能过大。

还有一种非常简单的做法就是直接上持久化线段树+差分的技术。线段树的每个结点记录区间中每个数出现的次数。之后对于每个请求，我们暴力扫描线段树，加上一旦发现区间中总数少于阈值就直接退出的剪枝。可以证明一次请求，线段树每一层最多有$k$个顶点被访问（因为阈值决定了每一层最多有$k$个条件满足条件）。总的时间复杂度为$O((n+kq)\log_2n)$。

第三种做法可以充分利用$k$很小的特性。但是$k$比较大的时候还是用莫队比较好。

一道题目。

问题2：给定一个序列$a_1,\ldots,a_n$，以及$q$个请求，每个请求指定一个区间$l,r$，要求找到序列$a_l,\ldots,a_r$中的众数（出现次数最多的数），如果有多个，就输出其中最小的。这里$n,q\leq 10^5$，要求在线处理请求

一道题目。

先离散化数据。

这道题目的核心是发现，要计算$A\cup B$的区间众数，其仅可能为$A$的区间众数，或者是$B$中的某个元素。

上面这个观察允许我们用分块解决这个问题。按照大小$\sqrt{n}$进行分块。

之后考虑一次请求，可以知道答案要么出现在区间两端的块中，要么就是区间中间部分的众数。

我们可以维护两个数组$c$和$p$。其中$c(i,j)$表示前$i$块中$j$的出现次数。这样我们可以利用差分的技巧来快速计算某个数字在连续块中总的出现次数。而$p(i,j)$表示第$i$块到第$j$块中的众数。数组$c$可以直接暴力计算每一块的信息最后统计前缀和，而$p$可以暴力枚举两端块，之后通过$p(i,j-1)$快速转移。预处理的时间复杂度和空间复杂度均为$O(n^{1.5})$。

每次请求我们也能以$O(\sqrt{n})$求解，枚举每个可能的众数即可（总共只有$O(\sqrt{n})$种可能）。

总的时间复杂度为$((n+q)\sqrt{n})$。

问题3：给定一个序列$a_1,\ldots,a_n$，找到一段最长的子数组（从头部和尾部删除若干个元素得到），满足子数组中众数非唯一，如果不存在这样的子数组，返回$0$。其中$1\leq n\leq 10^5$。

昨天比赛的一道题目。

称满足众数非唯一的数组称为好数组。假设$1$为整个数组的一个众数，我们可以直接证明任意最长的好数组一定包含$1$，否则我们可以扩大数组两端得到以$1$为众数的另外一个更长的好数组。

接下来，我们来考虑如何求这样一个好数组。我们可以暴力枚举另外一个众数$x$。找到$x$出现次数大于等于$1$出现次数的子数组，我们可以发现这样的数组一定可以扩展为好数组。当然这样做时间复杂度会变成$O(n^2)$，一种方式就是使用分块。我们只枚举出现次数超过$\sqrt{n}$的元素。而对于出现次数不超过$\sqrt{n}$的元素，我们知道这样的区间中$1$的出现次数也不会超过$\sqrt{n}$。于是乎我们可以分别对$1$出现次数为$1,2,\ldots,\sqrt{n}$暴力遍历数组$a$，每次遍历都使用双指针，整体的时间复杂度为$O(n\sqrt{n})$。

存在众数的连续子序列计数

一个连续子序列称为是好的，当且仅当其中有一个数出现超过半数以上，这个数称为众数。

现在给定一个长度为$n$的序列$a_1,\ldots,a_n$，要求统计有多少连续子序列是好的。

提供一道题目。

一种简单的思路是使用分块。先考虑所有出现次数不超过$\sqrt{n}$的数，它们能形成的连续子序列长度不会超过$2\sqrt{n}$。因此我们枚举所有长度不超过$2\sqrt{n}$的连续子序列，如果它里面存在众数，且总数全局出现次数不超过$\sqrt{n}$。

而对于出现次数超过$\sqrt{n}$的数$x$，我们可以构建一个序列$b$，其中如果$a_i=x$，则$b_i=1$，否则$b_i=-1$。问题就变成了有多少子数组和是正数。这个问题咋看之下需要维护一个树状数组来解决，但是实际上由于前缀和只会+1和-1，因此可以通过维护一个普通计数数组就可以了，于是这个新问题的时间复杂度为$O(n)$。而$x$最多取$\sqrt{n}$个数，因此总的时间复杂度为$O(n\sqrt{n})$。

下面讲另外一种思路，可以将时间复杂度优化到$O(n)$。

具体就是我们不分块处理，对于每个不同的数$x$，我们都构建$b$序列，并处理。很显然这样做的时间复杂度为$O(nD)$，$D$为$a$序列中的不同数数目。

假设$x$在$a$中出现$k$次，我们可以尝试将时间复杂度优化到$O(k)$。具体思路是我们可以把$b$中连续的-1合并为到一起。假设有一块连续的-1左边界为$l$，右边界为$r$，且以$l-1$为右边界的最大子数组和为$L$，以$r+1$为左边界的最大子数组和为$R$，如果$L+R-(r-l+1)\leq 0$，这意味着不可能有好数组包含这一整块-1。因此我们可以把这一段-1删除到只剩下$R+L$个，这不会影响我们的结果。可以发现这样做，会导致从左向右扫描的时候每个1最多会激活一个-1，同理从右往左扫描的时候每个1最多会激活一个-1。因此这样处理完后最多有$2k$个$-1$，我们需要处理的$b$序列长度仅为$3k$，用同样的算法，我们可以$O(3k)$处理。

总的时间复杂度为$O(n)$。