概要

各クエリで区間 \([L, R]\) の「最大値 − 最小値」を求める問題です。多数の区間問い合わせを高速に処理するため、セグメント木で区間最小値・最大値を管理します。

考察

各問い合わせごとに \(A_L, A_{L+1}, \dots, A_R\) を走査して最大・最小を求めると、1 回あたり \(O(R-L+1)\) かかります。最悪の場合、各クエリが長い区間になるため

• 素朴解法: \(O(NQ)\)（最大で \(10^5 \times 10^5 = 10^{10}\)）となり、時間制限に間に合いません。

ここで重要なのは、求めたい量が

• 区間の最小値
• 区間の最大値
  

という「区間集約（区間の情報をまとめる）」であり、これらは結合（左右の区間の結果から全体の結果が作れる）できることです。

例えば区間を左右に分けたとき、

• 全体の最小値 = \(\min(\text{左の最小値}, \text{右の最小値})\)
• 全体の最大値 = \(\max(\text{左の最大値}, \text{右の最大値})\)

この性質を利用すると、前処理をして各クエリを \(O(\log N)\) で処理できます。

アルゴリズム

セグメント木（Segment Tree）を使って、各区間の最小値と最大値を同時に管理します。

1. 構築（前処理）

1. 要素数 \(N\) 以上の最小の \(2\) 冪を size とします（葉を揃えるため）。
2. セグメント木の葉（配列の後半）に \(A_i\) を入れます。
3. 下から上へ、各ノードに以下を計算して格納します。
   • seg_min[i] = min(seg_min[2i], seg_min[2i+1])
   • seg_max[i] = max(seg_max[2i], seg_max[2i+1])

これで任意区間の最小・最大を対数時間で求められます。

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

実装では扱いやすいように 半開区間 \([l, r)\) に変換します（\(l=L-1\), \(r=R\)）。 セグメント木の典型的な走査で、区間を覆うノードだけを拾っていきます。

• mn（最小値）を \(+\infty\) で初期化
• mx（最大値）を \(-\infty\) で初期化
• 区間に対応するノードを集めながら mn, mx を更新
• 最後に答えは mx - mn

この方法により、1 クエリあたり木の高さ分（\(O(\log N)\)）しか見ません。

計算量

• 時間計算量: 構築 \(O(N)\)、各クエリ \(O(\log N)\)、合計 \(O(N + Q\log N)\)
• 空間計算量: \(O(N)\)（最小値用・最大値用にセグ木配列を持つ）

実装のポイント

• 半開区間 \([l, r)\) にすると、セグメント木の反復クエリが書きやすくバグが減ります（コードでも r = next(it) を「exclusive」として扱っています）。
• 最小・最大を別々の配列（seg_min, seg_max）で持つと実装が単純です。
• 入力が大きいので、sys.stdin.buffer.read() で一括読み込みして高速化しています。
• 初期値として INF = 10**18、-INF を使い、\(A_i\) の範囲（\(\pm 10^9\)）より十分大きくしています。

ソースコード

import sys

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    it = iter(data)
    N = next(it)
    Q = next(it)
    A = [next(it) for _ in range(N)]

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

    INF = 10**18
    seg_min = [INF] * (2 * size)
    seg_max = [-INF] * (2 * size)

    for i, v in enumerate(A):
        seg_min[size + i] = v
        seg_max[size + i] = v

    for i in range(size - 1, 0, -1):
        seg_min[i] = seg_min[i << 1] if seg_min[i << 1] < seg_min[i << 1 | 1] else seg_min[i << 1 | 1]
        seg_max[i] = seg_max[i << 1] if seg_max[i << 1] > seg_max[i << 1 | 1] else seg_max[i << 1 | 1]

    out = []
    for _ in range(Q):
        l = next(it) - 1
        r = next(it)  # exclusive
        l += size
        r += size
        mn = INF
        mx = -INF
        while l < r:
            if l & 1:
                vmin = seg_min[l]
                vmax = seg_max[l]
                if vmin < mn: mn = vmin
                if vmax > mx: mx = vmax
                l += 1
            if r & 1:
                r -= 1
                vmin = seg_min[r]
                vmax = seg_max[r]
                if vmin < mn: mn = vmin
                if vmax > mx: mx = vmax
            l >>= 1
            r >>= 1
        out.append(str(mx - mn))

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

if __name__ == "__main__":
    main()

---

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