题解：P11103 [ROI 2022] 挑战 (Day 2)
Felix72
·
·
题解
对于 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，因此加上历史最值。