概要

この問題は、与えられた \(N\) 個の山の標高データに対して、指定された範囲 \([L, R]\) 内の最大値を求める「Range Maximum Query (RMQ)」と呼ばれるクエリに効率よく答える問題です。

考察

素朴な方法

各クエリに対して、範囲 \(L\) から \(R\) までをループで走査して最大値を探す方法が考えられます。 しかし、この方法では 1 つのクエリにつき最大で \(O(N)\) の時間がかかります。クエリの数は \(Q\) 個あるため、全体の計算量は \(O(N \times Q)\) となります。 本問題では \(N, Q \leq 10^5\) であるため、最悪の場合 \(10^{10}\) 回程度の計算が必要になり、制限時間内に終わりません。

効率的な解決策

標高データは途中で更新されない（静的なデータである）ため、Sparse Table（スパーステーブル） というデータ構造を利用することで、事前準備に \(O(N \log N)\)、各クエリへの回答を \(O(1)\) という非常に高速な時間で処理できるようになります。

アルゴリズム

Sparse Table（スパーステーブル）

Sparse Table は、「長さが 2 のべき乗（\(1, 2, 4, 8, \dots\)）」の区間における最大値をあらかじめ計算しておく手法です。

1. 構築 (Precomputation):

   • \(st[k][i]\) を「インデックス \(i\) から始まる長さ \(2^k\) の区間内の最大値」と定義します。
   • \(k=0\) のとき、長さは \(2^0=1\) なので、元の配列そのものです。
   • \(k > 0\) のとき、長さ \(2^k\) の区間は「長さ \(2^{k-1}\) の区間 2 つ」を合わせることで計算できます。 $\(st[k][i] = \max(st[k-1][i], st[k-1][i + 2^{k-1}])\)$
   • これを \(2^k \leq N\) となる範囲で繰り返します。

2. クエリ (Query):

   • 求めたい範囲 \([L, R]\) の長さを \(len = R - L + 1\) とします。
   • \(2^k \leq len\) を満たす最大の整数 \(k\) を選びます。
   • 範囲 \([L, R]\) は、「\(L\) から始まる長さ \(2^k\) の区間」と「\(R\) で終わる長さ \(2^k\) の区間」の 2 つで完全にカバーできます（これらは重なっても問題ありません）。
   • したがって、答えは \(\max(st[k][L], st[k][R - 2^k + 1])\) となります。

計算量

• 時間計算量: \(O(N \log N + Q)\)
  • 構築に \(O(N \log N)\)、クエリ回答に \(1\) 回あたり \(O(1)\) かかります。
• 空間計算量: \(O(N \log N)\)
  • 二次元配列（テーブル）を保持するために必要です。

実装のポイント

• 高速な入出力: Python で \(10^5\) 規模の入出力を扱う場合、input() の代わりに sys.stdin.read().split() を使ったり、最後に sys.stdout.write() でまとめて出力したりすると大幅に高速化されます。

• ビット演算: \(2^k\) の計算は 1 << k と書くことで高速に行えます。また、範囲の長さから \(k\) を求める際は、length.bit_length() - 1 を使うと効率的です。

• 0-indexed への変換: 問題文は \(1\) 番目から始まる \(1\)-indexed ですが、プログラム上では \(0\) 番目から始まる \(0\)-indexed として処理すると計算がスムーズです。

  ソースコード

import sys

def solve():
    # 高速な入力読み込み: すべての入力を一度に読み込み、空白で分割します
    try:
        input_data = sys.stdin.read().split()
    except EOFError:
        return
    
    if not input_data:
        return
    
    # N: 山の数, Q: 問い合わせの数
    N = int(input_data[0])
    Q = int(input_data[1])
    
    # A: 各山の標高 (1-indexedを0-indexedとして扱う)
    # Pythonのリスト内包表記は、大規模な数値リストの作成に高速です
    A = [int(x) for x in input_data[2:2+N]]
    
    # Sparse Table (スパーステーブル) の構築
    # Range Maximum Query (RMQ) を O(1) で行うためのデータ構造
    # st[k][i] は、範囲 [i, i + 2^k) における最大値を保持します
    k_max = N.bit_length()
    st = [None] * k_max
    st[0] = A
    
    for k in range(1, k_max):
        offset = 1 << (k-1)
        prev_st = st[k-1]
        # zipとリスト内包表記を組み合わせて高速に構築します
        # st[k] の長さは N - (1 << k) + 1 となります
        st[k] = [v1 if v1 > v2 else v2 for v1, v2 in zip(prev_st, prev_st[offset:])]
        
    # 問い合わせの処理
    results = []
    query_start = 2 + N
    for i in range(Q):
        # L, R を 0-indexed に変換
        L = int(input_data[query_start + 2*i]) - 1
        R = int(input_data[query_start + 2*i + 1]) - 1
        
        # 範囲の長さ
        length = R - L + 1
        
        # length を超えない最大の 2 のべき乗 2^k を求めます
        # bit_length() を使うことで高速に計算可能です
        k = length.bit_length() - 1
        
        # Sparse Table を用いた RMQ
        # 範囲 [L, R] をカバーする2つの重なり合う 2^k 長の範囲の最大値を比較します
        v1 = st[k][L]
        v2 = st[k][R - (1 << k) + 1]
        
        # 最大値を選択して結果リストに追加
        if v1 > v2:
            results.append(str(v1))
        else:
            results.append(str(v2))
            
    # 全ての結果を改行で連結して一度に出力します（高速化のため）
    sys.stdout.write('\n'.join(results) + '\n')

if __name__ == '__main__':
    solve()

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