概要

この問題は、与えられた区間 \([L_j, R_j]\) において、左端の山から右へ順に見ていったときに「それまでの最大標高以上の高さを持つ山」が何個あるかを、クエリごとに高速に求める問題です。

ダブリング（倍増法）と単調スタック（Monotonic Stack）を用いることで、各クエリに対して高速に回答することができます。

---

考察

1. 素朴なアプローチとその限界

最も単純な方法は、各クエリ \((L, R)\) に対して、実際に \(L\) から \(R\) までループを回し、それまでの最大標高を更新しながら見える山を数える方法です。

しかし、この方法では 1 つのクエリを処理するのに最悪で \(O(N)\) の時間がかかります。クエリ数が \(Q\) 個あるため、全体の計算量は \(O(NQ)\) となり、今回の制約（\(N, Q \le 2 \times 10^5\)）では実行時間制限（TLE）になってしまいます。クエリあたり \(O(\log N)\) や \(O(1)\) などの高速な処理が必要です。

2. 「次に見える山」への遷移に着目する

見える山の満たすべき条件を整理してみましょう。 区間内で山 \(i\) が見えているとき、その次に見える山はどのような山でしょうか？

それは、「山 \(i\) より右側にあり、標高が \(H_i\) 以上である最初の山」になります。 なぜなら、山 \(i\) とその「次に標高が \(H_i\) 以上になる山」の間にある山は、すべて標高が \(H_i\) 未満であるため、山 \(i\) に遮られて見えなくなるからです。

山 \(i\) の次に見える山のインデックスを \(next\_idx[i]\) と呼ぶことにします。 すると、区間 \([L, R]\) で見える山は、以下のように一意に遷移していきます。

\[L \to next\_idx[L] \to next\_idx[next\_idx[L]] \to \cdots\]

この遷移を、遷移先が右端 \(R\) を超える直前まで繰り返したときの「遷移の回数 \(+ 1\)（最初の \(L\) の分）」が、求める見える山の個数になります。

3. 高速化のアイデア（ダブリング）

遷移を 1 つずつ辿っていくと、最悪で \(O(N)\) 回の遷移が必要になり高速化できません。 しかし、「次に遷移する先が一意に決まる」という性質があるため、ダブリング（倍増法）を適用できます。

ダブリングとは、「\(1, 2, 4, 8, \ldots\) ステップ先の遷移先」を前もって計算しておくことで、任意のステップ先の遷移先を \(O(\log N)\) で求められるようにする手法です。

---

アルゴリズム

具体的には、以下の 3 つのステップで解を求めます。

ステップ 1: \(next\_idx\) の構築（単調スタック）

各山 \(i\) について、右側で最初に標高が \(H_i\) 以上となる山のインデックス \(next\_idx[i]\) を求めます。 これは、配列を右から左へ走査しながらスタックを維持することで、全体で \(O(N)\) で計算できます。

1. 右端のさらに外側（インデックス \(N+1\)）に、どの山よりも高い「番兵（標高 \(2 \times 10^9\)）」を配置します。
2. 右から順に山 \(i\) を見ていきます。
3. スタックの先頭にある山の標高が \(H_i\) 未満である限り、スタックから要素を取り除きます（ポップ）。
4. この操作が終わったとき、スタックの先頭にある山が「山 \(i\) の右側で最初に標高が \(H_i\) 以上になる山」です。これを \(next\_idx[i]\) とします。
5. 山 \(i\) をスタックに追加し、左の山へ進みます。

ステップ 2: ダブリングテーブルの構築

\(dp[k][i]\) を「山 \(i\) からスタートして \(2^k\) 回遷移した先の山のインデックス」と定義します。

初期状態（\(2^0 = 1\) 回の遷移）は、ステップ 1 で求めた \(next\_idx\) そのものです。 $\(dp[0][i] = next\_idx[i]\)$

\(2^{k+1}\) 回の遷移は、「\(2^k\) 回遷移した先から、さらに \(2^k\) 回遷移する」と言い換えられるため、以下の遷移式でテーブルを埋めることができます。 $\(dp[k+1][i] = dp[k][dp[k][i]]\)$

\(k\) の範囲は、遷移先が \(N\) を超えるまでカバーできればよいため、 \(2^K \ge N\) を満たす \(K \approx 18\) まで計算すれば十分です。

ステップ 3: クエリへの回答

各クエリ \((L, R)\) に対して、以下のように回答します。

1. 現在地を \(curr = L\)、答えを \(ans = 1\)（左端の山 \(L\) の分）とします。
2. \(k = K-1, K-2, \ldots, 0\) の順に、大きいステップから試していきます。
3. もし \(2^k\) 回遷移した先が \(R\) 以下（\(dp[k][curr] \le R\)）であれば、実際にその先へジャンプし（\(curr = dp[k][curr]\)）、答えに \(2^k\) を加算します（\(ans \leftarrow ans + 2^k\)）。
4. これを \(k=0\) まで繰り返したときの \(ans\) が、そのクエリで見える山の個数です。

---

計算量

• 時間計算量: \(O((N + Q) \log N)\)
  • \(next\_idx\) の構築: スタックへの要素の追加・削除は各要素につき高々 1 回なので \(O(N)\) です。
  • ダブリングテーブルの構築: \(O(N \log N)\) です。
  • クエリの処理: 1 クエリあたり \(O(\log N)\) で処理できます。\(Q\) 個のクエリ全体で \(O(Q \log N)\) です。
• 空間計算量: \(O(N \log N)\)
  • ダブリング用のテーブル \(dp\) のサイズが \(K \times (N+2)\) となり、これが空間計算量のボトルネックになります。

---

実装のポイント

• 番兵の役割: 右側に自分以上の高さの山が存在しない場合、遷移先が配列の外に出てしまいます。これを防ぐために、末尾に非常に高い山（標高 \(2 \times 10^9\) などの十分大きな値）を番兵として配置しておくことで、例外処理をすることなくシンプルに実装できます。

  ソースコード

import sys


def solve():
    input_data = sys.stdin.read().split()
    if not input_data:
        return

    N = int(input_data[0])
    Q = int(input_data[1])

    H = [0] * (N + 2)
    for i in range(N):
        H[i + 1] = int(input_data[2 + i])
    H[N + 1] = 2000000000

    next_idx = [0] * (N + 2)
    stack = [N + 1]
    for i in range(N, 0, -1):
        h = H[i]
        while H[stack[-1]] < h:
            stack.pop()
        next_idx[i] = stack[-1]
        stack.append(i)
    next_idx[N + 1] = N + 1

    K = 18
    dp = [None] * K
    dp[0] = next_idx
    for k in range(K - 1):
        prev = dp[k]
        dp[k + 1] = [prev[p] for p in prev]

    out = []
    idx = 2 + N
    for _ in range(Q):
        L = int(input_data[idx])
        R = int(input_data[idx + 1])
        idx += 2

        curr = L
        ans = 1
        for k in range(K - 1, -1, -1):
            nxt = dp[k][curr]
            if nxt <= R:
                curr = nxt
                ans += 1 << k
        out.append(str(ans))

    print("\n".join(out))


if __name__ == "__main__":
    solve()

---

この解説は gemini-3.5-flash-thinking によって生成されました。