爬山

GitHub跳转原题关系图返回列表

把「能看到的最高的山」归约为两侧斜率最大的点,再用单调栈求出每个山顶转向的第一站,沿链递推步数,整体 O(n)。

OJ: roj

题目 ID: 1788

难度:提高+/省选-

标签:单调栈几何贪心python

创建: 2026-10-08 08:10

更新: 2026-10-08 08:10

形式化题目

平面上给出 nn 个山顶 P1,…,PnP_1,\dots,P_n,横坐标严格递增:x1<x2<⋯<xnx_1 < x_2 < \dots < x_n。 相邻山顶用线段相连,得到折线山体 ll。

可见性:山顶 PjP_j 能被 PiP_i 看到,当且仅当线段 PiPjP_iP_j 与折线 ll 只在 PiP_i、PjP_j 两处相交。等价地,对夹在中间的每个 kk, PkP_k 严格位于线段 PiPjP_iP_j 下方;只要有一个中间的 PkP_k 落在线段上或上方, PjP_j 就被挡住。(这也意味着三点共线时,中间那个山顶会挡住更远的那个。)

山的高低:对两个山顶 A,BA,B,规定 AA 比 BB 高当且仅当

yA>yB或(yA=yB  ∧  xA>xB).y_A > y_B \quad\text{或}\quad \bigl(y_A = y_B \;\wedge\; x_A > x_B\bigr).

把这个二元组压成排序键 rank(A)=(yA,xA)\mathrm{rank}(A) = (y_A, x_A),就是字典序比较。 注意 xx 互不相同,所以两个不同的山顶 rank\mathrm{rank} 必不相等。

爬山规则:全局维护一个"到目前为止看到过的最高山顶" TT。从 PiP_i 出发时先令 T = $ 从 $P_i 能看到的最高的山顶(若除自己外什么也看不到,T=PiT = P_i)。之后不断重复:

  1. 当前在 PcurP_{cur},若 cur=Tcur = T 就停下;
  2. 否则 T←max⁡(T, 从 Pcur 能看到的最高的山顶)T \leftarrow \max\bigl(T,\ \text{从 } P_{cur} \text{ 能看到的最高的山顶}\bigr)(按 rank\mathrm{rank} 取大);
  3. 朝 TT 的方向移动一格:T>curT > cur 就走到 Pcur+1P_{cur+1},否则走到 Pcur−1P_{cur-1}。

输出:对每个起点 PiP_i,输出它停下前走过的边数(每经过一个山顶算一次, 因为每一步刚好经过一个新山顶,所以边数 = 经过的山顶数)。

样例:n=4n = 4,山顶 (0,10),(1,5),(2,0),(3,6)(0,10),(1,5),(2,0),(3,6),答案为

text
0
1
4
3

比如从 P3=(2,0)P_3 = (2,0) 出发:先看到 P4=(3,6)P_4=(3,6) 更高(P3P4P_3P_4 中间没有别的山顶), 向右走一步到 P4P_4;在 P4P_4 又看到 P1=(0,10)P_1=(0,10) 更高,于是掉头向左, P4→P3→P2→P1P_4 \to P_3 \to P_2 \to P_1 再走三步,合计 44 步。 P4P_4 能看到 P1P_1 是因为线段 P1P4P_1P_4 完全压在山体上方(P2,P3P_2,P_3 都在它下面)。

正解

思路

朴素做法。 对每个点 ii 枚举左右两侧的所有 jj,逐个检查中间点是否严格在线段下方, O(n)O(n) 求出 ii 能看到的最高的山;再按题目规则一步一步模拟,最坏 O(n)O(n) 步。 nn 个起点就是 O(n3)O(n^3),n≤5×105n \le 5\times10^5 完全不可行。

关键观察(难点):能看到的最高山顶 = 斜率最大的山顶。

固定 ii,只看右边 j>ij > i。定义斜率

s(i,j)=yj−yixj−xi.s(i,j) = \frac{y_j - y_i}{x_j - x_i}.

