2024.8 #5 午夜时分月上枝头 谁为谁心疼 一杯浊酒浇在心头 谁让谁心冷

午夜时分月上枝头
谁为谁心疼
一杯浊酒浇在心头
谁让谁心冷----洛天依《广寒宫》

1.Choosing Ads

考虑最简单的情况，即 \(p > 50\)。那么这个问题就是请问出现次数 \(> \dfrac{n}{2}\) 的数。

Lemma：我们每次随机删除不相等的两个数，那么留下来的那个（那些）数就是答案。

Proof：假如答案 \(x\) 出现了 \(a\) 此，那么就有 \(a > n - a\)。那么假如删除了一个 \(x\) 和另外一个数，那么两边都减一，则 \(a - 1 > n - a - 1\)。那么如此，到最后的数就是答案。

那么我们扩展到 \(p\) 更小的情况，我们每一次删除 \(\lfloor \dfrac{100}{p} \rfloor + 1\) 个数，那么最后剩下的数就是答案。同时我们知道 \(p \ge 20\)，那么我们只会留下 \(5\) 个数，那么我们用一颗线段树来维护这五个值。

对于合并两个区间，我们可以直接暴力和并这 \(5\) 个数。那么复杂度就是 \(\mathrm O(n \log n)\)。