士兵 WC2025 & CTS2025

[WC2025] 士兵 & [CTS2025] 士兵

简单题，（还有抄袭环节）

题目链接： [WC2025] 士兵 和 [CTS2025] 士兵 。

题目描述：

有长度为 $n$ 的序列 $a,b$ ，一次操作中你可以任意指定区间 $[l,r]$ 并令 $[l,r]$ 内的 $a$ 全部 $-1$ 。你可以进行任意次操作。设你进行了 $k$ 次操作，则这些操作的总权值为 $(\sum [a_i\le 0]b_i)-km$ ，你需要最大化权值。

$n\le 5\times10^5,a_i\le 10^9,-10^9\le b_i\le 10^9$ 。

经典转化。首先将 $[l,r]$ 的区间减法转化为差分数组上的 $+/-$ 。那么容易设计出 $f_{i,j}$ 表示前 $i$ 个数，第 $i$ 个数的差分数组上的前缀和为 $j$ 的最大权值，则有：

$$f_{i,j}=b_i[a_i\le j]+\max_k\{f_{i-1,k}-m\times\max\{0,j-k\}\}$$

直接 DP 复杂度 $\mathcal{O}(nV)$ ，可以拿到 $15\%$ 的分数。

这个 DP 的状态很显然有大量浪费。比如说一个小数据中 $f_{1,100}$ 很显然是一个没有任何用处的状态，于是考虑离散化。

问题在于，我们究竟要离散化哪些值。所有的 $a_i$ 肯定要离散化的，然而这是错的。通过对拍我发现要离散化 $a_i-1$ 。道理不难想，因为可能某一个 $i$ 的 $b_i=-10^9$ ，但又必须把 $i$ 两边的值打下 $0$ ，所以必须把他控制在 $1$ 。

这样复杂度就被优化为 $\mathcal{O}(n^2)$ ，可以获得 $35\%$ 的分数。

再次观察 DP ，容易发现，对于 $i$ 的转移，差分数组上的 $+/-$ 只有可能在 $j=a_i$ 或 $j=a_i-1$ 时发生，因为其他的在这里发生必然更劣。于是单次更新就只用更新 $2$ 个点值，但仍然无济于事。

观察一下 DP 的转移，不妨把 $\max$ 拆开为 $j\le k$ 和 $j>k$ 两种情况：

Case #1: $j\le k$

此时比较简单，因为 $f_{i,j}=b_i[a_i\le j]+\max\limits_{j\le k}{f_{i-1,k}}$ ，这个直接线段树上区间加以及区间 max 即可解决。

Case #2: $j>k$

此时有些复杂，因为 $f_{i,j}=b_i[a_i\le j]+\max\limits_{j> k}{f_{i-1,k}-m(j-k)}$ ，看起来很不可做。不过我们可以大便分离，得出 $f_{i,j}+mj=b_i[a_i\le j]+\max\limits_{j> k}{f_{i-1,k}+mk}$ ，此时的形式恰好统一了！于是我们可以令 $g_{i,j}=f_{i,j}+mj$ ，那么我们就可以在 $g$ 上得出和 Case #1 一样的转移，只需要维护区间加和区间 max 就行。

最终我们需要两颗线段树分别维护 Case #1 和 Case #2 ，然后就解决了（这也配 T3 ）。