{{ self.title() }}

by 杨宇辰（command_block）

## 题目简述

给出 $h_{1\sim n}$，若水位为 $L$，在平面直角坐标系上标记点 $(i,h_i)$ 和 $(i,2L-h_i)$，共 $2n$ 个点。

对于两个点 $(x_1,y_1),(x_2,y_2)$，若满足 $x_2=x_1+1$ 且 $y_1<y_2$，则在两个点之间连一条有向边。

若存在一个 $L$（正实数），使得可以从 $x=u$ 上的某点通过有向边到达 $x=v$ 上的某点（$u<v$），则称 $(u,v)$ 是“好对子”。求出“好对子”的总数。

数据范围：$2\leq n\leq 5\times 10^5$，$1\leq h_i\leq 10^{12}$。

## 测试点设计

| 测试点编号 | 分值 | 限制                 | 说明                                       |
| ---------- | ---- | -------------------- | ------------------------------------------ |
| 1~2        | $8$  | $n\leq 10$           |                                            |
| 3~4        | $8$  | $n\leq 100$          | 复杂度为 $O\big(n^3\big)$ 或更高的朴素暴力 |
| 6~10       | $16$ | $n\leq 4000$         | 复杂度为 $O\big(n^2\big)$ 的暴力           |
| 11~18      | $32$ | $n\leq 10^5$         | 常数较大的 $O(n\log n)$ 算法               |
| 19~25      | $36$ | $n\leq 5\times 10^5$ | $O(n\log n)$ 算法                          |

## 算法1：$O\big(n^3\big)$ 暴力

称每个 $x$ 坐标为“一层”，只有相邻层之间有边。

点 $(i,h_i)$ 是固定不动的，点 $(i,2L-h_i)$ 会随着 $L$ 的变化而运动，相邻层之间的连边有 $O(1)$ 种可能的情况，每种情况生效的 $L$ 都是一个区间。

于是，我们可以将 $L$ 的可能取值划分为 $O(n)$ 个区间，每个区间内，有向图的结构都不变。

对于确定的图，简单 $O\big(n^2\big)$ 搜索（或递推）即可求出所有好对子，总复杂度 $O\big(n^3\big)$。

## 算法2：$O\big(n^2\big)$ 暴力

沿用算法1的思路，对 $L$ 分段讨论。

对于确定的图，按 $x$ 坐标从左往右 DP，记 $l_u$ 为在点 $u$ 结束的路径出发点 $x$​ 坐标的最小值，转移显然。所有的 $l$ 可以 $O(n)$ 求出。

记 $u_i=(i,h_i)$，$u_i'=(i,2L-h_i)$，$s_i=\min(l_{u_i},l_{u'_i})$，则 $(s_i,i),(s_i+1,i),\dots,(i-1,i)$​ 都是好对子。

对每个 $i$ 记录 $s_i$ 的最小值，则好对子总数为 $\sum_{i=1}^ni-s_i$。

## 算法3：$O(n\log n)$

对于固定的水位 $L$，石柱的像和本体的地位没有区别。可以记水面上方的落脚点高度为 $p_i=\max(h_i,2L-h_i)$，转化为所有石柱露出水面的情况。

若要有一条 $u\to v$ 的路径，直接观察 $p$ 上的特征，可以发现，存在 $t\in\{u\sim v-1\}$，使得 $p_{u\to t}$ 严格递减（在水下移动，对应的像严格递增），$p_{t+1\to v}$ 严格递增（在水上移动）。$p_t,p_{t+1}$ 之间是等号、不等号都可以。

不难发现这是充要条件。如果这个条件满足，必然存在一种水位使得方案存在。

形式化地，我们想要的是 $p_u>p_{u+1}>\dots>p_t\ ?\ p_{t+1}<\dots< p_v$。

让 $L$ 从小到大增加，$p$ 之间的不等号会逐个改变，可以用 `std::set` 维护合法的极长 `>>>?<<<` 区间。区间每次变化时（注意，可能有多个不等号同时变化），记下新的区间 $(l_i,r_i)$，使用单调栈求出所有区间的下包络，容易求出子区间总数。

## 算法4：$O(n\log n)$ 另解

$p_u>p_{u+1}>\dots>p_t\ ?\ p_{t+1}<\dots< p_v$ 可以转化为 $p_u\sim p_v$ 中不存在 $p_{i-1}\leq p_i\geq p_{i+1}$。

考虑水位变化给 $p$ 带来的影响。我们只关心相邻的 $p_i,p_{i+1}$ 的相对大小，不妨设 $h_i>h_{i+1}$，分类讨论可知

- 当 $L<\frac{h_i+h_{i+1}}{2}$ 时，$p_i>p_{i+1}$
- 当 $L>\frac{h_i+h_{i+1}}{2}$ 时, $p_i< p_{i+1}$
- 当 $L=\frac{h_i+h_{i+1}}{2}$ 时，$p_i=p_{i+1}$

另一种情况类似。

对于每个 $i$，“不存在 $p_{i-1}\leq p_i\geq p_{i+1}$”都对 $L$ 提出一个约束，形如“$L$ 不属于某区间”。

现在问题就转化成，给出 $N=n-1$ 个区间 $I_1,I_2,\dots,I_N$，求有多少对 $l,r$ 满足 $I_l\sim I_r$ 的并不是全集。

考虑用扫描线解决，枚举 $r$，我们要找到所有符合题意的 $l$。

先离散化，每次 $r$ 右移，新加入一个区间 $I_r$，将数组 $o$ 的区间 $I_r$ 赋值为 $r$。这样，数组 $o$ 中的最小值 $x_0$ 就是最薄弱的位置，$l\leq x_0$ 时能覆盖全集，$l>x_0$ 时不能。

（或者用双指针解决）复杂度 $O(n\log n)$​。