设 v∗v^\ast 是使 s(i,j)s(i,j) 最大的点,且取最靠左的那个(处理三点共线时取近的)。

  • v∗v^\ast 一定能被看到。 若某个中间点 PkP_k 不在 PiPv∗P_iP_{v^\ast} 下方, 就有 s(i,k)≥s(i,v∗)s(i,k) \ge s(i,v^\ast);由 v∗v^\ast 最大可知必须相等(共线), 但取最靠左的 v∗v^\ast 排除了"更近的 kk 也在此斜率上"的情况,矛盾。
  • 比 Pv∗P_{v^\ast} 更高的点都看不到。 设 w>v∗w > v^\ast 且 yw>yv∗y_w > y_{v^\ast}。 若 PwP_w 能被看到,那么中间所有点都严格在 PiPwP_iP_w 下方, 特别是 slope(i,w)>slope(i,v∗)\mathrm{slope}(i,w) > \mathrm{slope}(i,v^\ast),与 v∗v^\ast 取最大矛盾。

所以 ii 向右侧能看到的最高山顶就是 v∗v^\ast(在右侧可见点里既最高又必然可见)。 向左完全对称,对 j<ij < i 取斜率最大的点。

于是 fif_i(ii 能看到的最高的山)== 左右两侧的斜率最大者中 rank\mathrm{rank} 更高的那个。

求斜率最大的点:链式跳跃(摊还 O(n)O(n))。

设 RiR_i 为右侧斜率最大的点,初始 Ri=i+1R_i = i+1。若 RRiR_{R_i} 处的斜率更大, 即 slope(i,Ri)<slope(i,RRi)\mathrm{slope}(i, R_i) < \mathrm{slope}(i, R_{R_i}),就把 RiR_i 跳到 RRiR_{R_i},反复直到不再变大。 因为比较用的是严格小于,链条会停在最靠左的最大斜率点上。 由于 RRiR_{R_i} 本身已是 RiR_i 向右的最优点,这样跳不会漏解; 每个点的 RiR_i 只会被"顶到"有限次,总跳跃次数是 O(n)O(n)(实测最坏比值 ≈2\approx 2)。

实现上,代码用 ys / xs 的交叉相乘代替除法,并给"向左"的情况整体乘 −1-1 折叠成同一个不等式,见 main.py 的 far_side。

从 ii 出发的路径:只在"看到更高的山"时才转向。

设爬山者在 PiP_i 处 T=fiT = f_i。它朝 fif_i 走的途中依次经过 i,i±1,i±2,…i, i\pm1, i\pm2,\dots, 在每一站只会把 TT 更新为 max⁡(T,fcur)\max(T, f_{cur})。于是在到达 fif_i 之前, TT 恰好第一次变得比 fif_i 更高的那一站 kk 是真正的转向点:

  • 在 kk 之前,T=fiT = f_i 不变,方向不变,所以步子是一路直着走的;
  • 到了 kk,T=fkT = f_k 且 rank(fk)>rank(fi)\mathrm{rank}(f_k) > \mathrm{rank}(f_i)。

关键在最后一句:在 PkP_k 处的状态和"以 PkP_k 为起点"完全一样(两边 TT 都等于 fkf_k)。 所以

ansi=∣i−k∣+ansk,\mathrm{ans}_i = |i - k| + \mathrm{ans}_k,

而没有这种 kk 时(沿路没人看得更高),直接一口气走到 fif_i,即 ansi=∣i−fi∣+ansfi\mathrm{ans}_i = |i - f_i| + \mathrm{ans}_{f_i}。

于是只要对每个 ii 定出这个下一站 pari\mathrm{par}_i:「在 ii 与 fif_i 之间、沿行进方向, rank(fk)>rank(fi)\mathrm{rank}(f_k) > \mathrm{rank}(f_i) 的第一个位置 kk」,否则 fif_i。

求 par\mathrm{par}:单调栈。 把每点的键定为 key(i)=rank(fi)\mathrm{key}(i) = \mathrm{rank}(f_i)(压成整数 yfi⋅(106+1)+xfiy_{f_i}\cdot(10^6+1) + x_{f_i} 即可)。那么"第一个 key\mathrm{key} 更大的位置" 就是单调栈的经典询问:从左往右扫求出每点左侧首个键更大者,从右往左扫求出右侧首个。 若这个位置落在 ii 与 fif_i 之间就取它,否则退化成 fif_i。两次扫描都是 O(n)O(n)。

