CF671E Organizing a Race
题目大意
K 国有 \(n\) 座城市和 \(n-1\) 条道路将它们相连。第 \(i\) 条道路连接了编号为 \(i\) 和 \(i + 1\) 的两座城市，道路长度为 \(w_i\)。
在 K 国驾驶时，每当到达城市 \(i\)，你的车会立即得到能使它行驶 \(g_i\) 个单位长度的油。
你现在要举办一场赛车比赛。比赛在 \(l,r\) 两座城市间进行。比赛分为两个独立的阶段。第一阶段，车从 \(l\) 驶向 \(r\)，第二阶段，车从 \(r\) 回到 \(l\)。每个阶段内部，不能走回头路（也就是在第一阶段只能向右走，第二阶段只能向左走）。定义一场 \(l,r\) 之间的比赛的美丽度为 \(r - l + 1\)。你可以认为车的油箱是无穷大的，所以参赛者在途中会领取所有可获得的油。
在每个阶段的开始，油箱都是空的（也就是第一阶段剩余的油，不会留到第二阶段）。开始后的一瞬间，车会立刻得到起点处的油（在第一阶段是 \(g_l\)，在第二阶段是 \(g_r\)）。
如果在途中车没油了，则比赛无法进行。因此不是所有的 \(l,r\) 之间都能举行比赛。
你有 \(k\) 次机会。每次你可以选择一个城市 \(i\)，并令 \(g_i\) 提升 \(1\)。可以对一个城市重复操作，并多次获得提升。问，经过操作后，你能举办的美丽度最大的比赛，美丽度是多少？
数据范围：\(2\leq n\leq 10^5\)，\(1\leq w_i\leq 10^9\)，\(0\leq k,g_i\leq 10^9\)。
本题题解
初步转化：前缀和
考虑 \(l,r\) 之间能举办比赛，需要满足什么条件。对两个阶段分别看，不难列出条件：
\[\begin{cases} \forall i\in[l, r): \sum_{j = l}^{i}g_j \geq \sum_{j = l}^{i}w_j\\ \forall i\in[l,r): \sum_{j = i + 1}^{r} g_j\geq \sum_{j = i}^{r - 1} w_{j} \end{cases} \]做前缀和。设 \(G_i = \sum_{j = 1}^{i}g_j\)，\(W_i=\sum_{j = 1}^{i}w_j\)。则条件也可以写成：
\[\forall i \in[l,r):\begin{cases} G_i - G_{l - 1} \geq W_{i} - W_{l - 1}\\ G_r - G_{i}\geq W_{r - 1} - W_{i - 1} \end{cases} \]移项，把关于 \(i\) 的放在一边，关于 \(l\) 或 \(r\) 的放在另一边：
\[\forall i \in[l,r):\begin{cases} G_i - W_{i} \geq G_{l - 1} - W_{l - 1}\\ G_{i} - W_{i - 1}\leq G_r - W_{r - 1} \end{cases} \]设 \(a_i= G_i - W_i\)，\(b_i = G_i - W_{i - 1}\)。特别地，\(a_{0} = 0\)。则条件也可以写成：
\[\forall i \in[l,r): \begin{cases} a_i \geq a_{l - 1}\\ b_i \leq b_r \end{cases} \]考虑一次操作（\(g_i\texttt{++}\)）对 \(a\), \(b\) 的影响。发现相当于对所有 \(j\geq i\)，令 \(a_j\texttt{++}\)，\(b_j\texttt{++}\)。
至此我们把问题转化为了关于两个序列 \(a\), \(b\) 的，更简明的问题。
考虑枚举 \(l\) 或 \(r\)，再按一定顺序枚举另一个，我们很容易写出一个 \(\mathcal{O}(n^2)\) 的暴力。
进一步转化：单调栈，贪心
首先 \(l = r\) 一定是可行的。故以下只讨论 \(l < r\) 的情况。
先不考虑 \(b\) 的限制。如果只有 \(a_i\geq a_{l-1}\) 这一个要求，我们会如何操作呢？显然，全部都在 \(l\) 处操作是最优的，所需的操作次数是 \(\max\{0, a_{l - 1} - \min_{i \in[l,r)}\{a_i\}\}\)。
但当有了 \(b\) 的限制，全部在 \(l\) 处操作就不一定可行了。因为可能存在一个 \(b_p > b_r\) (\(p\in[l,r)\))，全在 \(l\) 操作时，\(b_p\) 会和 \(b_r\) 一起变大，则 \(b_p\) 永远大于 \(b_r\)，不满足 \(b\) 的限制。
为了让 \(b\) 合法，我们必须使 \(b_r\) 比 \(b_p\) 被多加了 \(b_p - b_r\) 次。也就是说，至少要有 \(b_p - b_r\) 次操作，是在 \(p\) 右边的位置进行的。
我们从 \(r\) 向左，依次找到：第一个大于 \(b_r\) 的位置 \(p_1\)；第一个大于 \(b_{p_1}\) 的位置 \(p_2\)；......。也就是序列 \(b_{1\dots r}\) 的后缀最大值所在的位置，从右向左记为 \(p_1,p_2,\dots,p_m\)。另记 \(p_0 = r, p_{m + 1} = 0\)。如果从小到大枚举 \(r\)，则这些位置可以用一个单调栈维护出来。现在，对每个 \(p_i\) (\(1\leq i\leq m, p_i \geq l\))，必须有至少 \(b_{p_i} - b_r\) 次操作是在 \(p_i\) 后面进行的。根据一开始的贪心原则（尽可能使 \(a\) 合法），我们一定会在尽量靠前的位置使用这些操作，也就是对所有 \(i\)，在 \(p_i + 1\) 的位置，使用 \(b_{p_i} - b_{p_{i - 1}}\) 次操作。
前面说过，我们从小到大枚举 \(r\)，并用单调栈维护出 \(p\) 序列。现在假设已知了 \(l\)，那我们就知道了所有 \(p_i\geq l\) 的 \(p_i\)，进而能够确定，为了使 \(b\) 合法，所必须做的这些操作（对所有 \(p_i\geq l\)，在 \(p_i + 1\) 的位置，使用 \(b_{p_i} - b_{p_{i - 1}}\) 次操作）。操作完成后，\(a\) 序列的数值会有所更新，记更新后的序列为 \(a'\)，即：\(a'_j = a_j + \sum_{l\leq p_i < j}(b_{p_i} - b_{p_{i - 1}})\)。现在 \(b\) 的限制已经满足，接下来要通过最少的操作使 \(a\) 合法，也就是最开始的贪心：在 \(l\) 处再进行 \(\max\{0, a_{l - 1} - \min_{j \in[l,r)}\{a'_j\}\}\) 次操作即可。
发现当 \(l\) 存在于某个区间 \((p_{i + 1}, p_i]\) 时，使 \(b\) 合法所需的操作次数（记为 \(x\)）是一样的，得到的 \(a'\) 序列也是一样的（只考虑 \(a'_{l\dots r - 1}\) 这段区间，其他位置不管）。所以可以枚举 \(l\) 所在的区间。在保证 \(x\leq k\) 的前提下，剩余操作次数 \(\max\{0, a_{l - 1} - \min_{j \in[l,r)}\{a'_j\}\}\) 这个式子里的 \(\max\) 可以去掉（因为 \(x +\max\{0,y\}\leq k\) 和 \(x + y\leq k\)，在 \(x\leq k\) 时是一样的）。于是我们可以用数据结构维护 \(a'\) 序列，并支持求 \(a_{l - 1} - \min_{j \in[l,r)}\{a'_j\}\leq k - x\) 的最小的 \(l\)（不知道具体实现方法没关系，后面会讲）。
但是当 \(b\) 序列近似单调递减时，\(p\) 序列的长度是 \(\mathcal{O}(n)\) 的，上述做法的时间复杂度可能退化为 \(\mathcal{O}(n^2\log n)\)，还不如暴力。但这可以通过一个巧妙的观察来避免。
巧妙观察，省去枚举
设区间 \((p_{i + 1}, p_i]\) 所需的操作次数为 \(x_i\)，即 \(x_i = \sum_{1\leq j\leq i}(b_{p_j} - b_{p_{j - 1}})\)。完成这 \(x_i\) 次操作后，我们会把剩余的 \(k - x_i\) 次操作，全部作用于位置 \(l\) 上。也就是说，每个 \(a'_j\) (\(l\leq j < r\)) 还会再增加 \(k - x_i\)。那把这 \(k - x_i\) 次操作作用于 \(l\)，和把这些操作作用于任意位置 \(1\leq t < l\)，对 \(a'_{l\dots r-1}\) 来说，效果是一模一样的。因此，如果我们找出了满足 \(x_i\leq k\) 的最大的 \(i\)，那么可以假装进行了这 \(x_i\) 次操作。这不会影响 \(l > p_i\) 时的正确性。
在单调栈加入、弹出元素时，可以顺便维护出 \(x_i\) 序列。因此可以很方便地二分出 \(x_i\leq k\) 的最大的 \(i\)。同时也就确定了对应的 \(a'\) 序列（具体如何维护后面会讲）。问题转化为求哪些 \(l\) 能在 \(k - x_i\) 次操作内，使 \(a\) 合法。具体来说是要找到 \(a_{l - 1} - \min_{j \in[l,r)}\{a'_j\}\leq k - x_i\) 的最小的 \(l\)。
数据结构维护：一类有技巧的线段树
用线段树来维护序列 \(c_i = a_{i - 1} - \min_{j \geq i}\{a'_j\}\)。其中 \(a_{i - 1}\) 是从一开始就确定不变的值。对 \(a'\) 我们会在整个过程中不断修改。注意，我们要查询的其实是：\(a_{l - 1} - \min_{j \in[l,r)}\{a'_j\}\)，但这可以通过把 \(j \geq r\) 的 \(a'_j\) 全部维护为 \(\infty\) 来转化为 \(c_l\)。
考虑具体要支持哪些操作：
- 对 \(a'\) 进行区间加。在单调栈加入、弹出元素，以及确定了 \(i\) 后，对 \(a'\) 的所有修改都可以归结为区间加（减法就是加负数）。
- 查询：在线段树上二分出 \(c_l\leq v\) 的最小的 \(l\)，其中 \(v = k - x_i\) 是一个定值。这相当于要维护出 \(c\) 序列的区间最小值。
对区间 \([l,r]\) 做区间加时，还会影响到 \(i < l\) 的 \(c_i\) 的值，所以并不是很容易直接维护。于是这里就需要用到一类有技巧的线段树，读者可以去粉兔的博客学习一下。
在本题里，线段树的每个节点上，维护四个信息。设这个节点对应的区间为 \([l,r]\)。
- \(\text{mn1}\)：区间内 \(a'\) 的最小值。即 \(\text{mn1}(l,r) = \min_{l\leq i\leq r}\{a'_i\}\)。
- \(\text{tag}\)：对 \(a'\) 进行区间加的懒标记。这和普通线段树是一样的。
- \(\text{mn}2\)：区间内 \(a_{i - 1}\) 的最小值。即 \(\text{mn2}(l,r) = \min_{l\leq i\leq r}\{a_{i - 1}\}\)。
- \(\text{lans}\)：这就是这类线段树特有的东西了。叶子节点是没有 \(\text{lans}\) 的。对非叶子节点，它的 \(\text{lans}\) 表示只考虑区间 \([l,r]\) 里的数（而不是整个序列 \(1\dots n\)）时，它左儿子区间的 \(c_i\) 的最小值。形式化地，设该节点两个儿子区间分别为：\([l,\text{mid}]\) 和 \([\text{mid} + 1, r]\)，则 \(\text{lans}(l,r) = \min_{l\leq i\leq \text{mid}}\{a_{i - 1} - \min_{i\leq j\leq r}\{a'_j\}\}\)。这个“只考虑区间 \([l,r]\) 里的数”，最关键就体现在，里面 \(a'_j\) 并不是取 \(j\in[i, n]\) 的 \(\min\)，而是 \(j\in[i,r]\)。
考虑如何 \(\text{push up}\)，也就是用儿子区间的信息，更新父亲区间。\(\text{mn1}\), \(\text{mn2}\) 的更新是简单的，对两个儿子取较小者即可。关键是 \(\text{lans}\)。现在假设已经知道了当前节点子树里，除它以外所有节点的 \(\text{lans}\)。
考虑定义一个函数 \(\text{calc}(u, v)\)。其中 \(u\) 是线段树上一个节点，\(v\) 可以是任意数值。\(\text{calc}(u, v)\) 返回的是：假设后缀最小值为 \(v\) 时，点 \(u\) 所代表的区间里，\(c_i\) 的最小值。则 \(\text{lans}(u)\) 就等于 \(\text{calc}(\text{LeftSon}_u, \text{mn1}(\text{RightSon}_u))\)。
考虑如何实现 \(\text{calc}\) 函数。这里给出伪代码：
\[\begin{array}{l} \textbf{def: } \mathrm{calc}(u, v) \\ \qquad \textbf{if } (u \text{ is a leaf node}) \\ \qquad \qquad \textbf{return } {\color{green}{\text{mn2}(u) - \min\{\text{mn1}(u), v\}}} \\ \qquad \textbf{else} \\ \qquad \qquad \textbf{if } (\text{mn1}(\text{RightSon}_u) > v) \\ \qquad \qquad \qquad \textbf{return } \min \{ {\color{blue}{\text{calc}(\text{LeftSon}_u, v)}}, {\color{red}{\text{mn2}(\text{RightSon}_u) - v}} \}\\ \qquad \qquad \textbf{else} \\ \qquad \qquad \qquad \textbf{return } \min \{ {\color{blue}{\text{lans}(u)}}, {\color{red}{\text{calc}(\text{RightSon}_u, v)}} \} \\ \qquad \qquad \textbf{endif.} \\ \qquad \textbf{endif.} \\ \textbf{enddef.} \end{array} \]代码的含义是：
- 当 \(u\) 是叶子节点的情况显然。
- 否则，若 \(\text{mn1}(\text{RightSon}_u) > v\)，则对右区间的所有位置来说，它们后面的最小值都是 \(v\)，所以右区间 \(c_i\) 的最小值就是 \(\text{mn2}(\text{RightSon}_u) - v\)。
- 否则，\(\text{mn1}(\text{RightSon}_u) \leq v\)，此时 \(v\) 不影响左区间的答案。
因为每次只向两儿子中的一个递归，所以执行一次 \(\text{calc}\) 函数的时间复杂度为 \(\mathcal{O}(\log n)\)。因为每次 \(\text{push up}\) 时都要 \(\text{calc}\)，所以一次区间加的时间复杂度为 \(\mathcal{O}(\log^2 n)\)。
线段树上二分也与普通的线段树上二分是类似的。只不过判断向哪边递归时需要调用 \(\text{calc}\) 函数。所以时间复杂度也是 \(\mathcal{O}(\log^2 n)\)。
至此，我们以 \(\mathcal{O}(n\log^2 n)\) 的总时间复杂度解决了本题。
参考代码
// problem: CF671E
#include <bits/stdc++.h>
using namespace std;
#define mk make_pair
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef unsigned int uint;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
template<typename T> inline void ckmax(T& x, T y) { x = (y > x ? y : x); }
template<typename T> inline void ckmin(T& x, T y) { x = (y < x ? y : x); }
const int MAXN = 1e5;
const int INF = 1e9;
const ll LL_INF = 1e16;
int n, g[MAXN + 5], w[MAXN + 5];
ll K, a[MAXN + 5], b[MAXN + 5];
int sta[MAXN + 5], top;
ll val[MAXN + 5], presum_val[MAXN + 5];
struct SegmentTree {
ll mn[MAXN * 4 + 5], tag[MAXN * 4 + 5];
ll mn2[MAXN * 4 + 5];
ll lans[MAXN * 4 + 5];
void push_down(int p) {
if (tag[p] != 0) {
mn[p << 1] += tag[p];
tag[p << 1] += tag[p];
lans[p << 1] -= tag[p];
mn[p << 1 | 1] += tag[p];
tag[p << 1 | 1] += tag[p];
lans[p << 1 | 1] -= tag[p];
tag[p] = 0;
}
}
ll calc(int p, int l, int r, ll right_min) {
if (l == r) {
return mn2[p] - min(right_min, mn[p]);
}
push_down(p);
int mid = (l + r) >> 1;
if (right_min >= mn[p << 1 | 1]) {
return min(lans[p], calc(p << 1 | 1, mid + 1, r, right_min));
} else {
return min(calc(p << 1, l, mid, right_min), mn2[p << 1 | 1] - right_min);
}
}
void push_up(int p, int l, int mid) {
mn[p] = min(mn[p << 1], mn[p << 1 | 1]);
lans[p] = calc(p << 1, l, mid, mn[p << 1 | 1]);
}
void build(int p, int l, int r) {
if (l == r) {
mn[p] = a[l];
mn2[p] = a[l - 1];
return;
}
int mid = (l + r) >> 1;
build(p << 1, l, mid);
build(p << 1 | 1, mid + 1, r);
mn2[p] = min(mn2[p << 1], mn2[p << 1 | 1]);
push_up(p, l, mid);
}
void range_add(int p, int l, int r, int ql, int qr, ll v) {
if (ql <= l && qr >= r) {
mn[p] += v;
tag[p] += v;
lans[p] -= v;
return;
}
push_down(p);
int mid = (l + r) >> 1;
if (ql <= mid) {
range_add(p << 1, l, mid, ql, qr, v);
}
if (qr > mid) {
range_add(p << 1 | 1, mid + 1, r, ql, qr, v);
}
push_up(p, l, mid);
}
int _find(int p, int l, int r, ll right_min, ll v) {
if (l == r) {
return l;
}
push_down(p);
int mid = (l + r) >> 1;
if (calc(p << 1, l, mid, min(right_min, mn[p << 1 | 1])) <= v) {
return _find(p << 1, l, mid, min(right_min, mn[p << 1 | 1]), v);
} else {
return _find(p << 1 | 1, mid + 1, r, right_min, v);
}
}
int find(int p, int l, int r, ll right_min, int ql, int qr, ll v) {
if (ql <= l && qr >= r) {
if (calc(p, l, r, right_min) <= v) {
return _find(p, l, r, right_min, v);
} else {
return INF;
}
}
push_down(p);
int mid = (l + r) >> 1;
int res = INF;
if (ql <= mid) {
res = find(p << 1, l, mid, min(right_min, mn[p << 1 | 1]), ql, qr, v);
if (res != INF)
return res;
}
if (qr > mid) {
res = find(p << 1 | 1, mid + 1, r, right_min, ql, qr, v);
}
return res;
}
SegmentTree() {}
};
SegmentTree T;
int calc(int p, int r) {
if (sta[p - 1] + 1 > r - 1) {
return 0;
}
ll sum = presum_val[top - 1] - presum_val[p - 1];
T.range_add(1, 1, n, r, n, LL_INF); // 强制不考虑 >= r 的部分
T.range_add(1, 1, n, sta[p - 1] + 1, r - 1, -presum_val[p - 1]);
int res = T.find(1, 1, n, LL_INF, sta[p - 1] + 1, r - 1, K - sum);
T.range_add(1, 1, n, r, n, -LL_INF); // 恢复原状
T.range_add(1, 1, n, sta[p - 1] + 1, r - 1, presum_val[p - 1]);
return r - res + 1;
}
int main() {
cin >> n >> K;
for (int i = 1; i < n; ++i) {
cin >> w[i];
}
for (int i = 1; i <= n; ++i) {
cin >> g[i];
}
for (int i = 1; i < n; ++i) {
a[i] = a[i - 1] + g[i] - w[i];
//cerr << a[i] << " \n"[i == n - 1];
}
for (int i = 1; i <= n; ++i) {
b[i] = b[i - 1] + g[i] - w[i - 1];
//cerr << b[i] << " \n"[i == n];
}
T.build(1, 1, n);
int ans = 1;
for (int i = 1; i <= n; ++i) {
while (top && b[sta[top]] <= b[i]) {
if (top > 1) {
T.range_add(1, 1, n, sta[top - 1] + 1, sta[top], -presum_val[top - 1]);
}
--top;
}
sta[++top] = i;
if (top > 1) {
val[top - 1] = b[sta[top - 1]] - b[i];
presum_val[top - 1] = presum_val[top - 2] + val[top - 1];
T.range_add(1, 1, n, sta[top - 1] + 1, i, presum_val[top - 1]);
}
/*
for (int j = 1; j <= i; ++j) f[j] = a[j];
ll sum = 0;
for (int j = top; j >= 1; --j) {
// l in (sta[j - 1], sta[j]]
for (int k = sta[j] + 1; k <= i; ++k) {
f[k] += b[sta[j]] - b[sta[j + 1]];
}
if (j < top) {
sum += b[sta[j]] - b[sta[j + 1]];
}
ll mn = LL_INF;
for (int k = sta[j] + 1; k < i; ++k)
ckmin(mn, f[k]);
for (int l = sta[j] - (j == top); l > sta[j - 1]; --l) {
ckmin(mn, f[l]);
ll cost = sum + max(0LL, a[l - 1] - mn);
if (cost <= K) {
ckmax(ans, i - l + 1);
}
}
}
*/
int l = 1, r = top;
while (l < r) {
int mid = (l + r) >> 1;
if (presum_val[top - 1] - presum_val[mid - 1] <= K) {
r = mid;
} else {
l = mid + 1;
}
}
ckmax(ans, calc(l, i));
}
cout << ans << endl;
return 0;
}
相关题目
本题里用到的“一类有技巧的线段树”，在一些其他问题中也有出现。读者可以自行选择练习：
正睿2018暑假集训day4 数组：我的题解