概要

配列 \(A\) に対して、各クエリ \((L,R)\) の区間最大値 \(\max(A_L,\dots,A_R)\) を高速に答える問題です。多数の区間最大クエリを処理するため、セグメント木を使います。

考察

各問い合わせごとに、区間 \([L,R]\) を先頭から走査して最大値を求めると、1クエリあたり \(O(R-L+1)\) かかります。最悪の場合は \(O(N)\) となり、全体では \(O(NQ)\) です。

制約は \(N,Q \le 10^5\) なので、例えば \(N=Q=10^5\) だと \(10^{10}\) 回程度の操作になり、これは現実的な時間では間に合いません（TLE）。

そこで、「配列を前処理して、各区間の最大値を対数時間で答える」必要があります。区間最大のような演算（結合則が成り立つ：\(\max(\max(a,b),c)=\max(a,\max(b,c))\)）は、セグメント木で扱えます。

アルゴリズム

セグメント木（区間最大）

セグメント木は、配列を区間に分割して管理する完全二分木です。

• 葉：各要素 \(A_i\)
• 内部ノード：そのノードが担当する区間の最大値

1. 構築（前処理）

要素数 \(N\) 以上の最小の \(2\) の冪を size とし、配列を木の葉（seg[size + i]）に置きます。残りの葉は「最大値に影響しない十分小さい値（\(-\infty\)）」で埋めます。

その後、下から順に - seg[i] = max(seg[2*i], seg[2*i+1]) として内部ノードを作れば、根 seg[1] まで最大値が埋まります。

2. クエリ処理（区間 \([L,R]\) の最大）

クエリ \((L,R)\) は 1-indexed で与えられるので、0-indexに直してから葉の位置へ移します： - l = (L-1) + size - r = (R-1) + size

そして次の要領で区間をカバーする最小限のノードだけを集めます：

• l が右子（奇数）なら、そのノードは区間に完全に含まれるので答えに反映して l++
• r が左子（偶数）なら、そのノードも区間に完全に含まれるので答えに反映して r--
• その後 l//=2, r//=2 で親へ上がる

これを l > r になるまで繰り返すと、ちょうど区間 \([L,R]\) を覆うノード集合の最大値が求まります。各ステップで高さ分だけ上がるため、計算量は \(O(\log N)\) です。

（例）\([L,R]\) を「2の冪長の区間」に分解して、その最大を取るイメージです。セグメント木はこの分解を自動でやってくれます。

計算量

• 時間計算量: 構築 \(O(N)\)、各クエリ \(O(\log N)\)、合計 \(O(N + Q\log N)\)
• 空間計算量: セグメント木配列に \(O(\text{size}) = O(N)\)

実装のポイント

• 1-indexed入力に注意：クエリの \(L,R\) は 1-indexed なので、L-1, R-1 に直してから処理します。

• size は \(2\) の冪にする：セグメント木を配列で管理するとき、size を \(2\) の冪にすると親子関係（i の子が 2i,2i+1）が簡単になります。

• 初期値（単位元）：最大値用なので、初期値は十分小さい値（コードでは -10**18）を使います。

• 高速入出力：\(Q\) が大きいので、sys.stdin.readline と、出力を配列に貯めて最後にまとめて出す方法が有効です。

  ソースコード

import sys

def main():
    input = sys.stdin.readline
    N, Q = map(int, input().split())
    A = list(map(int, input().split()))

    size = 1
    while size < N:
        size <<= 1

    seg = [-10**18] * (2 * size)
    for i, v in enumerate(A):
        seg[size + i] = v
    for i in range(size - 1, 0, -1):
        left = seg[i * 2]
        right = seg[i * 2 + 1]
        seg[i] = left if left > right else right

    out = []
    for _ in range(Q):
        l, r = map(int, input().split())
        l = l - 1 + size
        r = r - 1 + size
        res = -10**18
        while l <= r:
            if l & 1:
                if seg[l] > res:
                    res = seg[l]
                l += 1
            if not (r & 1):
                if seg[r] > res:
                    res = seg[r]
                r -= 1
            l >>= 1
            r >>= 1
        out.append(str(res))

    sys.stdout.write("\n".join(out))

if __name__ == "__main__":
    main()

---

この解説は gpt-5.2-high によって生成されました。