Super Bunny Man！

哎以为自己写了个 $3\log$ 结果跑的比别人 $2\log$ 还快。吓哭了。后面发现算错了。/咦

题意

给定 $n$ 个点 $(i,h_i)$，$q$ 次询问区间 $l,r$，求区间凸包的点数。

$n,q\le 10^5$，$h_i\le 10^{12}$。

思路

注意到一个叫做「存在 $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)$。能过就行。

代码

#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";
}