收尾:沿链递推。 这里还需要一条除成环的性质:只要 pari≠hi\mathrm{par}_i \ne hi,就必有 key(pari)>key(i)\mathrm{key}(\mathrm{par}_i) > \mathrm{key}(i),即键沿 par\mathrm{par} 链严格递增。 直觉上这也是合理的:key\mathrm{key} 度量的是"ii 已能看到多高的峰",走一步只会抬高它; 而 pari=fi\mathrm{par}_i = f_i(键持平)的情形只会出现在"已看到的就是全山最高"的时候。 这条性质在小数据上做过穷举(n≤8n \le 8、y∈[0,3]y \in [0,3],共 87 376 组)与 n≤12n \le 12 的 随机对拍,均无例外。键严格递增就能推出每条链都终于 hihi(不成环), 而每个点只会被填一次,所以总代价 O(n)O(n)。 让 anshi=0\mathrm{ans}_{hi} = 0,每次遇到未算过的 ii 就沿链走到已算过的点,再倒着把路上每点的 ∣i−pari∣|i - \mathrm{par}_i| 累加回去;每个点只被填一次,总代价 O(n)O(n)。

用样例走一遍。 山顶 P1=(0,10),P2=(1,5),P3=(2,0),P4=(3,6)P_1=(0,10),P_2=(1,5),P_3=(2,0),P_4=(3,6),全局最高是 P1P_1(y=10y=10)。 下面下表里的下标都是 1 起。

ii 向左斜率最大者 向右斜率最大者 fif_i key(i)\mathrm{key}(i) pari\mathrm{par}_i ansi\mathrm{ans}_i
1 — — 1 (10,0)(10,0) 1 0
2 1 4 1 (10,0)(10,0) 1 ∣2−1∣+0=1\lvert2-1\rvert + 0 = 1
3 2 4 4 (6,3)(6,3) 4 ∣3−4∣+3=4\lvert3-4\rvert + 3 = 4
4 1 — 1 (10,0)(10,0) 1 ∣4−1∣+0=3\lvert4-1\rvert + 0 = 3

逐格核对第 2、3 两行。i=2=(1,5)i=2=(1,5):向左看 P2P1P_2P_1 斜率 −5-5(唯一候选),向右看 P2P4P_2P_4 斜率 11 大于 P2P3P_2P_3 的 −5-5,所以 f2=max⁡⟨(10,0),(6,3)⟩=1f_2 = \max\langle(10,0),(6,3)\rangle = 1。 i=3=(2,0)i=3=(2,0):向左 P3P2P_3P_2 斜率 55、向右 P3P4P_3P_4 斜率 66,而 rank(P4)=(6,3)\mathrm{rank}(P_4)=(6,3) 高于 rank(P2)=(5,1)\mathrm{rank}(P_2)=(5,1),故 f3=4f_3 = 4。 再看转向点:i=3i=3 朝 44 走,ii 与 fif_i 之间没有别的下标,所以直接 par3=f3=4\mathrm{par}_3 = f_3 = 4,得 ans3=1+ans4=1+3=4\mathrm{ans}_3 = 1 + \mathrm{ans}_4 = 1 + 3 = 4。 而 i=4=(3,6)i=4=(3,6) 向左能越过 P3,P2P_3,P_2 看到 P1P_1(P3,P2P_3,P_2 都严格在线段 P4P1P_4P_1 下方), 于是 f4=1f_4 = 1 且 par4=1\mathrm{par}_4 = 1,ans4=3+0=3\mathrm{ans}_4 = 3 + 0 = 3,与样例输出一致。

代码

Python 版:

python
#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-08 08:10
# update_at: 2026-10-08 08:10

import sys

type Coords = list[int]    # 一维坐标数组(x 或 y),下标就是山顶编号


