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$ 个，此时除了那个集合能够抵消的「目标众数」外，其余的必须自成一个集合，则答案即为

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

实现是简单的。

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