概要

この問題は、複数の区間クエリに対し、各区間内の最大値を高速に求めるRange Maximum Query（RMQ）問題です。

考察

素朴な方法とその問題点

最も単純な方法は、各クエリごとに区間 \([L, R]\) 内の要素をすべて見て最大値を求めることです。
しかし、この方法では1つのクエリに最悪 \(O(N)\) かかり、全体で \(O(QN)\) の計算量が必要になります。
制約より、\(N, Q\) は最大で \(10^5\) なので、最悪ケースで \(10^{10}\) 回の計算となり、時間内に処理しきれません（TLE）。

効率的な方法

そこで、前処理を行い、各クエリに高速に応答できるようにします。
このような「前処理＋高速クエリ処理」の典型的な手法として、Sparse Table を用いた解法があります。
これは、任意の区間の最大値（や最小値など結合則が成り立つ演算）を \(O(1)\) で求めることができるデータ構造です。

アルゴリズム

Sparse Table とは？

Sparse Table は、静的配列（更新がない）に対する区間クエリを高速に処理するためのデータ構造です。
特に、区間の最大値・最小値・GCDなどの演算に有効です。

前処理（構築）

• 配列の長さを \(N\) とすると、Sparse Table は二次元配列 \(st[i][k]\) を持つ。
• \(st[i][k]\) は、区間 \([i, i + 2^k)\) の範囲の最大値を保持する。
• まず \(k=0\) のとき、\(st[i][0] = A[i]\) で初期化。
• その後、\(k = 1, 2, \ldots\) について以下のように更新： $\( st[i][k] = \max(st[i][k-1],\ st[i + 2^{k-1}][k-1]) \)$

クエリ処理

区間 \([L, R]\) の最大値を求めるには： - 区間の長さ \(len = R - L + 1\) - \(k = \lfloor \log_2(len) \rfloor\) - このとき、区間はちょうど2つの重なる区間（それぞれ長さ \(2^k\)）でカバーできる： $\( \max(st[L][k],\ st[R - 2^k + 1][k]) \)$

これにより、1回のクエリが \(O(1)\) で処理できます。

具体例

入力例：

N = 5, A = [3, 1, 4, 1, 5]
クエリ: L=2, R=4 （1-indexed）
→ 対象区間: [1, 4, 1] → 最大値は 4

Sparse Table 構築後、上記クエリに対して即座に答えが出ます。

計算量

• 時間計算量: \(O(N \log N + Q)\)
  • 前処理に \(O(N \log N)\)、クエリ処理に \(O(Q)\)
• 空間計算量: \(O(N \log N)\)
  • Sparse Table 用の二次元配列

実装のポイント

• 入力を高速に読み込むために sys.stdin.read を使用している。
• インデックスを0-basedに変換すること（問題では1-based）。
• Sparse Table の初期化時に、\(k\) のループと \(i\) のループの順序に注意。
• Python では、ビット長は .bit_length() で簡単に取得できる。

## ソースコード

```python
import sys
from math import gcd
from collections import defaultdict, deque, Counter
from itertools import combinations, permutations
from bisect import bisect_left, bisect_right
import heapq
import functools
from typing import List, Tuple
import math

# Sparse Table を用いた Range Maximum Query (RMQ) の実装
class SparseTable:
    def __init__(self, arr: List[int]):
        self.n = len(arr)
        self.logn = self.n.bit_length()
        # st[i][k] := 区間 [i, i + 2^k) の最大値
        self.st = [[0]*self.logn for _ in range(self.n)]
        
        # 初期化：k=0 の場合
        for i in range(self.n):
            self.st[i][0] = arr[i]
        
        # k >= 1 の場合
        k = 1
        while (1 << k) <= self.n:
            i = 0
            while i + (1 << k) <= self.n:
                self.st[i][k] = max(self.st[i][k-1], self.st[i + (1<<(k-1))][k-1])
                i += 1
            k += 1
    
    def query(self, l: int, r: int) -> int:
        # [l, r] の最大値を返す (0-indexed)
        length = r - l + 1
        k = length.bit_length() - 1
        return max(self.st[l][k], self.st[r - (1<<k) + 1][k])

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    
    idx = 0
    N = int(data[idx]); idx += 1
    Q = int(data[idx]); idx += 1
    
    A = [int(data[idx+i]) for i in range(N)]
    idx += N
    
    # Sparse Table の構築
    st = SparseTable(A)
    
    results = []
    for _ in range(Q):
        L = int(data[idx]) - 1; idx += 1  # 0-indexed へ変換
        R = int(data[idx]) - 1; idx += 1
        res = st.query(L, R)
        results.append(str(res))
    
    print('\n'.join(results))

if __name__ == "__main__":
    main()

---

この解説は qwen3-coder-480b によって生成されました。