CF671E Organizing a Race 题解

CF671E Organizing a Race

题意

• 有 $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)$。

代码

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 > r || t[p].d + k < x) return 0;
	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)) {
		int ret = ask(rs, l, r, max(x, t[ls].x));
		if (ret) return ret;
	}
	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;
}