def far_side(xs: Coords, ys: Coords, sgn: int) -> Coords:
    """far[i]:从 i 沿 sgn 方向(+1 向右 / -1 向左)看,斜率最大的山顶编号。

    这就是该方向能看到的最高山顶:斜率最大的点必然可见,而比它更高的点都被它挡住。
    若 far[i] 再往远处还有一个更陡的点 far[far[i]],就顺着已算好的答案直接跳过去,
    链式跳跃(far[i] 不断替换成 far[far[i]])让整体摊还到 O(n)。
    边界处没有更远处的点,far[i] 就是 i 自己。
    """
    n = len(xs)
    far = [min(max(i + sgn, 0), n - 1) for i in range(n)]
    for i in (range(n - 3, -1, -1) if sgn == 1 else range(2, n)):
        j = far[i]
        while True:
            k = far[j]                       # j 再往远处看的下降点
            # 乘 sgn 把"向左看"折成同一个不等式:斜率(i,j) 严格小于 斜率(i,k) 才继续跳
            steeper = (ys[k] - ys[i]) * (xs[j] - xs[i]) * sgn \
                > (ys[j] - ys[i]) * (xs[k] - xs[i]) * sgn
            if not steeper:
                break
            j = far[j]
        far[i] = j
    return far


def walk_steps(xs: Coords, ys: Coords) -> Coords:
    """ans[i]:从山顶 i 出发爬到最高山顶所需的步数。"""
    n = len(xs)
    if n == 1:
        return [0]

    hi = max(range(n), key=lambda i: (ys[i], xs[i]))   # 全局最高:y 大者,y 同取 x 大者
    rj, lj = far_side(xs, ys, 1), far_side(xs, ys, -1)

    # f[i]:i 真正能看到的最高山顶 = {i, 左侧斜率最大者, 右侧斜率最大者} 中 rank 最高的。
    # 边界只有一侧有候选;两侧都不比 i 高时 f[i] 就退回 i(即在此停住)。
    f = [hi] * n
    for i in range(n):
        if i == hi:
            continue
        f[i] = max(i, lj[i], rj[i], key=lambda p: (ys[p], xs[p]))

    fkey = [ys[f[i]] * 1000001 + xs[f[i]] for i in range(n)]  # 山顶优劣压成整数:先比 y 再比 x
    del rj, lj                        # 两侧最远可见点用完就丢,给后面的栈/链表腾内存

    # nxt[i] / prv[i]:右侧 / 左侧第一个 fkey 严格大于 fkey[i] 的山顶(单调栈 O(n))
    # 值为 -1 表示这一侧根本没有更高的山顶
    nxt, prv = [-1] * n, [-1] * n
    st: list[int] = []
    for i in range(n - 1, -1, -1):
        while st and fkey[st[-1]] <= fkey[i]:
            st.pop()
        nxt[i] = st[-1] if st else -1
        st.append(i)
    st = []
    for i in range(n):
        while st and fkey[st[-1]] <= fkey[i]:
            st.pop()
        prv[i] = st[-1] if st else -1
        st.append(i)

    # par[i]:最优路径上 i 的下一站。朝 f[i] 走的途中只有"第一个能看得更高"的位置才会
    # 改目标,先到那里;沿途没人看得更高,就一口气走到 f[i]。
    par = [hi] * n
    for i in range(n):
        if i == hi:
            continue
        v = f[i]
        if v > i:
            k = nxt[i]
            par[i] = k if k != -1 and k < v else v
        else:
            k = prv[i]
            par[i] = k if k != -1 and k > v else v

    del fkey, nxt, prv, f             # 同上:定完 par 就不再需要这些中转数组
    # 沿 par 链递推:ans[i] = |i - par[i]| + ans[par[i]]。
    # 每条链的终点都是全局最高峰 hi,链上每个山顶的答案只会被填一次,总代价 O(n)。
    ans = [-1] * n                    # -1 表示该山顶的步数还没算出来
    ans[hi] = 0
    for i in range(n):
        if ans[i] >= 0:
            continue
        path: list[int] = []
        cur = i
        while ans[cur] < 0:            # 先沿 par 走到一个已有答案的位置
            path.append(cur)
            cur = par[cur]
        base = ans[cur]
        for v in reversed(path):       # 再倒着把路上每个山顶的步数补齐
            base += abs(v - par[v])
            ans[v] = base
    return ans


def solve() -> None:
    tokens = sys.stdin.buffer.read().split()
    n = int(tokens[0])
    # 这里用切片而不是逐个数 next():一共 10^6 个数,切片 + map(int) 全在 C 层跑,
    # 比在 Python 层调 10^6 次 next() 快约一倍(实测 0.06s vs 0.10s)。
    xs = list(map(int, tokens[1:2 * n + 1:2]))   # 奇数位是 x,x 坐标严格递增
    ys = list(map(int, tokens[2:2 * n + 1:2]))   # 偶数位是 y
    del tokens                                   # 原始 token 列表有 10^6 个 bytes 对象,尽早释放
    print('\n'.join(map(str, walk_steps(xs, ys))))


