题解 CF671E 【Organizing a Race】

· · 题解

先定义两个数组 \mathrm{pre}[i] 和 \mathrm{suf}[i]：

$\mathrm{suf}[i]$ 表示：从 $i$ 出发到 $1$ 需要花费多少单位的油（假设开始时油量充分大）。 则有 $\mathrm{pre}[i] = \mathrm{pre}[i - 1] - g_{i - 1} + w_{i - 1}$； 并且 $\mathrm{suf}[i] = \mathrm{suf}[i - 1] - g_i + w_{i - 1}$。 则从 $i$ 向右走到 $j$，需要花费的油量就是 $\mathrm{pre}[j] - \mathrm{pre}[i]$。 则从 $j$ 向左走到 $i$，需要花费的油量就是 $\mathrm{suf}[j] - \mathrm{suf}[i]$。 --- 然后我们考虑去计算一个区间 $[l, r]$ 的**代价 $\boldsymbol{w(l, r)}$：这个区间内需要给 $\boldsymbol{g}$ 增加多少才可以往返通行**。 如果 $w(l, r) \le k$，则这个区间就可以作为答案了。 先考虑从左往右开，从 $l$ 一直开到 $r$，中间可能会遇到一个位置开不过去了，令这个位置为 $\mathrm{next}[l]$。 也就是说从 $l$ 一直往右开，最多只能开到 $\mathrm{next}[l] - 1$ 的位置，而开不到 $\mathrm{next}[l]$。 则这个位置就必须满足 $\mathrm{pre}[\mathrm{next}[l]] > \mathrm{pre}[l]$，而且 $\mathrm{next}[l]$ 必须是满足这个条件的第一个位置。 **也就是说 $\boldsymbol{\mathrm{next}[i]}$ 为满足 $\boldsymbol{\mathrm{pre}[i] < \mathrm{pre}[k]}$ 且 $\boldsymbol{i < k}$ 的第一个 $\boldsymbol{k}$，可以通过单调栈求出**。 那么我们考虑令 $\mathrm{val}[i] = \mathrm{pre}[\mathrm{next}[i]] - \mathrm{pre}[\mathrm{next}[i] - 1]$，这也就是想要到达 $\mathrm{next}[i]$ 需要给 $g$ 增加的最小权值。 也就是说：想要到达 $\mathrm{next}[i]$，就必须在 $g_l \sim g_{\mathrm{next}[i] - 1}$ 之间增加至少 $\mathrm{val}[i]$，具体加在哪里没有影响。 但是考虑到我们还要回来，就是说要从 $r$ 向左回到 $l$，那么这个 $\mathrm{val}[i]$ 还是加在尽量靠右的位置比较好。 也就是说 $\mathrm{val}[i]$ 一定会全部加在 $g_{\mathrm{next}[i] - 1}$ 上，也就是说 $g_{\mathrm{next}[i] - 1} \gets g_{\mathrm{next}[i] - 1} + \mathrm{val}[i]$。 这样就能在最优情况下成功到达 $\mathrm{next}[i]$ 了，且此时油箱是空的，就可以继续处理 $\mathrm{next}[i] \to r$ 的子问题了。 这样处理完之后，可以求出从 $l$ 到 $r$ 的最小代价，**令它为 $\boldsymbol{\mathrm{cost}(l, r)}$**。 **但是此时不一定能成功从 $\boldsymbol{r}$ 回到 $\boldsymbol{l}$**。 因为只需要考虑从 $r$ 回到 $l$ 的情况，所以这时候要是回不来，直接把所有需要加的油都在 $g_r$ 上加满就行了。 也就是说，刚刚从左到右的过程，会给 $g_i$ 造成一些影响（$g_{\mathrm{next}[i] - 1} \gets g_{\mathrm{next}[i] - 1} + \mathrm{val}[i]$）。 进而会影响到 $\mathrm{suf}[i]$ 的值，令被影响的新的 $\mathrm{suf}$ 叫做 $\mathrm{suf}'$。 则从 $r$ 无法回到 $l$ 当且仅当存在一个位置 $p$ 满足 $l \le p \le r$ 且 $\mathrm{suf}'[r] > \mathrm{suf}'[p]$。 令 $\mathrm{minsuf}'(l, r)$ 表示 $\displaystyle \min_{l \le i < r} \{ \mathrm{suf}'[i] \}$（注意 $i$ 的范围是 $[l, r)$，是左闭右开区间）。 则还需要在 $g_r$ 上增加的代价就为 $\max \{0, \mathrm{suf}'[r] - \mathrm{minsuf}'(l, r) \}$。 综上所述，$w(l, r)$ 应该等于 $\mathrm{cost}(l, r) + \max \{0, \mathrm{suf}'[r] - \mathrm{minsuf}'(l, r) \}$。 令 $w'(l, r) = \mathrm{cost}(l, r) + \mathrm{suf}'[r] - \mathrm{minsuf}'(l, r)$，也就是去掉了和 $0$ 取 $\mathrm{max}$ 的操作。 那么要求的就是满足 $\mathrm{cost}(l, r) \le k$ 且 $w'(l, r) \le k$ 的，最大的 $r - l + 1$ 的值。 --- 考虑计算某个左端点 $l$ 的答案，可以记 $S_l = \{\mathrm{next}[l], \mathrm{next}[\mathrm{next}[l]], \ldots \}$。 可以发现这个是一个链状结构，把所有的 $l \to \mathrm{next}[l]$ 的边画出来后，其实是一个树状结构（准确地说是森林）。 建立一个虚根 $\mathrm{root}$，所有的不存在 $\mathrm{next}$ 的位置（也就是每个森林的根）连向 $\mathrm{root}$。 然后从 $\mathrm{root}$ 开始 DFS，每次进入子树的时候考虑增加一个 $\mathrm{next}$ 的贡献即可，也就是每次给 $S_l$ 新添一个元素。 --- 当左端点 $l$ 固定时，需要找到的就是满足 $\mathrm{cost}(l, r) \le k$ 且 $w'(l, r) \le k$ 的最大的 $r$。 注意到 $\mathrm{cost}(l, r)$ 关于 $r$ 是个递增的函数，**所以 $\boldsymbol{r}$ 不能太大，先二分求出 $\boldsymbol{r}$ 的上限**。 而 $w'(l, r)$ 有三部分，我们分别考虑： 对于 $\mathrm{cost}(l, r)$，每一个 $S_l$ 的元素 $x$ 会对 $\mathrm{cost}(l, r)$ 产生一个后缀加的贡献（从 $x$ 开始的后缀）。 对于 $\mathrm{suf}'[r]$，每一个 $S_l$ 的元素 $x$ 会对 $\mathrm{suf}'[r]$ 产生一个后缀减的贡献（从 $x$ 开始的后缀）。 很神奇的是：这两个贡献，作用的后缀完全相同，产生的贡献互为相反数，那么我们完全不管也是可以的。 也就是说： $\mathrm{cost}(l, r) + \mathrm{suf}'[r]$，这个值是固定不变的，它永远等于 $\mathrm{suf}[r]$。 最后，对于 $\mathrm{minsuf}'(l, r)$，每次对 $\mathrm{suf}'$ 有一个后缀减的贡献（**从 $\boldsymbol{x - 1}$ 开始的后缀**）。 之前定义为左闭右开区间的优势在这里显现出来了： 对于 $r \ge x$ 的情况，会给 $g_{x - 1}$ 加上 $\mathrm{val}$（注意是 $x - 1$），这是不好处理的（如果 $r = x - 1$ 比较难办）。 但是定义为 $[l, r)$，那么 $g_{x - 1}$ 的修改就会在 $\mathrm{minsuf}'(l, x)$ 上才显现出来，这就避免了 $r = x - 1$ 时的问题。 --- 那么也就是说，对于固定的 $l$，每个位置 $r$ 的代价为 $\mathrm{suf}[r] - \mathrm{minsuf}'(l, r)$，考虑使用**线段树**维护这个代价。 而 $r$ 的取值范围显然为 $l \le r \le r_{\max}$，其中 $r_{\max}$ 为之前确定的上限。 注意到 $\displaystyle \mathrm{minsuf}'(l, r) = \min_{l \le i < r} \{ \mathrm{suf}'[i] \}$，其中这个 $l \le i$ 不好处理，因为要计算很多个 $l$ 的答案。 考虑在处理某个特定的 $l$ 时，把 $\mathrm{suf}'[1] \sim \mathrm{suf}'[l - 1]$ 加上 $\infty$，这样就取消了 $i < l$ 的影响。 这之后 $\mathrm{minsuf}'(l, r)$ 就可以看作是 $\displaystyle \min_{1 \le i < r} \{ \mathrm{suf}'[i] \}$ 了。 对于 $r \le r_{\max}$ 的限制我们也如法炮制，把 $\mathrm{suf}'[r_{\max}] \sim \mathrm{suf}'[n]$ 减去 $\infty$，即可消除 $r > r_{\max}$ 的影响。 （注意是包括 $\mathrm{suf}'[r_{\max}]$，这样才能把 $\mathrm{minsuf}'(l, r_{\max} + 1)$ 给变成 $-\infty$） **当然，对于 $\boldsymbol{l \le r \le r_{\max}}$ 的处理，可以直接在线段树上提取区间，但复杂度可能会退化为 $\boldsymbol{\mathcal O (n \log^3 n)}$**。 （存在一种精细实现的方法使得复杂度不退化，但是需要先把所有区间提取出来，再从左到右扫一遍，从右到左查询，最后可以得到时间复杂度为 $\mathcal O (n \log^2 n)$，实现起来有点复杂） 所以最终就变成了一个线段树维护 $\displaystyle a_i - \min_{1 \le j < i} \{ b_j \}$ 的最小值的问题，然后对于修改需要支持 $b_i$ 的区间加减法。 --- 这个东西怎么维护呢？ 考虑一个类似[楼房重建](https://www.luogu.com.cn/problem/P4198)的线段树算法： 线段树中的每个节点维护区间 $\mathrm{suf}[i], \mathrm{suf}'[i]$ 的最小值， 再特别维护一个：仅考虑本区间的 $\mathrm{suf}'[i]$ 时，$r$ 的取值仅在右子树的答案的最小值。 在 Pushup 的时候使用一个类似[楼房重建](https://www.luogu.com.cn/problem/P4198)的每次只递归到一个子树内的函数维护当前节点信息。 在查询答案时，使用一个类似线段树上二分的结构求得最靠右的满足 $w'(l, r) \le k$ 的下标 $r_{\mathrm{ans}}$。 这部分与楼房重建相比，还是有很多新的东西，需要再详细说一下： 当区间左侧传来的最小值 $pre$ 比左子树的 $\mathrm{suf}'[i]$ 的最小值小时，也就是左子树完全被 $pre$ 控制， 也就是，左子树中的条件变为 $\mathrm{suf}[i] - pre \le k$，就是 $\mathrm{suf}[i] \le k + pre$，这部分是正常的线段树上二分。 但是不要忘记了还要递归进右子树查询，虽然两边子树都递归了，但是时间复杂度没有退化到 $\mathcal O (n)$。 因为每次递归到左子树时，都是 $\mathcal O (\log n)$ 的，而可能有 $\mathcal O (\log n)$ 次向左子树的递归，所以是 $\mathcal O (\log^2 n)$ 的。 具体细节请见[从《楼房重建》出发浅谈一类使用线段树维护前缀最大值的算法](https://www.luogu.com.cn/blog/PinkRabbit/Segment-Tree-and-Prefix-Maximums)。 时间复杂度为 $\mathcal O (n \log^2 n)$，[评测链接](https://codeforces.com/contest/671/submission/72599319)。