Overview

In this problem, we need to efficiently compute the difference between the maximum and minimum values within a range for multiple range queries.

Analysis

A naive approach would be to scan the interval \([L, R]\) for each query to find the maximum and minimum values. However, the time complexity of this method is \(O(N)\) per query in the worst case, resulting in \(O(QN)\) overall, which is too slow under the constraints \(N, Q \leq 10^5\) (requiring up to \(10^{10}\) computations).

Therefore, we perform preprocessing to enable fast responses to each query. To efficiently retrieve range maximum and minimum values, a data structure called a “Segment Tree” is extremely effective. By using a segment tree, we can process range queries in \(O(\log N)\).

Algorithm

Segment Tree Solution

1. Preprocessing:

   • Build segment trees that maintain range maximum and range minimum values based on the input array \(A\).
   • A segment tree has the shape of a complete binary tree, where leaf nodes store the original array values, and internal nodes store the maximum (or minimum) of their child nodes.

2. Query Processing:

   • For each query \([L, R]\), retrieve the maximum and minimum values of the interval \([L, R]\) on the segment tree, and output their difference as the answer.
   • Both maximum and minimum retrieval can be computed in \(O(\log N)\) using range queries on the segment tree.

Concrete Example

For example, if the temperature data is \(A = [10, 5, 20, 15]\) and the query is \([1, 4]\): - The maximum of the interval \([1, 4]\) is 20, and the minimum is 5 - The difference is \(20 - 5 = 15\)

Complexity

• Time complexity: \(O((N + Q) \log N)\)
  • Segment tree construction: \(O(N)\)
  • Each query processing: \(O(\log N)\), for \(Q\) queries: \(O(Q \log N)\)
• Space complexity: \(O(N)\)
  • The size of the segment tree is approximately \(2N\)

Implementation Notes

• Segment tree indices are typically handled in the range from \(1\) to \(2n-1\), where \(n\) is the array size.

• It is common to use half-open intervals \([l, r)\) for range specification in queries, but since this code uses closed intervals \([L, R]\), we pass them as query_max(L, R+1).

• Maintaining two separate trees, one for maximum and one for minimum, keeps the code simple.

  Source Code

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()

This editorial was generated by qwen3-coder-480b.