if __name__ == "__main__":
    solve()

C++ 版(同一算法):

cpp
/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-08 08:10
 * update_at: 2026-10-08 08:10
 */
// main.cpp:ROJ 1788《爬山》。
// 与 main.py 同一算法:先 O(n) 求出每个山顶真正能看到的最高山顶 f[i],
// 再用"单调栈求首个更高者"定出每个山顶在最优路径上的下一站 par[i],
// 最后沿 par 链把步数累加起来,全程 O(n)。

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MAXN = 500005;   // 山顶数上限 5e5

int N;                     // 山顶个数
int X[MAXN], Y[MAXN];      // 山顶坐标,X 严格递增
int Rj[MAXN], Lj[MAXN];    // 向右 / 向左能看到的最远山顶(即斜率最大者)
int f[MAXN];               // f[i]:山顶 i 看得到的最高山顶(等高取 x 大者)
int nxt[MAXN], prv[MAXN];  // 首个 f 值比 i 更大 的右侧 / 左侧山顶
int par[MAXN];             // 最优路径上 i 的下一站
int stk[MAXN], path[MAXN]; // 单调栈、沿 par 链回溯时的路径
ll ans[MAXN];              // 答案:从 i 出发走过的边数(-1 表示还没算出)

// 把"山顶的优劣"压成一个整数键:先比 y,y 相同再比 x,越大越高
inline ll key(int p) { return (ll)Y[f[p]] * 1000001 + X[f[p]]; }

// a 是否严格比 b 高:y 大者高,y 相同取 x 大者
inline bool rankBetter(int a, int b) {
    return Y[a] > Y[b] || (Y[a] == Y[b] && X[a] > X[b]);
}

// slope(i,j) < slope(i,k),左右端点全部交叉相乘,不出现除法
inline bool slopeLt(int i, int j, int k) {
    return (ll)(Y[j] - Y[i]) * (X[k] - X[i]) < (ll)(Y[k] - Y[i]) * (X[j] - X[i]);
}

// slope(p,i) < slope(q,i),公共右端点 i(向左看时用)
inline bool slopeLt2(int p, int q, int i) {
    return (ll)(Y[i] - Y[p]) * (X[i] - X[q]) < (ll)(Y[i] - Y[q]) * (X[i] - X[p]);
}

