CF1514D

· · 题解

本文摘自 可持久化数据结构

这种众数题又不带修首先考虑主席树吧。

但我们目前还不知道怎么使用它，先放着。

考虑刻画一个合法区间的形态：若一个区间内有 tot 个「目标众数」（即严格大于区间长度一半向上取整的数），则必定有 tot-1 个非「目标众数」与之抵消。

接着，我们考虑划分的最优策略：显然对于每个众数分一个集合是最劣的，我们考虑两两进行合并。对于两个集合 tot_1,tot_1-1，和 tot_2,tot_2-1（前者为「目标众数」，后者为非「目标众数」），它们合并之后为 tot_1+tot_2,tot_1+tot_2-2，这并不符合要求。应该扔掉一个「目标众数」才行。这样，原先是两个集合，现在还是两个集合，这是最劣的情形。当「目标众数」很少时，还有可能更优。这便说明，合并两个集合不会更劣。

（这里补充一下，为什么每个集合都是形如 tot,tot-1，这是因为，给每组「目标众数」都分配最少的非「目标众数」，则后面的其他「目标众数」将会有更多的选择，这是贪心的思想。）

得出上述结论后，考虑把所有集合合并到一块，即所有非「目标众数」均分布在一个集合内，这样必定是最不劣的。令「目标众数」有 tot 个，此时除了那个集合能够抵消的「目标众数」外，其余的必须自成一个集合，则答案即为

1+tot-(r-l+1-tot+1)\\ =2 \times tot-(r-l+1)

后面那部分是一定的，我们仅需求出 tot 即可，这就是主席树干的事情了，在线段树上二分即可（就是看左边的个数大于区间长一半就去左边，反之去右边，如果都不行就无解）。

实现是简单的。

总结：众数不带修考虑主席树；刻画答案；往最优化的方向思考。