E. Linear Kingdom Races 详细题解

题目重述

有 $n$ 条道路（编号 $1$ 到 $n$），修复道路 $i$ 需要花费 $c_i$（非负整数）。有 $m$ 个比赛，每个比赛是一个区间 $[l, r]$，如果举办该比赛可以获得收益 $p$。举办比赛的前提是区间内所有道路都被修复。你可以任意选择修复哪些道路（不修复也可），目标是最大化 总收益 − 总修复花费。允许不举办任何比赛，此时利润为 $0$。

数据范围：$n, m \le 2\times 10^5$，$c_i, p \le 10^9$。

核心思路

这是一道典型的 DP + 线段树优化 问题。
设 $dp[i]$ 表示只考虑前 $i$ 条道路（即道路 $1 \dots i$）时，能获得的最大利润。注意 $dp[i]$ 中道路 $i$ 必须被修复（因为我们要用最后一个位置强制修复来辅助转移）。但最终答案允许最后一条路不修复，因此答案需要对所有 $dp[i]$ 以及 $0$ 取最大值。

状态转移

考虑 $dp[i]$ 怎么计算。
如果修复了道路 $i$，那么我们可以选择是否举办一些以 $i$ 为右端点的比赛。设 $S_i$ 表示所有右端点 $\le i$ 的比赛集合。为了计算 $dp[i]$，我们可以枚举上一个“修复”的位置 $j$（$0 \le j < i$），其中 $dp[j]$ 已经计算好，且道路 $j$ 被修复（$j=0$ 表示没有道路）。那么区间 $(j, i]$ 内的道路我们都可以自由决定是否修复，但为了获得这些比赛的收益，我们必须修复它们覆盖的所有道路。

更好的表述是：当我们从 $j$ 转移到 $i$ 时，我们考虑所有右端点 $\le i$ 且左端点 $> j$ 的比赛。这些比赛完全位于 $(j, i]$ 内，因此如果要举办它们，需要修复它们覆盖的所有道路，而修复成本已经在 $dp$ 中通过前缀和扣除。具体地：

设 $pre[i] = \sum_{k=1}^i c_k$ 为修复前 $i$ 条道路的总费用。
如果我们强制修复了道路 $i$，并选取了某个 $j$ 作为上一个被修复的道路（$j=0$ 表示之前没修复过任何路），那么区间 $(j, i]$ 内的道路都可能被修复（实际上我们可以选择只修复其中一部分，但为了举办比赛，所有被覆盖的道路都必须修，这会导致额外费用）。真正计算收益的常见技巧是：

定义：令 $f[i]$ 表示考虑前 $i$ 条道路，且道路 $i$ 必须被修复 时的最大利润。
转移时，枚举上一个被修复的位置 $j$（$0 \le j < i$），那么：

• 我们修复了所有道路 $(j, i]$（因为 $i$ 修复了，$j$ 修复了，中间的不能有缺口？实际上为了简化，我们强制区间 $(j, i]$ 全部修复——这是关键，因为如果某个 $k$ 在 $(j,i)$ 中没有被修复，那么任何跨越它的比赛都无法举行，但我们可以通过将 $j$ 设为最后一个修复点来涵盖。）

更常用的状态设计是：$dp[i]$ 表示考虑前 $i$ 条道路，并且第 $i$ 条道路被修复时的最大利润。那么转移时，我们考虑上一个被修复的道路 $j$（$0 \le j < i$），那么区间 $(j, i]$ 内的道路都被修复（因为 $j$ 和 $i$ 都修复了，但中间如果有的没修复，其实是不允许的，因为如果有比赛要求修复那些路就不能办。然而我们可以通过调整 $j$ 来避免中间的缺口。实际上这个 DP 隐含了“所有被修复的道路是连续的若干段”的假设吗？不，比赛不要求所有道路都修复，只要求比赛区间内全部修复。所以中间的缺口可能被允许，但转移时我们要考虑的是：以 $i$ 结尾的所有比赛，它们可能覆盖到更左的位置，所以我们需要在 $j$ 处加一个“分隔”。

更精妙的方法是使用扫描线 + 线段树。设 $dp[i]$ 如上定义。我们维护一个数组 $g[j] = dp[j] - pre[j]$，其中 $pre[j]$ 是修复前 $j$ 条道路的累计花费。那么对于每个 $i$，考虑所有以 $i$ 为右端点的比赛 $(l, i, p)$。这些比赛如果能举办，需要修复 $[l, i]$ 之间的所有道路，也就意味着上一个修复点 $j$ 必须 $< l$（因为如果 $j \ge l$，那么 $l$ 到 $i$ 之间的道路会被修复吗？不一定，但如果我们把 $j$ 视为上一个修复点，那么从 $j+1$ 到 $i$ 必须全部修复才能举办此类比赛。因此对于每个比赛，它对所有 $j \le l-1$ 的转移贡献 $+p$。

