自动搬运

查看原文

来自洛谷，原作者为

	Felix72 公式和原理永远无法推论人情。

搬运于2025-08-24 23:04:15，当前版本为作者最后更新于2025-08-18 16:36:55，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

对于 $t = 0$ 的情况，我们可以使用最大流求解。考虑模拟网络流，由于网络流的图可以转化为二分图，因此 $\text{Hall}$ 定理适用，即最大流为 $\sum c - \max(\sum_{i \in S} c_i - \sum_{i \in P(S)})$，其中 $S$ 是一些区间的集合，$P(S)$ 是这些区间覆盖到的位置。

尝试 DP 出 $\max(\sum_{i \in S} c_i - \sum_{i \in P(S)})$。$P(S)$ 可以分为若干极长连续段，不妨从这个角度 DP。设 $w(l, r) = \sum_{i | [l_i, r_i] \sube [l, r] c_i} - \sum_{i = l}^{r} a_i$，$w$ 可以使用数据结构扫描线维护，则可以边扫描线边 DP 了。

若考虑 $t = 1$ 的情况，则可以分类讨论：

• 如果我们要计算的 $w(l, r)$ 中没有任何一个 $(l, r)$ 满足 $l \leq x \leq r$，则 $t = 1$ 的区间对贡献没有影响，按照 $t = 0$ 做就可以；
• 否则我们要计算的形如 $w(l, r) + f_{l - 1} + g_{r + 1}$，其中 $f, g$ 是前后缀的只考虑 $t = 0$ 的 DP 值。

我们要对每个 $x$ 计算 $\max\{f_{l - 1} + w(l, r) + g_{r + 1} \ | \ l \leq x \leq r\}$。仍然是扫描线维护。但因为查询的范围形如 $l \leq x$ 且 $r \geq x$，因此加上历史最值。