题解 CF671E 【Organizing a Race】

> [CF671E Organizing a Race](https://codeforces.com/contest/671/problem/E) ## 题意 - 有 $n$ 个点排成一行，第 $i$ 个点与第 $i + 1$ 个点之间的距离为 $w_i$ 个单位。 - 每个点都有一个加油站，第 $i$ 个点的加油站可以给你的车加能跑 $g_i$ 个单位的油。 - 若一辆初始没有油的车能从 $l$ 一路向右开到 $r$，也能从 $r$ 一路向左开到 $l$，则称 $l,r$ 之间可以往返。 - 另外，你有 $k$ 次将某个 $g_i$ 加 $1$ 的机会。 - 请你求出在 $l,r$ 之间可以往返的情况下，$r-l+1$ 的最大值。 - $n \le 10^5$，$k,w_i,g_i \le 10^9$。 ## 题解 考虑什么条件下 $l,r$ 之间可以往返。 显然为： $$\begin{cases}w_l \le g_l \\w_l + w_{l+1} \le g_l + g_{l+1} \\\cdots \\\sum_{i=l}^{r-1} w_i \le \sum_{i=l}^{r-1} g_i\end{cases}$$ 以及 $$\begin{cases}w_{r-1} \le g_r \\w_{r-1} + w_{r-2} \le g_r + g_{r-1} \\\cdots \\\sum_{i=l}^{r-1} w_i \le \sum_{i=l+1}^{r} g_i\end{cases}$$ 考虑对 $w,g$ 的前缀和 $a,b$，则条件变为： $$\begin{cases}a_l-a_{l-1} \le b_l-b_{l-1} \\a_{l+1}-a_{l-1} \le b_{l+1}-b_{l-1} \\\cdots \\a_{r-1}-a_{l-1} \le b_{r-1}-b_{l-1}\end{cases}$$ 以及 $$\begin{cases}a_{r-1} - a_{r-2} \le b_r - b_{r-1} \\a_{r-1} - a_{r-3} \le b_r - b_{r-2} \\\cdots \\a_{r-1} - a_{l-1} \le b_r - b_{l}\end{cases}$$ 设 $c_i = a_{i-1} - b_{i-1}$，$d_i = b_i - a_{i-1}$，则条件变为简单的两个等式： $$\begin{cases}c_{l} = \max_{i=l}^{r} c_i\\d_{r} = \max_{i=l}^{r} d_i\end{cases}$$ 若 $g_i$ 加 $1$，则对于 $j \ge i$，$b_j$ 加 $1$；对于 $j > i$，$c_j$ 减 $1$；对于 $j \ge i$，$d_j$ 加 $1$。 先考虑 $l \to r$。 从 $n$ 到 $1$ 枚举 $l$，用单调栈维护一个单调上升的子序列 $c_{x_0} < c_{x_1} < c_{x_2} < \cdots$，其中 $x_0 = l$。则 $k$ 一定是贪心地依次对 $g_{x_1-1},g_{x_2-1},\cdots$ 使用，每次将 $g_{x_i-1}$ 加 $c_{x_i} - c_{x_{i-1}}$。 再考虑 $r\to l$。 到某个 $x_p$ 后，设剩下的 $k$ 为 $k^\prime$，上一步使用完后的 $d$ 为 $d^\prime$，则要满足 $d^\prime_r + k^\prime \ge d^\prime_{l \dots r-1}$，即 $d_r + k \ge \max_{i=l}^{r-1} d^\prime_{i}$。 因此，我们可以先在单调栈上二分出只考虑 $l \to r$ 的情况下的最大 $r^\prime$，即找到满足 $c_{x_i} - c_{l} \le k$ 的最大 $x_i$，则最大 $r^\prime = x_{i+1} - 1$。 此时，最优解的范围一定在 $[l,r^\prime]$ 中，再在这个范围内的线段树上二分找到最大的 $r$，然后取每次 $r-l+1$ 的最大值即可。 具体来说，我们用线段树维护 $d^\prime$，每次往单调栈里加一个位置 $x$ 后，将单调栈中前一个位置 $y$ 的贡献 $c_{y} - c_{x}$ 加到 $d^\prime_{y-1\dots n}$ 上，退栈时相应减去。另外，对于 $l$ 左边的部分，为了方便可以将 $d^\prime$ 设为 $-\infty$。 线段树上二分时，对于一个节点 $p$，如果 $\max_{rs} d_i + k \ge \max_{1\dots p_{mid}} d^\prime_i$，则意味着 $\max_{rs} d_i$ 的 $i$ 处一定是一个合法解，因此递归往右儿子找，否则递归往左儿子找。 为什么 $\max_{rs} d_i + k \ge \max_{1\dots p_{mid}} d^\prime_i$ 就意味着 $\max_{rs} d_i$ 的 $i$ 处一定是一个合法解呢？合法条件为 $d_r + k \ge \max_{i=l}^{r-1} d^\prime_{i}$，那么 $d^\prime_{p_{mid+1}\dots i-1}$ 中有没有可能比 $d_i + k$ 大呢？ 其实很显然，注意到 $d^\prime$ 是 $d$ 加上 $\le k$ 的一个数生成的就可以了。 时间复杂度 $\mathcal O(n \log n)$。 ## 代码 ```cpp const int N = 1e5 + 7; const ll inf = 1e18; int n, ans, s[N], p; ll k, w[N], g[N], a[N], b[N], c[N], d[N]; struct T { int l, r; ll x, z, d; } t[N<<2]; void build(int p, int l, int r) { t[p].l = l, t[p].r = r, t[p].x = -inf; if (t[p].l == t[p].r) return; build(ls, l, md), build(rs, md + 1, r); } inline void upd(int p) { t[p].x = max(t[ls].x, t[rs].x); t[p].d = max(t[ls].d, t[rs].d); } inline void spd(int p) { if (t[p].z) { t[ls].x += t[p].z; t[ls].z += t[p].z; t[rs].x += t[p].z; t[rs].z += t[p].z; t[p].z = 0; } } void setx(int p, int x, ll k) { if (t[p].l == t[p].r) return t[p].x = t[p].d = k, void(); spd(p); if (x <= md) setx(ls, x, k); else setx(rs, x, k); upd(p); } void add(int p, int l, int r, ll k) { if (t[p].l >= l && t[p].r <= r) return t[p].x += k, t[p].z += k, void(); spd(p); if (l <= md) add(ls, l, r, k); if (r > md) add(rs, l, r, k); upd(p); } int ask(int p, int l, int r, ll x) { if (t[p].l == t[p].r) return t[p].l; spd(p); if (md < l) return ask(rs, l, r, x); if (r <= md) return ask(ls, l, r, x); if (t[rs].d + k >= max(x, t[ls].x)) return ask(rs, l, r, max(x, t[ls].x)); return ask(ls, l, r, x); } int main() { rd(n), rd(k), rda(w, n - 1), rda(g, n); for (int i = 1; i < n; i++) a[i] = a[i-1] + w[i]; for (int i = 1; i <= n; i++) b[i] = b[i-1] + g[i]; for (int i = 1; i <= n; i++) c[i] = a[i-1] - b[i-1]; for (int i = 1; i <= n; i++) d[i] = b[i] - a[i-1]; build(1, 1, n); for (int i = n; i; i--) { while (p && c[i] >= c[s[p]]) { if (p > 1) add(1, s[p-1] - 1, n, c[s[p]] - c[s[p-1]]); --p; } s[++p] = i, setx(1, i, d[i]); if (p > 1) add(1, s[p-1] - 1, n, c[s[p-1]] - c[i]); int l = 1, r = p; while (l < r) { int mid = (l + r) >> 1; if (c[s[mid]] - c[i] <= k) r = mid; else l = mid + 1; } r = r == 1 ? n : s[r-1] - 1; ans = max(ans, ask(1, i, r, -inf) - i + 1); } print(ans); return 0; } ```