题解

思路

令 $b_i=a_i\bmod k$，把生命值为 $k$ 看成 $0$。若第 $i$ 个位置一共被操作 $h_i$ 次，则必须有

$$h_i=b_i+q_i k,\qquad q_i\ge0.$$

一旦各个 $h_i$ 确定，用区间操作形成这个覆盖次数序列的最少操作数为

$$h_1+\sum_{i=2}^{n}\max(0,h_i-h_{i-1}).$$

因此问题变为：给每个 $b_i$ 加上非负整数倍的 $k$，使上述正差分之和最小。

做法

子任务 1：提升次数动态规划

对每个位置枚举提升次数 $q_i$。存在最优解满足 $0\le q_i\le n$：若某个连通段上的提升次数都超过 $n$，整体减去一层不会增加任何正差分；反复处理即可得到该界。

设 $dp_i(q)$ 表示处理到位置 $i$ 且 $q_i=q$ 时的最小代价，转移为

$$dp_i(q)=\min_p\left(dp_{i-1}(p)+\max(0,b_i+qk-b_{i-1}-pk)\right).$$

时间复杂度为 $O(n^3)$，空间复杂度为 $O(n)$。

子任务 2：模值非降

若 $b_1\le b_2\le\cdots\le b_n$，直接取所有 $q_i=0$，代价为 $b_n$。任何一次提升都会额外引入不少于原正差分的代价，不能得到更优结果。因此线性扫描即可。

子任务 3：反悔贪心

记 $b_0=0$，并从左到右处理差分 $d_i=b_i-b_{i-1}$。

若 $d_i\le0$，当前没有正差分贡献，但以后可以把一段前缀提升一层，把代价改为 $d_i+k$，于是将 $d_i+k$ 放入候选集合。

若 $d_i>0$，可以直接支付 $d_i$；也可以反悔，使用此前某个候选代价。把 $d_i$ 也放进候选集合，取集合最小值计入答案并删除它。候选集合用最小堆维护。

时间复杂度为 $O(n\log n)$，空间复杂度为 $O(n)$。

正确性证明

引理 1

固定覆盖次数序列 $h$ 后，最少操作数等于 $h_1+\sum_{i=2}^{n}\max(0,h_i-h_{i-1})$。

证明。 在位置 $1$ 必须开始 $h_1$ 个区间；从位置 $i-1$ 到 $i$，若覆盖次数增加，就必须再开始 $h_i-h_{i-1}$ 个新区间。这给出下界。让已有区间尽量向右延伸，并只在覆盖次数增加时开启新区间，恰能达到该下界。$\square$

引理 2

处理正差分 $d_i>0$ 时，所有尚未使用的直接方案和前缀提升方案中，选择最小代价不会损失最优性。

证明。 每个正差分都必须由一次直接支付或一次此前的前缀提升消除。所有候选只通过各自的两个边界影响正差分，内部差分不变；交换两个正差分所使用的候选不会改变后续可用候选集合。故当前选择最小代价满足交换论证。$\square$

定理

反悔贪心得到全局最少操作数。

证明。 引理 1 将原问题等价地化为最小化提升后序列的正差分和。扫描过程中，非正差分产生一个未来可用的前缀提升候选，正差分同时产生直接候选。由引理 2，每次取当前最小候选均可扩展为某个全局最优方案。归纳到全部位置，所得答案即全局最优值。$\square$

复杂度

满分算法对每个测试用例的时间复杂度为 $O(n\log n)$，空间复杂度为 $O(n)$；所有测试用例的 $n$ 之和不超过 $2\times10^5$。