概要

この問題では、複数の区間クエリに対して、各区間内の要素の最大値と最小値の差を高速に求める必要があります。

考察

素朴な方法として、各クエリごとに区間 \([L, R]\) を走査して最大値と最小値を求めることを考えます。しかし、この方法の時間計算量は各クエリで最悪 \(O(N)\) かかり、全体では \(O(QN)\) となり、制約 \(N, Q \leq 10^5\) のもとでは間に合いません（最大で \(10^{10}\) 回の計算が必要）。

そこで、前処理を行い、各クエリに高速に応答できるようにします。区間の最大値・最小値を効率的に取得するには、「セグメント木（Segment Tree）」というデータ構造が非常に有効です。セグメント木を使うことで、区間に対するクエリを \(O(\log N)\) で処理できます。

アルゴリズム

セグメント木による解法

1. 前処理:

   • 入力配列 \(A\) に基づいて、区間最大値と区間最小値を保持するセグメント木を構築します。
   • セグメント木は完全二分木の形をしており、葉ノードには元の配列の値が格納され、内部ノードには子ノードの最大値（または最小値）が格納されます。

2. クエリ処理:

   • 各クエリ \([L, R]\) に対して、セグメント木上で区間 \([L, R]\) の最大値と最小値を取得し、その差を答えとして出力します。
   • 最大値・最小値取得ともに、セグメント木上での区間クエリにより \(O(\log N)\) で求められます。

具体例

例えば、気温データが \(A = [10, 5, 20, 15]\) で、クエリが \([1, 4]\) の場合：

• 区間 \([1, 4]\) の最大値は 20、最小値は 5
• 差は \(20 - 5 = 15\)

計算量

• 時間計算量: \(O((N + Q) \log N)\)
  • セグメント木構築: \(O(N)\)
  • 各クエリ処理: \(O(\log N)\)、\(Q\) 回のクエリで \(O(Q \log N)\)
• 空間計算量: \(O(N)\)
  • セグメント木のサイズは \(2N\) 程度

実装のポイント

• セグメント木のインデックスは通常、配列のサイズを \(n\) として \(1\) から \(2n-1\) の範囲で扱います。
• クエリの区間指定は半開区間 \([l, r)\) で統一するのが一般的ですが、このコードでは閉区間 \([L, R]\) を使用しているため、query_max(L, R+1) のように渡しています。
• 最大値用と最小値用の2つの木を持つことで、コードがシンプルになります。

ソースコード

import sys
from math import gcd
from collections import defaultdict, deque, Counter, OrderedDict
from itertools import permutations, combinations, accumulate
from bisect import bisect_left, bisect_right
from heapq import heapify, heappush, heappop

input = sys.stdin.readline

def main():
    N, Q = map(int, input().split())
    A = list(map(int, input().split()))
    
    # セグメント木で区間最大値・最小値を管理
    class SegmentTree:
        def __init__(self, data):
            self.n = len(data)
            self.max_tree = [0] * (2 * self.n)
            self.min_tree = [0] * (2 * self.n)
            # 葉ノードの初期化
            for i in range(self.n):
                self.max_tree[self.n + i] = data[i]
                self.min_tree[self.n + i] = data[i]
            # 内部ノードの構築
            for i in range(self.n - 1, 0, -1):
                self.max_tree[i] = max(self.max_tree[2*i], self.max_tree[2*i+1])
                self.min_tree[i] = min(self.min_tree[2*i], self.min_tree[2*i+1])
        
        def query_max(self, l, r):
            res = -float('inf')
            l += self.n
            r += self.n
            while l < r:
                if l & 1:
                    res = max(res, self.max_tree[l])
                    l += 1
                if r & 1:
                    r -= 1
                    res = max(res, self.max_tree[r])
                l >>= 1
                r >>= 1
            return res
        
        def query_min(self, l, r):
            res = float('inf')
            l += self.n
            r += self.n
            while l < r:
                if l & 1:
                    res = min(res, self.min_tree[l])
                    l += 1
                if r & 1:
                    r -= 1
                    res = min(res, self.min_tree[r])
                l >>= 1
                r >>= 1
            return res
    
    seg = SegmentTree(A)
    
    results = []
    for _ in range(Q):
        L, R = map(int, input().split())
        L -= 1
        R -= 1
        max_val = seg.query_max(L, R+1)
        min_val = seg.query_min(L, R+1)
        results.append(max_val - min_val)
    
    print('\n'.join(map(str, results)))

if __name__ == "__main__":
    main()

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