CF1514D Cut and Stick 题解

不知道会不会更不好的阅读体验

题目的关键步骤为求出区间绝对众数（频率高于 \(\left \lceil \frac{len}{2} \right \rceil\)）的出现次数，本文仅仅对这一问题进行探讨，剩余的解题步骤不难理解，可以参考其他题解。

解法 1

考虑一个随机化的解法，从区间中随 \(40\) 个数，假定其为区间绝对众数，然后对所有的情况取频率最大的那个。

若区间绝对众数存在，其一次被选中的概率为 \(\frac{1}{2}\)，\(40\) 次被选中过的概率则为 \(1-2^{-40}\)，错误概率极小，可以接受。

区间统计一个数字的出现次数也并不需要 \(O(n)\) 遍历，注意到值域不大，我们对每个值开一个 vector 记录它所有出现的下标，则区间出现次数只需要二分左右端点：

upper_bound(r) - lower_bound(l)

code

这样我们用 \(O(n \log n)\) 的时间复杂度解决了问题，但是带一个 \(40\) 的常数，跑起来可能和根号差不多。

解法 2

前置知识：摩尔投票。

在做摩尔投票的过程中，我们维护了两个变量 \(val,cnt\)。既然题目涉及区间查询，我们考虑把这两个值丢到线段树上。

在合并左右区间信息时，若左右区间的投票均选出一个 \(val\)，则合并后的区间 \(val\) 不变，\(cnt\) 加和。否则选出 \(cnt\) 更大的并把另一个区间的负贡献加入。

时间复杂度 \(O(n \log n)\)。

code