Overview

This problem asks us to find “maximum − minimum” over the interval \([L, R]\) for each query. To efficiently handle a large number of range queries, we use a segment tree to manage range minimums and maximums.

Analysis

If we scan \(A_L, A_{L+1}, \dots, A_R\) for each query to find the maximum and minimum, it takes \(O(R-L+1)\) per query. In the worst case, each query covers a long interval, so:

• Naive approach: \(O(NQ)\) (up to \(10^5 \times 10^5 = 10^{10}\)), which will not fit within the time limit.

The key observation is that the quantities we want to compute are: - Range minimum - Range maximum

These are “range aggregations” (combining information over a range), and they are associative (the result for the whole range can be computed from the results of its left and right halves).

For example, when splitting a range into left and right halves: - Overall minimum = \(\min(\text{left minimum}, \text{right minimum})\) - Overall maximum = \(\max(\text{left maximum}, \text{right maximum})\)

Using this property, we can preprocess the data and answer each query in \(O(\log N)\).

Algorithm

We use a Segment Tree to simultaneously manage the minimum and maximum values for each range.

1. Construction (Preprocessing)

1. Let size be the smallest power of \(2\) that is at least \(N\) (to align the leaves).
2. Place \(A_i\) in the leaves (the second half of the array) of the segment tree.
3. From bottom to top, compute and store the following for each node:
   • seg_min[i] = min(seg_min[2i], seg_min[2i+1])
   • seg_max[i] = max(seg_max[2i], seg_max[2i+1])

This allows us to answer range minimum and maximum queries in logarithmic time.

2. Query Processing (Interval \([L, R]\))

For ease of implementation, we convert to a half-open interval \([l, r)\) (\(l=L-1\), \(r=R\)). We use the standard segment tree traversal, collecting only the nodes that cover the interval.

• Initialize mn (minimum) to \(+\infty\)
• Initialize mx (maximum) to \(-\infty\)
• Gather the nodes corresponding to the interval while updating mn and mx
• The final answer is mx - mn

With this approach, each query visits only as many nodes as the height of the tree (\(O(\log N)\)).

Complexity

• Time complexity: Construction \(O(N)\), each query \(O(\log N)\), total \(O(N + Q\log N)\)
• Space complexity: \(O(N)\) (segment tree arrays for minimum and maximum)

Implementation Notes

• Using half-open intervals \([l, r)\) makes the iterative segment tree query easier to write and less error-prone (in the code, r = next(it) is treated as “exclusive”).

• Storing minimums and maximums in separate arrays (seg_min, seg_max) keeps the implementation simple.

• Since the input is large, we use sys.stdin.buffer.read() to read all input at once for faster I/O.

• We use INF = 10**18 and -INF as initial values, which are sufficiently larger than the range of \(A_i\) (\(\pm 10^9\)).

  Source Code

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

---

This editorial was generated by gpt-5.2-high.