题意
给定一个序列,表示 \(n\) 个人每个人给 \(a_i\) 投了一票。
每次操作给定序列 \([l, r]\),求 \([l, r]\) 的众数。
若 \([l, r]\) 没有绝对众数则令该区间的众数为 \(p\),并将随后给定的 \(k\) 个整数,\(a_{s_1}, a_{s_2}, ... a_{s_k}\) 改为 \(p\)。
Sol
摩尔投票。
一句话总结,就是设二元组 \((x, y)\),表示当前数为 \(x\),权值为 \(y\)。
若合并两个二元组 \((x_1, y_1), (x_2, y_2)\) 取 \(y\) 较大的 \(x\),\(y\) 相减,若 \(x\) 相同,则 \(y\) 相加。
这个玩意显然是满足结合律的。
考虑使用线段树维护这个东西。
但是有个问题,摩尔投票保证若 区间有众数 则留下的一定是众数,若区间没有众数,求出来的不一定是众数。
可以考虑用一颗平衡树判断每一次操作的是否是区间的众数。
复杂度:\(O(n \log n)\)
标签:二元,选举,总统,摩尔,给定,P3765,众数,区间 From: https://www.cnblogs.com/cxqghzj/p/18171259