问题分析

在苏门答腊岛的热带雨林中，有 $N$ 棵树排成一排，每棵树有唯一的高度。猩猩的跳跃规则是：从当前树只能向左或向右跳到比当前树高的第一棵树上。

我们需要处理 $Q$ 个查询，每个查询给出起点区间 $[A,B]$ 和终点区间 $[C,D]$，要求判断是否存在从起点区间某棵树到终点区间某棵树的路径，并求最少跳跃次数。

关键观察

跳跃性质

单调栈结构：对于每棵树 $i$，向左和向右比它高的第一棵树可以通过单调栈预处理

决策规则：猩猩总是跳向左右两侧中高度较低的那棵更高的树

区间最大值：路径规划与区间最大值密切相关

核心思路

预处理每个树的左右邻居（比它高的第一棵树）

使用倍增方法快速模拟多步跳跃

利用区间最大值查询确定关键路径点

算法设计

预处理阶段 (init 函数)

计算左右边界：

使用单调栈计算每个树 $i$ 的 $l[i]$（左边第一个比它高的树）

使用单调栈计算每个树 $i$ 的 $r[i]$（右边第一个比它高的树）

构建倍增数组：

fa[0][i]：按照"跳向左右两侧中高度较低者"规则的下一个位置

jump[0][i]：另一个方向的位置（用于特殊情况）

构建 $M$ 层倍增表，支持快速多步跳跃

构建ST表：

用于快速查询任意区间的最大值及其位置

查询处理 (minimum_jumps 函数)

可行性判断：

找到终点区间 $[C,D]$ 中的最高树 $cd$

检查起点区间 $[A,B]$ 是否包含在 $cd$ 的左邻居的右边

路径规划：

在有效起点范围内选择最高树作为起点 $s$

检查中间区域 $[B+1, C-1]$ 的最大值 $val$

如果起点高度已超过中间最大值，只需1步

否则使用倍增方法模拟跳跃过程

跳跃计数：

使用 jump 数组进行大跨度跳跃

使用 fa 数组进行精细调整

返回总跳跃次数

复杂度分析

预处理：$O(N \log N)$

单调栈：$O(N)$

倍增数组：$O(N \log N)$

ST表：$O(N \log N)$

每次查询：$O(\log N)$

区间最大值查询：$O(1)$

倍增跳跃：$O(\log N)$

总结

该算法通过巧妙的预处理和倍增技术，高效解决了猩猩跳跃问题。核心在于利用单调栈确定跳跃目标，通过ST表快速定位关键点，使用倍增方法优化跳跃过程的模拟，最终在 $O(\log N)$ 时间内回答每个查询。

AC代码

#include <bits/stdc++.h>
#include "jumps.h"
#define pb push_back
#define popcnt __builtin_popcountll
#define debug printf("Passed line %d\n", __LINE__)

using namespace std;
typedef long long ll;
typedef pair<int, int> PII;

template<typename T> inline void checkmax(T &a, const T &b) {
    if (a < b)
        a = b;
}

template<typename T> inline void checkmin(T &a, const T &b) {
    if (a > b)
        a = b;
}

const int N = 2e5 + 5, M = 19;
int a[N], l[N], r[N], fa[M][N], jump[M][N], n;
PII st[M][N];
stack<int> s;

void init(int N, std::vector<int> H) {
    n = N;

    for (int i = 1; i <= n; i++)
        a[i] = H[i - 1], st[0][i] = {a[i], i};

    a[0] = a[n + 1] = 1e8;

    s.push(0);

    for (int i = 1; i <= n; i++) {
        while (a[i] > a[s.top()])
            s.pop();

        l[i] = s.top(), s.push(i);
    }

    while (!s.empty())
        s.pop();

    s.push(n + 1);

    for (int i = n; i >= 1; i--) {
        while (a[i] > a[s.top()])
            s.pop();

        r[i] = s.top(), s.push(i);
    }

    fa[0][0] = jump[0][0] = 0, fa[0][n + 1] = jump[0][n + 1] = n + 1;

    for (int i = 1; i <= n; i++) {
        if (a[l[i]] > a[r[i]])
            fa[0][i] = r[i], jump[0][i] = l[i];
        else
            fa[0][i] = l[i], jump[0][i] = r[i];
    }

    for (int i = 1; i < M; i++)
        for (int j = 0; j <= n + 1; j++)
            fa[i][j] = fa[i - 1][fa[i - 1][j]], jump[i][j] = jump[i - 1][jump[i - 1][j]];

    for (int i = 1; i < M; i++) {
        for (int j = 1; j + (1 << i) - 1 <= n; j++)
            st[i][j] = max(st[i - 1][j], st[i - 1][j + (1 << i - 1)]);
    }
}

PII query(int l, int r) {
    int d = __lg(r - l + 1);
    return max(st[d][l], st[d][r - (1 << d) + 1]);
}

int minimum_jumps(int A, int B, int C, int D) {
    A++, B++, C++, D++;
    int cd = query(C, D).second;

    if (l[cd] + 1 > B)
        return -1;

    int s = query(max(l[cd] + 1, A), B).second, val = 0, ans = 0;

    if (B + 1 <= C - 1)
        val = query(B + 1, C - 1).first;

    if (a[s] >= val)
        return 1;

    for (int i = M - 1; i >= 0; i--)
        if (a[jump[i][s]] < val)
            s = jump[i][s], ans += (1 << i);

    if (a[jump[0][s]] <= a[cd])
        return ans + 2;

    for (int i = M - 1; i >= 0; i--)
        if (a[fa[i][s]] < val)
            s = fa[i][s], ans += (1 << i);

    return ans + 2;
}