概要

山脈を西側から見たとき、指定区間内で「見える」山の個数を各クエリに対して求める問題。単調スタックで次に見える山への遷移を前計算し、ダブリング（二分持ち上げ）で各クエリに高速に回答する。

考察

「見える」条件の言い換え

山 \(k\) が区間 \([L, R]\) で見えるとは、\(L \le m < k\) なる \(m\) で \(H_m > H_k\) となるものが存在しないこと。つまり \(H_k \ge \max(H_L, H_{L+1}, \ldots, H_k)\) が成り立つことです。

見える山はチェーン構造を成す

位置 \(L\) から出発して見える山を順に追うと、現在の山以上の高さを持つ次の山に遷移していくことに気づきます。

例えば \(H = [3, 1, 4, 2, 5]\) で \(L=0\) から見ると： - 山0（高さ3）→ 次に高さ3以上の山は山2（高さ4） - 山2（高さ4）→ 次に高さ4以上の山は山4（高さ5）

見える山は {0, 2, 4} の3つです。

素朴なアプローチの問題点

各クエリで区間を左から走査すると、1クエリあたり最悪 \(O(N)\) かかり、全体で \(O(NQ)\) となりTLEします。

解決策：遷移関数 + ダブリング

各位置 \(i\) に対して「\(i\) より右で \(H[j] \ge H[i]\) を満たす最小の \(j\)」を \(\text{nxt}[i]\) と定義します。すると、見える山の列は \(L \to \text{nxt}[L] \to \text{nxt}[\text{nxt}[L]] \to \cdots\) と辿れます。

この遷移にダブリングを適用すれば、各クエリを \(O(\log N)\) で処理できます。

アルゴリズム

1. \(\text{nxt}[i]\) の計算（単調スタック）
   配列を左から走査し、スタックに未解決のインデックスを保持。\(H[i]\) がスタック頂の値以上なら、スタック頂の \(\text{nxt}\) を \(i\) に設定してpop。これにより全体 \(O(N)\) で計算できる。

2. ダブリングテーブルの構築
   \(\text{up}[k][i]\)：位置 \(i\) から \(2^k\) 回遷移した先の位置。

   • \(\text{up}[0][i] = \text{nxt}[i]\)
   • \(\text{up}[k][i] = \text{up}[k-1][\text{up}[k-1][i]]\)（到達可能な場合）

3. クエリ応答
   クエリ \((L, R)\) に対し、\(\text{cur} = L\)、\(\text{count} = 1\) から開始。\(k\) を大きい方から試し、\(\text{up}[k][\text{cur}] \le R\) なら \(2^k\) 回分ジャンプして count に加算。最終的な count が答え。

計算量

• 時間計算量: \(O(N \log N + Q \log N)\)（ダブリングテーブル構築に \(O(N \log N)\)、各クエリに \(O(\log N)\)）
• 空間計算量: \(O(N \log N)\)（ダブリングテーブル）

実装のポイント

• \(\text{nxt}\) の定義に注意：「\(H[j] \ge H[i]\)」（以上）で遷移する。等号を含めるのは、同じ高さの山も見えるため。

• 境界値：\(\text{nxt}[i] = N\)（配列外）をデフォルトとし、ダブリングでも \(N\) 以上なら遷移しないように処理する。

• 0-indexed への変換：入力は1-indexedなので、内部処理では0-indexedに変換している。

• LOG の設定：\(\lceil \log_2(N+1) \rceil + 1\) 程度で十分。ジャンプ回数は最大 \(N-1\) 回なので、\(\log_2 N\) レベルあればカバーできる。

  ソースコード

import sys
from math import log2, ceil

def main():
    input_data = sys.stdin.buffer.read().split()
    idx = 0
    N = int(input_data[idx]); idx += 1
    Q = int(input_data[idx]); idx += 1
    H = [int(input_data[idx + i]) for i in range(N)]
    idx += N
    
    queries = []
    for j in range(Q):
        L = int(input_data[idx]); idx += 1
        R = int(input_data[idx]); idx += 1
        queries.append((L - 1, R - 1, j))  # 0-indexed
    
    # For each query [L, R], count the number of "visible" mountains from the left.
    # A mountain k is visible if no mountain m with L <= m < k has H[m] > H[k].
    # Equivalently, mountain k is visible if H[k] >= max(H[L..k]).
    # This equals the number of "left-to-right maxima (non-strict)" in the subarray.
    
    # We use an offline approach with a stack-based structure.
    # 
    # Key idea: Process queries offline sorted by L (right to left).
    # We maintain a structure where for each position, we know whether it contributes
    # to visibility given a certain starting point.
    #
    # Alternative: Use a merge sort tree / persistent segment tree approach.
    #
    # Approach: Offline with sweepline from right to left on L.
    # For a fixed L, a position k in [L, R] is visible iff H[k] >= max(H[L..k]).
    # As L decreases, the set of visible positions changes.
    #
    # Let's use a different approach: sparse table for range max, and binary lifting
    # to count visible mountains.
    #
    # For each position i, define nxt[i] = the next position j > i such that H[j] >= H[i]
    # (using a monotone stack). Then from L, the visible mountains are L, nxt[L], nxt[nxt[L]], ...
    # until we exceed R. We can use binary lifting on the "nxt" function.
    
    # Compute nxt[i]: next index j > i with H[j] >= H[i]
    nxt = [N] * N  # default: beyond array
    stack = []
    for i in range(N):
        while stack and H[stack[-1]] <= H[i]:
            nxt[stack.pop()] = i
        stack.append(i)
    
    # Binary lifting on nxt
    LOG = max(1, ceil(log2(N + 1)) + 1)
    # up[k][i] = position reached after 2^k jumps from i
    # cnt is implicit: 2^k jumps means 2^k visible mountains after i
    
    up = [[0] * N for _ in range(LOG)]
    up[0] = nxt[:]
    
    for k in range(1, LOG):
        for i in range(N):
            if up[k-1][i] < N:
                up[k][i] = up[k-1][up[k-1][i]]
            else:
                up[k][i] = N
    
    # For query (L, R): start at L (which is always visible, count=1),
    # then jump via nxt. Count how many jumps land within [L, R].
    # The answer = 1 + number of jumps from L that land in <= R.
    
    ans = [0] * Q
    for L, R, j in queries:
        count = 1  # L itself is visible
        cur = L
        for k in range(LOG - 1, -1, -1):
            if up[k][cur] <= R:
                count += (1 << k)
                cur = up[k][cur]
        ans[j] = count
    
    sys.stdout.write('\n'.join(map(str, ans)) + '\n')

main()

---

この解説は claude4.6opus-thinking によって生成されました。