摩尔投票法
stripe_python · · 算法·理论
:::::info[] 其实只是一种半群信息的构造方法。 :::::
定义绝对众数为出现次数超过一半的数。
注意到如下事实:每轮消去一个绝对众数和一个其余元素,最后剩下的一定是绝对众数。
考虑模拟上述过程。维护二元组
新元素
- 若
\text{val}_1=\text{val}_2 ,票数相加为(\text{val},\text{cnt}_1+\text{cnt}_2) 。 - 若
\text{val}_1 \ne \text{val}_2 ,取票数较大者,并做抵消操作。- 若
\text{cnt}_1 \ge \text{cnt}_2 ,合并为(\text{val}_1,\text{cnt}_1-\text{cnt}_2) 。 - 若
\text{cnt}_1 < \text{cnt}_2 ,合并为(\text{val}_2,\text{cnt}_2-\text{cnt}_1) 。
- 若
上述过程称为摩尔投票法。若序列存在绝对众数,则对其做摩尔投票后,所得的
考察
P3765 总统选举
维护一个长为
n 的序列a_i ,支持q 次操作:
- 给定
i,x ,令a_ i \gets x 。- 给定
l,r ,查询[l,r] 的绝对众数,或报告不存在。
:::::success[题解]
若绝对众数存在,则可以用线段树维护摩尔投票解决。
对于摩尔投票得到的答案
复杂度
:::::
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[题解]
考虑对每个数组开一棵权值线段树
删除操作需要知道删掉了什么数,可以使用双向链表维护数组
视
:::::