摩尔投票法

· · 算法·理论

:::::info[] 其实只是一种半群信息的构造方法。 :::::

定义绝对众数为出现次数超过一半的数。

注意到如下事实:每轮消去一个绝对众数和一个其余元素,最后剩下的一定是绝对众数。

考虑模拟上述过程。维护二元组 (\text{val},\text{cnt}),其中:

新元素 x 可以被视作二元组 (x,1)。对 (\text{val}_1,\text{cnt}_1) 和 (\text{val}_2,\text{cnt}_2),对信息的合并进行讨论:

上述过程称为摩尔投票法。若序列存在绝对众数,则对其做摩尔投票后,所得的 \text{val} 即为绝对众数。否则 \text{val} 是无效值。

考察 (\text{val},\text{cnt}) 合并满足结合律、交换律,且有单位元 (\text{null}, 0)。故称摩尔投票信息构成交换幺半群。这允许我们使用数据结构来维护绝对众数。

P3765 总统选举

维护一个长为 n 的序列 a_i,支持 q 次操作:

  • 给定 i,x,令 a_ i \gets x。
  • 给定 l,r,查询 [l,r] 的绝对众数,或报告不存在。

:::::success[题解]

若绝对众数存在,则可以用线段树维护摩尔投票解决。

对于摩尔投票得到的答案 \text{val},我们需要在 [l,r] 中查询其出现次数。可以对每个值开一棵平衡树,查询 l 和 r+1 的排名后相减得到。

复杂度 O(q \log n)。

:::::

P8496 [NOI2022] 众数

维护若干数组 a_i,支持 q 次操作:

  • 在数组 a_x 末尾插入数字 y。
  • 删除数组 a_x 的末尾数字。
  • 求数组 a_{x_1},a_{x_2},\cdots,a_{x_m} 顺次拼接后的绝对众数,不存在输出 -1。
  • 令数组 a_z 为数组 a_x,a_y 首尾顺次相接的结果,保证数组 a_x,a_y 之后不再使用。

:::::success[题解]

考虑对每个数组开一棵权值线段树 T_x,线段树上节点维护子树的摩尔投票信息并。查询操作将 T_{x_1} \sim T_{x_m} 的全树信息进行合并得到候选答案,然后在权值线段树上查询其出现次数即可回答询问。

删除操作需要知道删掉了什么数,可以使用双向链表维护数组 L_x。插入删除在对应链表上操作,并在权值线段树上更新。合并操作就是直接合并两个链表,同时做线段树合并。

视 n,q, \sum m,V 同阶,复杂度 O(n \log n)。代码。

:::::