于是转移方程可以写为：

$$dp[i] = \max\left(0,\ \max_{0 \le j < i} \left( dp[j] - (pre[i] - pre[j]) + \sum_{(l, i, p) \text{ with } l > j} p \right) \right) $$

其中 $dp[0]=0$，$pre[0]=0$。
整理得：

$$dp[i] = \max\left(0,\ \max_{0 \le j < i} \left( (dp[j] + pre[j]) + \left( \sum_{l>j} p - pre[i] \right) \right) \right) $$

定义 $val[j] = dp[j] + pre[j]$。那么对于固定的 $i$，我们需要对所有 $j < i$ 计算 $val[j] + sum_{l>j} p$，其中求和只考虑右端点为 $i$ 的比赛且左端点 $l > j$。如果我们能动态维护这个最大值，就可以用线段树实现。

线段树维护技巧

我们按 $i$ 从 $1$ 到 $n$ 扫描。开始时，线段树在位置 $j$ 存储 $val[j]$。当处理到 $i$ 时：

1. 对于每个以 $i$ 为右端点的比赛 $(l, i, p)$，它对所有 $j < l$（即左端点 > j）的转移有贡献，相当于对区间 $[0, l-1]$ 整体加上 $p$。
2. 然后整个线段树的最大值就是 $\max_{j < i} (val[j] + \text{当前积累的贡献})$，记为 $best$。
3. 则 $dp[i] = best - pre[i]$。注意 $dp[i]$ 可能小于 $0$，我们可以选择不修复 $i$，所以 $dp[i] = \max(0, best - pre[i])$。
4. 最后，将 $val[i] = dp[i] + pre[i]$ 插入到线段树的位置 $i$ 上（实际上是更新该位置的值，因为之前该位置是 $-\infty$）。

最终答案等于 $\max(0, dp[1], dp[2], ..., dp[n])$，因为最后一条道路可以不修复。

算法步骤

1. 读入 $n, m$，读入修复费用 $c[1..n]$，计算前缀和 $pre[i]$。
2. 将比赛按右端点分组：races[r].push_back({l, p})。
3. 建立线段树，初始时位置 $0$ 值为 $val[0]=dp[0]+pre[0]=0$，其他位置为 $-\infty$。
4. 循环 $i = 1$ 到 $n$：
   • 对于 races[i] 中的每个比赛 (l, p)，在线段树上对区间 $[0, l-1]$ 加上 $p$。
   • 查询线段树全局最大值 best。
   • 计算 dp[i] = max(0, best - pre[i])。
   • 将位置 $i$ 的值设置为 dp[i] + pre[i]（如果比当前值大，实际上直接覆盖，因为之前是负无穷）。
5. 答案为 $\max(0, \max_{1\le i\le n} dp[i])$。

时间复杂度

• 对比赛进行分类：$O(m)$。
• 每个比赛执行一次区间加操作：$O(\log n)$，总 $O(m \log n)$。
• 每个 $i$ 查询一次最大值和一次点更新：$O(\log n)$，总 $O(n \log n)$。
• 总复杂度 $O((n+m) \log n)$，满足 $2\times 10^5$ 的数据范围。

正确性证明

• 我们维护的 $val[j] = dp[j] + pre[j]$ 表示：如果上一个修复点是 $j$，且修复了 $j$，那么到目前 $i$ 为止，不包含任何右端点 > i 的比赛时，已经获得的收益基础值。
• 每当加入一个以 $i$ 为右端点的比赛时，所有 $j < l$ 的转移都可以获得这个比赛的收益，因此对 $[0, l-1]$ 区间加 $p$。
• 线段树维护的是 $\max_{j \le i-1} (val[j] + \text{当前累积的收益})$，即最优的 $j$ 对应的值（其中 $j$ 是合法转移点）。
• 减去 $pre[i]$ 得到 $dp[i]$，因为修复 $1..i$ 需要花费 $pre[i]$，而 $dp[j]$ 已扣除了 $pre[j]$，所以 $val[j] - pre[i] = dp[j] - (pre[i]-pre[j])$，正好是修复 $j+1..i$ 的净花费。
• 允许 $dp[i]$ 为负时取 $0$，表示不修复道路 $i$ 甚至放弃这个转移。
• 最终答案对所有 $i$ 取最大，是因为可以不修复最后一条路，所以利润可能出现在任何 $dp[i]$ 或 $0$。

关键点总结

• 状态定义 $dp[i]$：强制修复第 $i$ 条路时，前 $i$ 条路的最大利润。
• 转化：$val[j] = dp[j] + pre[j]$，利用前缀和统一处理修复费用。
• 动态维护：扫描右端点，用线段树维护区间加（比赛收益）和全局最大值查询。
• 最终答案：取所有 $dp[i]$ 和 $0$ 的最大值。

这道题是 DP 优化与区间操作的经典结合，线段树在其中起到了关键的加速作用。