Overview

Given temperature data for \(N\) days, we need to answer \(Q\) queries, each asking for “the difference between the maximum and minimum values in a specified period \([L, R]\).”

Analysis

The simplest approach is to scan from day \(L\) to day \(R\) for each query to find the maximum and minimum values. However, this method takes up to \(O(N)\) time per query. Since there are \(Q\) queries, the overall time complexity becomes \(O(NQ)\). Given the constraints of this problem, \(N, Q \leq 10^5\), we get \(NQ \approx 10^{10}\), which is far too slow for a typical time limit (around 2 seconds).

Therefore, we need a technique that can efficiently process range queries on a static array. Since there are no data updates in this problem, by using a data structure called a Sparse Table, we can answer each query in \(O(1)\).

Algorithm

Sparse Table

A Sparse Table is a technique that precomputes results for intervals whose lengths are powers of 2 (1, 2, 4, 8…).

1. Preprocessing:

   • st_max[k][i]: the maximum value in the interval of length \(2^k\) starting at position \(i\)
   • st_min[k][i]: the minimum value in the interval of length \(2^k\) starting at position \(i\) These are constructed in \(O(N \log N)\) time. For example, st_max[k][i] can be computed by simply comparing two values: st_max[k-1][i] and st_max[k-1][i + 2^{k-1}].

2. Query Processing: Any interval \([L, R]\) of length \(len\) can be completely covered by two overlapping intervals using “the largest \(2^k\) such that \(2^k \leq len\)”:

   • Interval 1: length \(2^k\) starting from \(L\)
   • Interval 2: length \(2^k\) going back (to the left) from \(R\)

   For operations with idempotency such as maximum and minimum, the result does not change even if intervals overlap. Therefore, by simply comparing the values of these two intervals, we can obtain the answer for the entire original interval in \(O(1)\).

Complexity

• Time Complexity: \(O(N \log N + Q)\)
  • Preprocessing (table construction) takes \(O(N \log N)\), and answering each query takes \(O(1)\).
• Space Complexity: \(O(N \log N)\)
  • This is because we maintain a table of height \(\log N\) for an array of length \(N\).

Implementation Notes

• Fast I/O: Since \(N\) and \(Q\) are large, in Python it is important to speed up input/output using sys.stdin.read().split() and sys.stdout.write.

• Precomputation of Logarithms: Instead of computing \(\log\) for each query, we precompute them into an array to achieve constant-factor speedup.

• Optimization in Python: By leveraging the map function and slicing, such as st_min[k] = list(map(min, prev_min, prev_min[offset:])), we avoid Python loops and utilize internal C-level processing to build the table efficiently.

  Source Code

import sys

def solve():
    # Read all input tokens at once for speed
    try:
        input_data = sys.stdin.read().split()
    except EOFError:
        return
    
    if not input_data:
        return
    
    N = int(input_data[0])
    Q = int(input_data[1])
    
    # A is the list of temperatures
    A = list(map(int, input_data[2:N+2]))
    
    # Precompute logs to find the power of 2 for any range length
    logs = [0] * (N + 1)
    for i in range(2, N + 1):
        logs[i] = logs[i >> 1] + 1
        
    k_max = logs[N] + 1
    st_min = [None] * k_max
    st_max = [None] * k_max
    st_min[0] = A
    st_max[0] = A
    
    # Build Sparse Table for O(1) range minimum and maximum queries
    for k in range(1, k_max):
        offset = 1 << (k - 1)
        prev_min = st_min[k - 1]
        prev_max = st_max[k - 1]
        # Use map for efficient element-wise min/max with C-level speed
        st_min[k] = list(map(min, prev_min, prev_min[offset:]))
        st_max[k] = list(map(max, prev_max, prev_max[offset:]))
        
    results = []
    # ptr points to the start of query parameters L, R
    ptr = N + 2
    for _ in range(Q):
        L = int(input_data[ptr]) - 1
        R = int(input_data[ptr + 1]) - 1
        ptr += 2
        
        length = R - L + 1
        k = logs[length]
        
        # Query for range maximum
        st_max_k = st_max[k]
        v1_max = st_max_k[L]
        v2_max = st_max_k[R - (1 << k) + 1]
        mx = v1_max if v1_max > v2_max else v2_max
        
        # Query for range minimum
        st_min_k = st_min[k]
        v1_min = st_min_k[L]
        v2_min = st_min_k[R - (1 << k) + 1]
        mn = v1_min if v1_min < v2_min else v2_min
        
        # Difference between max and min
        results.append(str(mx - mn))
        
    # Output all results at once
    sys.stdout.write('\n'.join(results) + '\n')

if __name__ == '__main__':
    solve()

This editorial was generated by gemini-3-flash-preview.