AGC049E 题解

EuphoricStar · 2023-07-19 21:26:52 · 题解

好题。同时考查了 slope trick 和选手的计数能力，不愧是 AGC E。

先考虑问题的第一部分。

你现在有一个初始全为 0 的序列 b。你每次可以给 b 单点 \pm 1，代价为 1，或区间 \pm 1，代价为 m。求把 b 变成给定序列 a 的最小代价。

考虑先执行区间加减操作，设操作完的序列为 c，那么之后单点加减操作的代价就是 \sum\limits_{i = 1}^n |c_i - a_i|。对 c 差分，可以发现最少的区间操作次数就是差分后数组的正数项的值的和。所以总代价就是 \sum\limits_{i = 1}^n |c_i - a_i| + m \sum\limits_{i = 1}^n \max(c_i - c_{i - 1}, 0)。

考虑 dp，设 f_{i, j} 为 c_i = j 的最小代价（显然最优时 c_i \ge 0）。初始有 \forall i \ge 0, f_{0, i} = mi。转移枚举 c_{i - 1}，可得：

看到转移式里面有计算绝对值，联想到 slope trick。发现 f_i 是凸函数，并且每段的斜率在 [-1, m + 1] 之间。容易归纳，我们初始的图像是一条斜率为 m 的射线，然后我们先进行 f_{i, j} \gets \min\limits_k f_{i - 1, k} + m \max(j - k, 0) 的更新，这个更新产生的影响就是，斜率为 -1 的段被拍平（斜率变成 0），斜率为 m + 1 的段斜率变成 m。然后我们给这个图像整体加上 |a_i - j| 的分段函数，也就是把 \le a_i 的段斜率减少 1，> a_i 的段斜率增加 1。

考虑运用 slope trick，用 multiset 维护这个分段函数。回忆一下在 slope trick 中，我们维护的是分段函数图像变化的断点，并且一个断点代表斜率增加 1。那么在这题中，我们初始往 multiset 添加 m 个 0 代表断点为 0 且斜率为 m，然后当 i = 1 时，因为图像不存在斜率为 -1 或 m + 1 的段，因此我们不需要进行删除操作，直接添加两个 a_i 表示 a_i 处斜率变化为 2。当 i > 1 时，我们先删除 multiset 中的最小值和最大值表示这两个断点被拍平了，不存在了，再添加两个 a_i。

至于统计答案，我们在每次添加两个 a_i 后统计，此时 multiset 中的最小值就是斜率 -1 \to 0 变化的断点，因此我们把答案累加 a_i - p，其中 p 为 multiset 中的最小值（不用加绝对值是因为此时加入 a_i 后 p 一定 \le a_i）。

于是我们现在可以 O(n \log n) 求解这个问题了。

考虑问题的第二部分，即统计所有可能的 a_i 对应的答案之和。

考虑我们上面的算法流程。

初始往 multiset 中添加 m 个 0。i = 1 时，往 multiset 中添加 2 个 a_i，然后计算 a_i - p，其中 p 为 multiset 中最小值；i > 1 时，先删除 multiset 中的最小值和最大值，然后往其中添加 2 个 a_i，再计算 a_i - p。