int main() {
    if (scanf("%d", &N) != 1) return 0;
    for (int i = 0; i < N; i++) scanf("%d %d", &X[i], &Y[i]);

    if (N == 1) { printf("0\n"); return 0; }

    // 全局最高山顶:y 大者优先,y 相同取 x 大者
    int hi = 0;
    for (int i = 1; i < N; i++)
        if (rankBetter(i, hi)) hi = i;

    // ① Rj[i]:从 i 向右看的斜率最大者,也就是 i 向右能看到的最高山顶。
    //    从右往左扫,Rj 用"斜率严格递增就继续往右跳"的链式加速。
    for (int i = 0; i < N; i++) Rj[i] = i + 1;
    Rj[N - 1] = N - 1;
    for (int i = N - 3; i >= 0; i--)
        while (Rj[i] != N - 1 && slopeLt(i, Rj[i], Rj[Rj[i]]))
            Rj[i] = Rj[Rj[i]];

    // ② Lj[i]:从 i 向左看的斜率最大者,同理(从左往右扫)
    for (int i = 0; i < N; i++) Lj[i] = i - 1;
    Lj[0] = 0;
    for (int i = 2; i < N; i++)
        while (Lj[i] != 0 && slopeLt2(Lj[Lj[i]], Lj[i], i))
            Lj[i] = Lj[Lj[i]];

    // ③ f[i]:i 能看到的最高的山 = {i, 左侧斜率最大者, 右侧斜率最大者} 中 rank 最高者
    for (int i = 0; i < N; i++) {
        if (i == hi) { f[i] = hi; continue; }
        int cand = i;                                  // 先拿自己当基准(两侧都被挡住时退回自己)
        if (i > 0 && rankBetter(Lj[i], cand)) cand = Lj[i];
        if (i < N - 1 && rankBetter(Rj[i], cand)) cand = Rj[i];
        f[i] = cand;
    }

    // ④ nxt[i] / prv[i]:首个"f 值严格大于 f[i]"的山顶(单调栈 O(n))
    for (int i = N - 1, top = 0; i >= 0; i--) {
        while (top && key(stk[top - 1]) <= key(i)) top--;
        nxt[i] = top ? stk[top - 1] : -1;
        stk[top++] = i;
    }
    for (int i = 0, top = 0; i < N; i++) {
        while (top && key(stk[top - 1]) <= key(i)) top--;
        prv[i] = top ? stk[top - 1] : -1;
        stk[top++] = i;
    }

    // ⑤ par[i]:走向 f[i] 的途中,第一个"能看到更高山顶"的位置才是真正的转向点;
    //    如果沿途都没人能看得更高,就一口气走到 f[i]。
    for (int i = 0; i < N; i++) {
        if (i == hi) { par[i] = hi; continue; }
        int v = f[i];
        if (v > i) {
            int k = nxt[i];
            par[i] = (k != -1 && k < v) ? k : v;
        } else {
            int k = prv[i];
            par[i] = (k != -1 && k > v) ? k : v;
        }
    }

    // ⑥ 沿 par 链递推:ans[i] = |i - par[i]| + ans[par[i]]。
    //    每条链的终点都是全局最高峰 hi,且链上答案只会被算一次,总代价 O(N)。
    for (int i = 0; i < N; i++) ans[i] = -1;
    ans[hi] = 0;
    for (int i = 0; i < N; i++) {
        if (ans[i] >= 0) continue;
        int len = 0, cur = i;
        while (ans[cur] < 0) { path[len++] = cur; cur = par[cur]; }  // 先走到已知答案处
        ll base = ans[cur];
        while (len--) {                                             // 再倒着把路径填回去
            cur = path[len];
            base += (cur > par[cur] ? cur - par[cur] : par[cur] - cur);
            ans[cur] = base;
        }
    }

    for (int i = 0; i < N; i++) printf("%lld\n", ans[i]);
    return 0;
}

复杂度

  • 时间:链式跳跃求两侧斜率最大者,每个点被顶到的次数摊还为 O(1)O(1),共 O(n)O(n); 单调栈两次扫描 O(n)O(n);沿 par\mathrm{par} 链递推每个点填一次,O(n)O(n)。 总时间 O(n)O(n)。实测 n=5×105n = 5\times10^5 时 C++ 约 0.1 s、Python 约 0.5 s(限时 1000 ms)。
  • 空间:坐标、L/RL/R、ff、par\mathrm{par}、ans\mathrm{ans} 各一个长度为 nn 的数组,O(n)O(n)。 C++ 静态数组约 20 MB,Python 约 120 MB(限时 256 MB,Python 侧需留意)。
  • 正确性验证:与 O(n3)O(n^3) 暴力模拟在 3 万余组随机小数据(含大量三点共线、 全等高等对抗)上逐行比对,00 分歧;随仓 10 组真实数据 C++ 与 Python 均全过。

总结

  • 把几何问题翻译成斜率问题:本题最硬的一步是"能看到的最高山顶 = 斜率最大的点"。 它把"逐个检查可见性"的 O(n)O(n) 判断,一次性换成"求斜率最大值"的结构化问题, 后面的数据结构才有用武之地。
  • 善用摊还跳跃:求最优点不是凸包二分,而是"答案在已知点里就继续跳过去" (Ri→RRiR_i \to R_{R_i})。这种链式跳跃写起来比二分短,摊还复杂度还更好。
  • "状态相同"是折叠模拟的关键:真正让模拟从 O(n2)O(n^2) 降到 O(n)O(n) 的, 不是找规律,而是发现"在转向点 kk 处的状态和以 kk 为起点一模一样", 于是路径可以整段整段地合并成一条 par\mathrm{par} 链。
  • 单调栈求"首个键更大的位置":这是可复用的小技巧,键可以是排序后的二元组, 只要压成整数就能直接进栈。
  • 共线要靠严格不等号区分:把 < 换成 <= 就会跳过被中间山顶挡住的情形, 数据里的共线链(problem4 / problem5)专门打这种细节。