我从未理解贪心与倍增。
b1tset
·
2026-09-04 21:17:29
·
题解
很有意思的一道题。在做这题的时候参考了这篇题解，但是对题解中的 f 和 g 数组的定义感到很不自然——能理解转移式的必要性但无法理解其充分性。过了这题之后本来想丢掉不管的，不过想了想还是秉着严谨点的态度把这东西弄懂吧，于是在 AI 帮助下理解了正确性，便有了这篇题解。感觉类似的贪心题还是得严谨证明、写点东西记录一下才行。希望此题解能对后人的理解起到帮助。
转化、贪心与倍增处理
和其他题解一样，将原问题刻画成在若干权值为 1 和 2 的区间中选若干不交区间，使得收益最大。单独一颗树向左 / 右倒下后的区间权值为 1 ；对于两颗同向倒下的树（左边的往右倒，右边的往左倒）形成的区间权值为 2 。对于两种区间的预处理原题解已经足够详细，此处不再赘述。
再来考虑本题中的最重要贪心思想：在已经确定取得相同总权值的前提下，只需要保留结束位置最靠左的方案。这个很好理解，权值相同的情况下越早结束就拥有更多的“选择空间”，这个显然不劣。因此我们可以预处理出对于每个起始点 i ，下一步选权值为 1 或 2 的区间的最早结束点，即原题解的 r_{0 / 1, *} 数组。
预处理出 r 数组之后暴力跳肯定太慢了，我们考虑倍增（参考区间权值为 1 的弱化版），也就是建立倍增数组 f_{i, j} 表示在 i 处开始取，收益为 2^j 的最早结束点。与弱化版不同的是，此题有权值为 2 的区间，因此直接做贪心处理不了。为了解决这个问题，我们还要新定义 g_{i, j} 表示在 i 处开始取，收益为 2^j \red{-1} 的最早结束点。
状态定义的由来和转移正确性的证明
看到 g 数组的定义你或许会觉得很不自然，为什么定义个新状态考虑 2^j-1 的情况就能解决问题？下面我们不妨先忘掉 f 和 g 数组，用我们解决最优化问题的经典手段来考虑——观察并从最优解的形态入手。
显然，最优的合法区间选取方案肯定是若干个 1 区间和 2 区间拼起来。这样的形式有个关键性质：依次选取这些区间，我们的收益每次只会 +1 或 +2 。如果我们把这个收益序列从值域上考虑，会发现每两个连续的数中必然有一个在最优解的权值序列中，这个关键性质就成了两个小区间的最优解合并成大区间最优解的理论基础，也就是倍增的正确性基础。同时这个性质也是我们维护两个相邻的数进行转移的根本原因。
由此可见，g 数组定义中的 2^j - 1 不是凭空捏造出来的，是有严格正确性依据的。事实上，将 g 数组的定义改为 2^j + 1 也能正确处理本题。
至此我们已经证明了区间合并的正确性，下面来看看两个倍增数组是如何转移的。
f 数组的转移
- 若左半区间末尾的权值取在 $2^{j - 1}$，那么右半部分要还要再取 $2^{j - 1}$ 的权值，即：
$$
f_{i, j} \leftarrow f_{f_{i, j - 1} + 1, j - 1}
$$
- 若左半区间末尾的权值取在 $2^{j - 1} - 1$，那么右半部分要还要再取 $2^{j - 1} + 1$ 的权值（这个可以拆成 $2^{j - 1} - 1 + 2$），即：
$$
f_{i, j} \leftarrow f_{r_2(g_{i, j - 1} + 1) + 1, j - 1}
$$
根据上面的分析，这两条转移不多余也不缺漏，不会有更多的转移。满足贪心正确的充分性与必要性。
### $g$ 数组的转移
和 $f$ 的转移本质相同。$g_{i, j}$ 的定义是从 $i$ 开始选，收益 $2^j - 1$ 的最早结束点。$2^j - 1$ 同样有两种拆分方式，一种是分给左区间 $2^{j - 1} - 1$，另一种是分给左区间 $2^{j - 1}$，这两种分配方式依然是严格遵循「每两个连续的数中必然有一个在最优解的权值序列中」这一性质的。
- 若左半区间末尾的权值取在 $2^{j - 1} - 1$，那么右半部分要还要再取 $2^{j - 1}$ 的权值，即：
$$
g_{i, j} \leftarrow f_{g_{i, j - 1} + 1, j - 1}
$$
- 若左半区间末尾的权值取在 $2^{j - 1}$，那么右半部分要还要再取 $2^{j - 1} - 1$ 的权值，即：
$$
g_{i, j} \leftarrow g_{f_{i, j - 1} + 1, j - 1}
$$
同样，两条转移取较小值即可。这两条转移也恰好涵盖所有的区间合并方式。
## 查询部分的倍增跳
这里和 $f$ 与 $g$ 数组本质相同，都是在尝试合并区间，从小区间的最优解合并成大区间的最优解，依然是运用「每两个连续的数中必然有一个在最优解的权值序列中」的性质。
根据这一性质，我们还是要维护两个相邻收益的指针 $p$ 和 $q$，其中 $p$ 表示从询问左端点开始，收益为 $x$ 的最早结束点；$q$ 是收益为 $x + 1$ 的最早结束点。根据倍增思想，我们从大往小枚举步长 $i$，尝试取选取收益 $2^i$。我们同样尝试推导将 $2^i$ 收益合并到 $p$ 与 $q$ 后她俩的位置。
### $p$ 指针的转移
考虑给 $p$ 指针拼上 $2^i$ 的贡献，也就是转移到取 $x + 2^i$ 权值的最早结束点。依然考虑运用「每两个连续的数中必然有一个在最优解的权值序列中」的性质把这个数拆成两种转移。
- 将 $x + 2^i$ 拆成 $x$ 与 $2^i$ 相加，即：
$$
p' \leftarrow f_{p, i}
$$
- 将 $x + 2^i$ 拆成 $x + 1$ 与 $2^i - 1$ 相加，即：
$$
p' \leftarrow g_{q, i}
$$
$p'$ 指针取较小值即可。
### $q$ 指针的转移
和 $p$ 指针一样，考虑给 $q$ 指针拼上 $2^i$ 的贡献，也就是转移到取 $x + 1 + 2^i$ 权值的最早结束点。依旧拆成两种转移。
- 将 $x + 1 + 2^i$ 拆成 $x + 1$ 与 $2^i$ 相加，即：
$$
q' \leftarrow f_{q, i}
$$
- 将 $x + 1 + 2^i$ 拆成 $x$ 与 $2^i - 1 + 2$ 相加，即：
$$
q' \leftarrow g_{r_2(g_{p, i - 1} + 1) + 1, i - 1}
$$
$q'$ 指针取较小值即可。
### 累加答案
因为区间端点处的两颗树可以往两边倒，所以没限制，因此满足 $next(q') \le r$ 就可以取，取完之后更新 $p \leftarrow next(p')$，$q \leftarrow next(q')$ 和 $x \overset{+}{\leftarrow} 2^i$ 即可。
由于我们维护了 $q$ 指针，并保证了 $q$ 指针不超出范围，因此最后的答案应当是 $q$ 指针对应的 $x + 1$，这个细节要注意下。
## 代码
```cpp
#include <bits/stdc++.h>
using namespace std;
#define nxt(x) ((x) >= n ? n + 1 : (x) + 1)
using ll = long long;
const int N = 5e5, L = 19;
int n, p[N + 5], h[N + 5], r[N + 5], nr[N + 5];
int mx[L + 1][N + 5], f[L + 1][N + 5], g[L + 1][N + 5];
int get_max(int l, int r) {
int le = __lg(r - l + 1);
return max(mx[le][l], mx[le][r - (1 << le) + 1]);
}
int main() {
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int q; cin >> n >> q;
for (int i = 1; i <= n; i++) cin >> p[i];
for (int i = 1; i <= n; i++) cin >> h[i];
for (int i = 1; i <= n + 1; i++) r[i] = nr[i] = n + 1;
for (int i = 1, pv, nx; i <= n; i++) {
pv = lower_bound(p + 1, p + n + 1, p[i] - h[i]) - p;
if (pv) r[pv] = min(r[pv], i);
nx = upper_bound(p + 1, p + n + 1, p[i] + h[i]) - p - 1;
r[i] = min(r[i], nx);
}
for (int i = n; i >= 1; i--) r[i] = min(r[i + 1], r[i]);
for (int i = 1; i <= n; i++) mx[0][i] = p[i] - h[i];
for (int j = 1; j <= L; j++)
for (int i = 1; i + (1 << j) - 1 <= n; i++)
mx[j][i] = max(mx[j - 1][i], mx[j - 1][i + (1 << (j - 1))]);
for (int i = 1, nx, L, R, mi, pos; i <= n; i++) {
nx = upper_bound(p + i + 1, p + n + 1, p[i] + h[i]) - p;
L = nx, R = n, pos = n + 1;
while (L <= R) {
mi = (L + R) >> 1;
if (get_max(nx, mi) > p[i]) R = mi - 1, pos = min(pos, mi);
else L = mi + 1;
}
nr[i] = min(nr[i], pos);
}
for (int i = n; i >= 1; i--) nr[i] = min(nr[i + 1], nr[i]);
for (int i = 0; i <= L; i++) f[i][n + 1] = g[i][n + 1] = n + 1;
for (int i = 1; i <= n; i++) f[0][i] = r[i], g[0][i] = i - 1;
for (int j = 1; j <= L; j++)
for (int i = 1; i <= n; i++) {
f[j][i] = min(f[j - 1][nxt(f[j - 1][i])], g[j - 1][nxt(nr[nxt(g[j - 1][i])])]);
g[j][i] = min(f[j - 1][nxt(g[j - 1][i])], g[j - 1][nxt(f[j - 1][i])]);
}
int pl, pr;
while (q--) {
cin >> pl >> pr;
if (pl == pr) { cout << 1 << '\n'; continue ; }
static int x, y, nx1, nx2, ny1, ny2, ans;
ans = 2, x = nxt(pl), y = nxt(r[nxt(pl)]);
if (y > pr) { cout << 2 << '\n'; continue ; }
for (int i = L; i >= 0; i--) {
nx1 = f[i][x], nx2 = g[i][y];
ny1 = f[i][y], ny2 = g[i][nxt(nr[x])];
if (min(nxt(ny1), nxt(ny2)) > pr) continue ;
ans += (1 << i);
x = min(nxt(nx1), nxt(nx2));
y = min(nxt(ny1), nxt(ny2));
}
cout << ans + 1 << '\n';
}
return 0;
} // g++ qwq.cpp -o qwq -std=c++14 -O2 -static -Wall
```
到这里这道题就解决了。这题并没有什么高级的算法和技巧，却组成了一道黑题，也算是回归了算法的本质吧。当我们执着追求高级算法与 trick 的时候，往往忽视了算法学习中最重要的观察力与严谨的推导能力。或许学会思考，理解算法底层的原理与背后的数学逻辑才是最重要的吧。