题解：AT_joisc2019_j ケーキの貼り合わせ (Cake 3)

· · 题解

发现决策单调性之后这题简直就是整体二分和主席树的板子题，这里说说一个简单严谨的证明。

假设已经按照颜色排好序。

定义区间 [l, r] 的决策是在这中间选出 m 个 v 值最大的元素的过程，而 f(l, r) 表示 [l, r] 决策的值。最优决策则为左端点固定时，f 值减去颜色差值最大的选法。

考虑两个决策：[l_1, r_1] 和 [l_2, r_2]。不妨假设 l_1 < l_2 且 [l_1, r_1] 是以 l_1 为左端点的最优决策。如果 r_2 < r_1，我们要证明 [l_2, r_2] 必然不是最优决策。

首先证明一个引理：考虑一个分割点 lim，则对于两个相交的最优决策 [l_1, r_1] 和 [l_2, r_2]，若有 l_1 \leq l_2 \leq lim，则前者决策在 lim 前选的元素个数不小于后者决策，lim 后则相反。

道理也不难理解，考虑用堆动态维护前 m 大的过程即可。既然前者在 lim 之前有更多选择，那么之后加入新元素的过程中，若 lim 前元素被替换，则后者决策一定也有元素被替换了。

回到正题，用引理考虑 [l_1, r_1] 和 [l_2, r_2]，如果后者也是最优决策，设 lim = r1，则根据引理，(lim, r_1] 中选的个数不大于 (lim, r_2] 中选的个数。

但我们发现 lim = r_2，也就是说 (lim, r_2] 中选了 0 个元素。那么 (lim, r_1] 这一段也选了 0 个元素，根本没有存在的必要，删去这一段颜色差还可能变小，有矛盾了。

因此这个问题存在决策单调性，直接整体二分即可。