题解：AT_agc049_e [AGC049E] Increment Decrement

· · 题解

铜牌题。

这个题目需要一个基本结论：通过 3 操作完成一个序列的代价是 C\sum \max(a_i-a_{i-1},0)。

我们可以钦定先做区间、再做单点修改。

那我们考虑先对一个序列做 dp，不妨把状态想得暴力一点，设 f_{i,j} 为当前计算了前 i 个位置，第 j 个位置在区间操作之后为 c_i。

那么转移方程就是 f_{i,j}=|a_i-j|+\min_k (f_{i-1,k}+C\max(j-k,0))。

然后我们这个地方要用 slope trick 优化了。我之前没有学过这个，所以现在学一下。

学完了。我们考虑分步进行这个转移的过程，首先进行 f_{i,j}\leftarrow \min(\min_{k\leq j} f_{i-1,k}+C(j-k),\min_{k>j} f_{i-1,k})。

考虑对于 k>j 的情况，实际上只需要考虑左半边（单调递减），发现可以全部推平为最小值；

对于 k<j 的情况，我们考虑什么时候可以更新，首先显然是只有右半边需要考虑。可以先把所有 f_{i,j} 置为 f_{i-1,j}，然后考虑要满足 f_{i-1,j}>f_{i-1,k}+Cj-Ck，整理一下就是 f_{i-1,j}-Cj>f_{i-1,k}-Ck，这个可以用函数 f^\prime(i)=f(i)-Ci 来表示，f^\prime(i) 实质上就是原函数所有的直线斜率减少 C，而不等式的意义是 f^\prime(j)>f^\prime(k)。考虑不等式满足的条件，发现新的零点就是原来斜率为 C 的直线的右端点，因此可以用这个零点去更新斜率 >C 的位置，即全部推平。至于为什么不能使用新零点左边的点来更新的原因是，我们发现左侧斜率 \leq C，而附加代价的变化率就是 C 了，因此向左一定不优。

然后对于 |a_i-j| 的贡献的维护就是老生常谈了，往维护的容器里塞两个 a_i 即可。

我们注意到，根据更新操作的特点，实际上斜率总是 \in [-1,C+1]。那我们考虑使用 multiset 维护斜率集合，操作可以如下刻画：

现在，我们可以 O(n\log n) 地解决这个子问题了。

考虑整个流程，即加入 C+2 个 0 之后要循环做的事情：

删去最大值和最小值，加入两个 a_i，ans\leftarrow a_i-\min。

考虑拆开做，首先计算 a_i 部分的贡献系数。由于选了 a_i 之后可以随便选，都能产生贡献，因此贡献系数为 K^{n-1}。

考虑统计所有情况下的 p 之和。这里就需要一些 trick 了，首先考虑从值域出发，枚举所有可能的 p，计算最小值 \leq p 和 <p 的方案数的差值，就是 p 的贡献系数。这样，就把统计的单点问题转化成区间问题了，而我们也就不关心最大值的情况了。

那我们考虑将问题进一步简化为 01 问题，这样的好处是将 multiset 的维护转化成了单个变量（1 的个数）的维护问题了。不妨让 a_i\leftarrow [a_i\geq p]，这样相当于如果有 0，那么最小值 <p 成立。

考虑何种情况下最小值不为 0。发现每次删除最小值时都会删掉一个最初加上的 0（第一轮会删掉两个），因此 C+1 轮之后如果此前全都有 a_i=1，那么在第 C+2 轮时如果 a_i=1 那么本轮会出现一次这样的情况。也就是说，当出现 C+2 个 a_i=1 时才能满足条件。此后如果一直满足 a_i=1 那么 1 的数量就会维持在 C+2（全部为 1），于是可以据此 dp。

设 f_{i,j} 为前 i 个位置，1 的数量为 j，那么最小值为 1 的方案数就是 \sum\limits_{i=1}^n K^{n-i} f_{i,C+2}；可以容斥一下，总方案数是 nK^n，即每个位置都有 K^n 种情况产生或者不产生贡献，这样两个值相减就得到了所有位置满足最小值 <p 的方案数之和 \sum\limits_{i=1}^n K^n-K^{n-i}f_{i,C+2}。

现在考虑如何转移。考虑当前的 f_{i,j} 向后进行第 i+1 轮的转移，先删去最大值和最小值，即 j\leftarrow j-[j>0]-[j=C+2]。

然后枚举可选的 K 种 a_i，注意它们本质的不同只在于与 p 的关系，即有多少个当前能作为 1，剩下的作为 0。

这样，我们 dp 的复杂度就是 O(n^2CK)，这也是总时间复杂度。