概要

山脈の指定区間における標高の最大値を求める「Range Maximum Query (RMQ)」を、複数のクエリに対して高速に処理する問題です。

考察

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

各クエリに対して、指定された区間 \([L, R]\) を単純にループで走査して最大値を求める方法が最も直感的です。

for i in range(L-1, R):
    ans = max(ans, A[i])

しかし、この方法では1回のクエリに \(O(N)\) かかるため、全体で \(O(NQ)\) となります。\(N, Q\) がともに最大 \(10^5\) の場合、\(10^{10}\) 回の操作が必要となり、制限時間内に間に合いません（TLE）。

解決の方針

クエリが大量にある場合、前処理を行ってクエリを高速に処理するアプローチが有効です。区間の最大値クエリには「Sparse Table（スパーステーブル）」というデータ構造が適しています。

アルゴリズム

Sparse Table とは

Sparse Table は、長さが2のべき乗である区間の情報をあらかじめ計算しておくテクニックです。

• sparse_table[k][i] = 位置 \(i\) から始まる長さ \(2^k\) の区間の最大値
  • つまり、\(\max(A[i], A[i+1], \ldots, A[i+2^k-1])\)

構築方法

1. 基底（k=0）: 長さ \(2^0 = 1\) の区間は要素そのもの

   • sparse_table[0][i] = A[i]

2. 漸化式（k≥1）: 長さ \(2^k\) の区間を、2つの長さ \(2^{k-1}\) の区間に分割

   • sparse_table[k][i] = max(sparse_table[k-1][i], sparse_table[k-1][i + 2^(k-1)])

クエリの応答

区間 \([l, r]\)（0-indexed）の最大値を求めるには：

1. 区間の長さ \(len = r - l + 1\) に対して、\(2^k \leq len\) となる最大の \(k\) を求める
2. 区間を 2つの重なり合う区間 で覆う：
   • 左から: \([l, l + 2^k - 1]\)
   • 右から: \([r - 2^k + 1, r]\)
3. 両区間の最大値の大きい方が答え

具体例: 区間 \([1, 5]\)（長さ5）の場合 - \(k = 2\)（\(2^2 = 4 \leq 5\)） - 区間 \([1, 4]\) と \([2, 5]\) の最大値を比較

計算量

• 前処理（Sparse Table 構築）

  • 時間計算量: \(O(N \log N)\)
  • 空間計算量: \(O(N \log N)\)

• 各クエリの応答

  • 時間計算量: \(O(1)\)

• 全体

  • 時間計算量: \(O(N \log N + Q)\)
  • 空間計算量: \(O(N \log N)\)

実装のポイント

1. 1-indexed から 0-indexed への変換: 問題文では山の番号が1から始まるため、配列アクセス時に L-1, R-1 と変換する

2. log テーブルの前計算: クエリごとに \(\log_2\) を計算すると遅いため、あらかじめテーブルを作成

   log_table[i] = log_table[i // 2] + 1
   

3. 出力の高速化: 結果をリストに溜めて最後に一括出力することで、I/O のオーバーヘッドを削減

4. max が重複計算を許容する性質の利用: Sparse Table は min/max/gcd など「同じ要素を複数回計算しても結果が変わらない」演算に適用可能

   ソースコード

import sys
from math import log2, ceil

def main():
    input = sys.stdin.readline
    
    N, Q = map(int, input().split())
    A = list(map(int, input().split()))
    
    # Sparse Table for Range Maximum Query
    # sparse_table[k][i] = max of A[i:i+2^k]
    
    if N == 0:
        for _ in range(Q):
            print(0)
        return
    
    LOG = max(1, ceil(log2(N + 1)))
    
    # Initialize sparse table
    sparse_table = [[0] * N for _ in range(LOG + 1)]
    
    # Base case: intervals of length 1
    for i in range(N):
        sparse_table[0][i] = A[i]
    
    # Build sparse table
    for k in range(1, LOG + 1):
        length = 1 << k
        half = 1 << (k - 1)
        for i in range(N - length + 1):
            sparse_table[k][i] = max(sparse_table[k-1][i], sparse_table[k-1][i + half])
    
    # Precompute log2 values
    log_table = [0] * (N + 1)
    for i in range(2, N + 1):
        log_table[i] = log_table[i // 2] + 1
    
    # Answer queries
    results = []
    for _ in range(Q):
        L, R = map(int, input().split())
        # Convert to 0-indexed
        l = L - 1
        r = R - 1
        length = r - l + 1
        k = log_table[length]
        # max of [l, l + 2^k) and [r - 2^k + 1, r + 1)
        ans = max(sparse_table[k][l], sparse_table[k][r - (1 << k) + 1])
        results.append(ans)
    
    print('\n'.join(map(str, results)))

if __name__ == "__main__":
    main()

---

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