---
lang: ja-jp
tags: APIO
---
# APIO 2021-B 熱帯⾬林における跳躍 (Rainforest Jumps)

はじめて Sparse Table 使った

## 問題文

https://github.com/ia-toki/apio-2021-statements/blob/master/jumps/ja_JP.pdf
https://oj.uz/problem/view/APIO21_jumps

長さ $N$ の数列 $H$ があります。$H[i]$ は pairwise distinct です。
位置 $i$ にいるとき、$1$ 回の操作で $H[j] ≥ H[i]$ であるような $j$ のうち $i$ の隣に移動することができます。
$Q$ 回のクエリが与えられます。
各クエリでは $A ≤ B < C ≤ D$ が与えられます。$[A, B]$ のいずれかから始めて $[C, D]$ の中に移動するための最小の操作回数を求めてください。

$N ≤ 2 \times 10^5,\ Q ≤ 10^5$

## 考察

まずは移動できる条件を考える。
$X = \max H[B, C),\ Y = \max H[C, D]$ とする。
少なくとも $X$ までは上がる必要があって、そこから右を連打すればいいので、条件は $X < Y$ 。
スタートする地点はできるだけ高い方がいいので、$H[i] < Y$ であるような $i \in [C, D]$ のうち $H[i]$ が最大のもの。
右が低くて左が高い場合、右に行っても左の見え方は変わらないので、左右で高い方を選んだ方が効率的に高さを上げられる。ただし、$Y$ を超えてはいけない。
$Y$ を超えないように $o(N)$ で選ぶにはダブリングをすると良い。

1. $X$ を超えないように高い方を選ぶダブリング
2. 1 手進んで $h < Y$ なら OK
3. $X$ を超えないように低い方を選ぶダブリング
4. 1 手進むと $h < Y$ なので OK

## 実装

スタート地点を選ぶときに $Y$ 未満での最小を選ぶ必要があるので、$Y$ 以上が含まれていたらそれより左を無視するみたいなことが必要。
セグ木よりも Sparse Table のほうがうまく実装できる。

https://oj.uz/submission/414614

#include <bits/stdc++.h>
using namespace std;
 
int N, lgN;
vector<vector<int>> rmq, low, high;

void init(int N, vector<int> H) {
    ::N = N;
    lgN = __lg(N);
    rmq.assign(lgN + 1, vector<int>(N));
    low.assign(lgN + 1, vector<int>(N, -1));
    high.assign(lgN + 1, vector<int>(N, -1));
    rmq[0] = H;
    for(int i = 0; i < lgN; i++) for(int j = 0; j + (2 << i) <= N; j++) rmq[i + 1][j] = max(rmq[i][j], rmq[i][j + (1 << i)]);
    vector<int> q;
    for(int i = 0; i < N; i++){
        while(q.size() && H[q.back()] < H[i]){
            const int j = q.back();
            q.pop_back();
            low[0][j] = i;
        }
        q.push_back(i);
    }
    for(int i = N; i--; ){
        while(q.size() && H[q.back()] < H[i]){
            const int j = q.back();
            q.pop_back();
            high[0][j] = i;
        }
        q.push_back(i);
    }
    for(int i = 0; i < N; i++) if(int &x = low[0][i], &y = high[0][i]; x != -1 && (y == -1 || H[x] > H[y])) swap(x, y);
    for(int i = 0; i < lgN; i++) for(int j = 0; j < N; j++) if(low[i][j] != -1) low[i + 1][j] = low[i][low[i][j]];
    for(int i = 0; i < lgN; i++) for(int j = 0; j < N; j++) if(high[i][j] != -1) high[i + 1][j] = high[i][high[i][j]];
}

int get(int l, int r){
    const int x = __lg(r - l);
    return max(rmq[x][l], rmq[x][r - (1 << x)]);
}
 
int minimum_jumps(int A, int B, int C, int D) {
    auto& H = rmq[0];
    const int X = get(B, C), Y = get(C, D + 1);
    if(X >= Y) return -1;
    {
        int a = B;
        for(int i = lgN; i >= 0; i--) if(const int a2 = a - (1 << i); a2 >= A && get(a2, B + 1) < Y) a = a2;
        A = a;
    }
    const int s = get(A, B + 1);
    if(s >= X) return 1;
    int ans = 2, at = A;
    for(int i = lgN; i >= 0; i--) if(const int at2 = at + (1 << i); at2 < B + 1 && get(at2, B + 1) >= s) at = at2;
    for(int i = lgN; i >= 0; i--) if(high[i][at] != -1 && H[high[i][at]] < X){
        ans += 1 << i;
        at = high[i][at];
    }
    if(high[0][at] != -1 && H[high[0][at]] < Y) return ans;
    for(int i = lgN; i >= 0; i--) if(low[i][at] != -1 && H[low[i][at]] < X){
        ans += 1 << i;
        at = low[i][at];
    }
    return ans;
}