CF643G Choosing Ads 6k大常数题解

Rain_chr · 2024-07-24 14:55:52 · 题解

前言：自己想了两个小时胡的做法，发现复杂度与已有题解全部不同，并且这个做法能保证输出的一定是正确的数字，所以写一篇题解纪念一下。

首先我们可以需要提出一个结论：

如果一个长为 len 的区间，x 出现的次数超过区间长度的 p%,那么把这一个区间拆成任意两个部分 len_1 和 len_2，至少存在一个子区间使得 x 出现的数超过区间长度的 p%。

证明：

考虑最坏的情况，x 在原区间中恰好有 \lceil len\times p \rceil 个，拆到两个部分的 x 分别为 a,b，即需要说明：

尝试反证

假设这个结论不成立，那么首先有 \frac{a}{len_1}<p，即 a<len_1\times p

其次有 \frac{b}{len_2}<p，即 \frac{\lceil len\times p \rceil-a}{len-len_1}<p，拆开式子得到 \lceil len\times p \rceil-a < p \times len-p\times len_1，即 p\times len_1-a < p \times len-\lceil len\times p \rceil

如果 a=0，很明显第二个区间 x 出现次数一定超过 p%

否则，因为有 a<len_1\times p，所以这个式子不成立。

综上，矛盾，得证。

有了这一个结论，我们就可以用线段树维护每一个区间中出现次数大于 p% 的元素。由于上述结论，当前区间的答案一定出现在两个子区间中，所以只需要对于每一个子区间中的元素查询在当前区间的出现次数，统计合法元素并去重即可。

现在的问题就是，怎么计算每种元素在一个区间的出现次数？这个可以直接颜色段均摊，再用权值线段树维护一下即可。

总复杂度 O(n\log^2 n k),k=\lfloor \frac{100}{p} \rfloor

此算法是确定性算法，且输出答案一定满足条件。