题解：P15130 [ROIR 2026] 超级跳跃
ForgetOIDuck
·
·
题解
Super Bunny Man！
哎以为自己写了个 3\log 结果跑的比别人 2\log 还快。吓哭了。后面发现算错了。/咦
题意
给定 n 个点 (i,h_i)，q 次询问区间 l,r，求区间凸包的点数。
### 思路
注意到一个叫做「存在 $k$，使得对于所有 $i$，满足 $l_i \leq k \leq r_i$」的部分分。
这不是分治是啥。于是我们考虑分治，现在我们有一个中心点 $mid$，所有待计算区间都包含这个点。那么现在要做的事情是：
1. 计算每个左半部分的后缀凸包，右半部分的前缀凸包。
2. 对于一个询问，合并两个凸包。
以计算左半边的后缀凸包为例。每次计算一个后缀 $x\sim mid$，就相当于从 $x+1\sim mid$ 的凸包中**截取一段后缀** $y\sim mid$，和 $x$ 拼起来，$y$ 是 $x+1\sim mid$ 凸包的所有点中与 $x$ 连线斜率最大的。
注意到我们当然不能直接给每个 $x$ 开一个 `vector` 存。考虑每个 $x$ 向其对应的 $y$ 连一条有向边，那么整个左半边的点会形成一个**树状结构**，$x\sim mid$ 的凸包就是 $x$ 的**到根链**。如何找 $x$ 对应的 $y$？在所有 $x+1$ 的祖先上倍增即可。右半边同理。
接下来如何合并两个凸包 $l\sim mid$ 和 $mid\sim r$？我们需要找一个直线同时外切两个凸包。在左边凸包上二分一个点 $x^\prime$，找到右边与这个点斜率最大的点 $y^\prime$，看两个部分 $l\sim x^\prime$ 和 $y^\prime\sim r$ 拼起来之后有没有凹进去。这个依然可以倍增套倍增做。
分析一下时间复杂度：每一层都要 $O(n\log n)$ 地建出凸包，共 $\log n$ 层，时间复杂度 $O(n\log^2 n)$；每个询问都要倍增套倍增，时间复杂度 $O(q\log^2 n)$；总时间复杂度 $O((n+q)\log^2n)$。能过就行。
### 代码
```cpp
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n, m, h[100002], fa[22][100002], cnt[100002], ans[100002];
struct node {
ll l, r, id;
}q[100002], q2[100002];
void solve(ll l, ll r, ll qL, ll qR) {
if (l > r || qL > qR) return ;
ll mid = l + r >> 1, p1 = qL, p2 = qR;
for (ll i = qL; i <= qR; i ++ ) {
if (q[i].r < mid) q2[p1 ++] = q[i];
else if (q[i].l <= mid) q2[p2 --] = q[i];
}
p2 = p1;
for (ll i = qL; i <= qR; i ++ ) if (q[i].l > mid) q2[p2 ++] = q[i];
for (ll i = qL; i <= qR; i ++ ) q[i] = q2[i];
solve(l, mid - 1, qL, p1 - 1), solve(mid + 1, r, p1, p2 - 1), qL = p2;
if (qL > qR) return ;
ll dep = __lg(r - l + 1);
for (ll i = 0; i <= dep; i ++ ) fa[i][mid] = 0;
cnt[mid] = 1;
for (ll x = mid - 1; x >= l; x -- ) {
ll p = x + 1;
while (p != mid && (h[p] - h[x]) * (fa[0][p] - p) <= (h[fa[0][p]] - h[p]) * (p - x)) p = fa[0][p];
cnt[x] = cnt[fa[0][x] = p] + 1;
for (ll i = 1; i <= dep; i ++ ) fa[i][x] = fa[i - 1][fa[i - 1][x]];
}
for (ll x = mid + 1; x <= r; x ++ ) {
ll p = x - 1;
while (p != mid && (h[p] - h[fa[0][p]]) * (x - p) <= (h[x] - h[p]) * (p - fa[0][p])) p = fa[0][p];
cnt[x] = cnt[fa[0][x] = p] + 1;
for (ll i = 1; i <= dep; i ++ ) fa[i][x] = fa[i - 1][fa[i - 1][x]];
}
for (ll t = qL, ap1, ap2, ap3; t <= qR; t ++ ) {
if (q[t].l == mid) { ans[q[t].id] = cnt[q[t].r]; continue; }
if (q[t].r == mid) { ans[q[t].id] = cnt[q[t].l]; continue; }
p1 = q[t].l;
ap1 = ap2 = mid;
for (ll i = dep; i >= -1; i -- ) {
ll p = (i == -1 ? q[t].l : fa[i][p1]);
if (p == mid || !p) continue;
p2 = q[t].r; ap3 = mid;
for (ll j = dep; j >= -1; j -- ) {
ll c = (j == -1 ? q[t].r : fa[j][p2]);
if (c == mid || !c) continue;
if ((h[c] - h[p]) * (fa[0][c] - p) < (h[fa[0][c]] - h[p]) * (c - p)) p2 = c;
else ap3 = c;
}
if ((h[ap3] - h[p]) * (fa[0][p] - p) < (h[fa[0][p]] - h[p]) * (ap3 - p)) p1 = p;
else ap1 = p, ap2 = ap3;
}
ans[q[t].id] = cnt[q[t].l] + cnt[q[t].r] - cnt[ap1] - cnt[ap2] + 2;
}
}
int main() {
cin >> n;
for (ll i = 1; i <= n; i ++ ) cin >> h[i];
cin >> m;
for (ll i = 1; i <= m; i ++ ) cin >> q[i].l >> q[i].r, q[i].id = i;
solve(1, n, 1, m);
for (ll i = 1; i <= m; i ++ ) cout << ans[i] - 1 << "\n";
}
```