摩尔投票法（Boyer-Moore majority vote algorithm）可以解决绝对众数问题及相关问题。

定义

绝对众数：长度为 $n$ 的数列中出现次数严格大于 $\left\lfloor\frac{n}{2}\right\rfloor$ 的数。

「$\frac{1}{k}$ 众数」：长度 $n$ 的数列中出现次数严格大于 $\left\lfloor\frac{n}{k}\right\rfloor$ 的数。特殊地，当 $k = 2$ 时「$\frac{1}{2}$ 众数」即为绝对众数。

基本原理

摩尔投票法：对于一个长度为 $n$ 的数列 $\{a_{i}\}$，每次选出两个不同的元素并删除，直到无法删除为止。如果此时数列为空，则原数列不存在绝对众数，否则原数列的绝对众数为剩下的数（这些数字一定相同）。

例题

「BZOJ 2456」mode

求全局的绝对众数，保证存在。

空间限制 $1 \texttt{MB}$。

记录当前剩余数字 $num$ 和剩余个数 $cnt$。对于新的一个数字 $x$：

• 存在剩余数字即 $cnt > 0$ 时，

  • 如果 $x = num$，则 $cnt \leftarrow cnt + 1$；
  • 否则，则将一个 $num$ 和 $x$ 删去 $cnt \leftarrow cnt - 1$。
• $cnt = 0$ 时，说明之前的部分不存在绝对众数，那么这个众数一定在剩余部分中为绝对众数，重新回到了原问题，$num \leftarrow x, cnt \leftarrow 1$。

「Codeforces 674G」Choosing Ads

求区间出现频率不小于 $p \%$ 的数。

$20 \le p \le 100$。

将摩尔投票法扩展一下，每次删除 $k$ 个不同的数，就能够求解「$\frac{1}{k}$ 众数」了。

又发现这个过程是有可合并性的，用线段树维护这个过程即可。

区间合并的复杂度为 $\mathcal O(k^{2})$，由于 $k_{\max} = \frac{100}{p} = 5$，复杂度接近常数因此可以暴力合并。