题解：P11630 [WC 2025] 士兵（暂无数据）

· · 题解

先考虑 \mathcal O(nV) 做法：f_{i,j} 表示 i 位置减了 j 次的最大收益，转移就是从 f_{i-1,k} 讨论，如果 k<j 需要产生 (k-j)m 的收益；否则可以直接掉下来。对于 j\ge a_i 需要加上 b_i。不难发现你需要做出的是将 i 移出代价或者加入代价，因此所有有用的 j 为 a_i,a_i-1 构成的集合，加上一个 0，可以做到 \mathcal O(n^2)。对于一个方案，你发现其有用的地方当且仅当它将 a_i 移出/加入了代价，否则可以调整到后面去修改而代价不变。因此每次只需要修改 j=a_i,a_i-1 的点值。线段树维护求单点 f_{i,j} 做到 \mathcal O(n\log n)。

下面是我的赛时做法，很遗憾由于很晚开始写导致最终并没有调试完。

另一个做法是直接维护 f。转移是：f_{i,j}=\max(f_{i-1,k}-\max(j-k,0)m)+[j\ge a_i]b_i。我们拆成三步：先对 f 修改为其后缀 \max，再对 f'_i=\max_{j\leq i} (f_j+jm)-im，这一步等价于正序扫描 i，令 f_i=\max(f_{i-1}-m,f_i)。正确性其实是有的，如果一个后缀 \max 被丢到前面算了只会被算小。最后一步：对于 f 下标 \ge a_i 的部分整体加上 b_i。这个很像 slope trick 啊，场上我就会了维护差分的做法。也就是说令 diff_i=f_{i}-f_{i-1}，我们观察 diff 序列的变化：对于第一步，修改为后缀 \max，等价于对 diff_i 所有数对 0 取较小值。对于第二步：等价于所有数对 -m 取较大值。第三步：单点修改 diff_{a_i}\to diff_{a_i}+b_i。这是线段树容易维护的，每次线段树二分找到不符合条件的这个区间进行修改，由于只有第三步可能破坏这个东西，这是 \mathcal O(1) 影响的，所以总修改次数正确的。时间复杂度 \mathcal O(n\log n)。等一下这不就是维护颜色段吗。

提交记录