Overview

This problem is a Range Maximum Query (RMQ) problem, where for multiple interval queries, we need to efficiently find the maximum value within each interval.

Analysis

Naive Approach and Its Issues

The simplest method is to scan all elements in the interval \([L, R]\) for each query and find the maximum value.
However, this method takes \(O(N)\) in the worst case for a single query, resulting in an overall time complexity of \(O(QN)\).
Given the constraints, \(N, Q\) can be up to \(10^5\), so in the worst case this requires \(10^{10}\) operations, which cannot be processed within the time limit (TLE).

Efficient Approach

Instead, we perform preprocessing so that each query can be answered quickly.
A typical technique for this “preprocessing + fast query processing” pattern is a solution using a Sparse Table.
This is a data structure that can compute the maximum (or minimum, or any operation satisfying the overlap property) of any interval in \(O(1)\).

Algorithm

What is a Sparse Table?

A Sparse Table is a data structure for efficiently processing interval queries on a static array (no updates).
It is particularly effective for operations such as interval maximum, minimum, and GCD.

Preprocessing (Construction)

• Let the length of the array be \(N\). The Sparse Table has a two-dimensional array \(st[i][k]\).
• \(st[i][k]\) stores the maximum value in the range \([i, i + 2^k)\).
• First, for \(k=0\), initialize \(st[i][0] = A[i]\).
• Then, for \(k = 1, 2, \ldots\), update as follows: $\( st[i][k] = \max(st[i][k-1],\ st[i + 2^{k-1}][k-1]) \)$

Query Processing

To find the maximum value in the interval \([L, R]\): - Length of the interval: \(len = R - L + 1\) - \(k = \lfloor \log_2(len) \rfloor\) - The interval can be covered by exactly two overlapping sub-intervals (each of length \(2^k\)): $\( \max(st[L][k],\ st[R - 2^k + 1][k]) \)$

This allows each query to be processed in \(O(1)\).

Concrete Example

Sample input:

N = 5, A = [3, 1, 4, 1, 5]
Query: L=2, R=4 (1-indexed)
→ Target interval: [1, 4, 1] → Maximum value is 4

After constructing the Sparse Table, the answer to the above query can be obtained immediately.

Complexity

• Time complexity: \(O(N \log N + Q)\)
  • \(O(N \log N)\) for preprocessing, \(O(Q)\) for query processing
• Space complexity: \(O(N \log N)\)
  • For the two-dimensional Sparse Table array

Implementation Notes

• sys.stdin.read is used for fast input reading.

• Convert indices to 0-based (the problem uses 1-based indexing).

• Pay attention to the order of the \(k\) loop and the \(i\) loop when initializing the Sparse Table.

• In Python, the bit length can be easily obtained using .bit_length().

  Source Code

import sys
from math import gcd
from collections import defaultdict, deque, Counter
from itertools import combinations, permutations
from bisect import bisect_left, bisect_right
import heapq
import functools
from typing import List, Tuple
import math

# Sparse Table を用いた Range Maximum Query (RMQ) の実装
class SparseTable:
    def __init__(self, arr: List[int]):
        self.n = len(arr)
        self.logn = self.n.bit_length()
        # st[i][k] := 区間 [i, i + 2^k) の最大値
        self.st = [[0]*self.logn for _ in range(self.n)]
        
        # 初期化：k=0 の場合
        for i in range(self.n):
            self.st[i][0] = arr[i]
        
        # k >= 1 の場合
        k = 1
        while (1 << k) <= self.n:
            i = 0
            while i + (1 << k) <= self.n:
                self.st[i][k] = max(self.st[i][k-1], self.st[i + (1<<(k-1))][k-1])
                i += 1
            k += 1
    
    def query(self, l: int, r: int) -> int:
        # [l, r] の最大値を返す (0-indexed)
        length = r - l + 1
        k = length.bit_length() - 1
        return max(self.st[l][k], self.st[r - (1<<k) + 1][k])

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    
    idx = 0
    N = int(data[idx]); idx += 1
    Q = int(data[idx]); idx += 1
    
    A = [int(data[idx+i]) for i in range(N)]
    idx += N
    
    # Sparse Table の構築
    st = SparseTable(A)
    
    results = []
    for _ in range(Q):
        L = int(data[idx]) - 1; idx += 1  # 0-indexed へ変換
        R = int(data[idx]) - 1; idx += 1
        res = st.query(L, R)
        results.append(str(res))
    
    print('\n'.join(results))

if __name__ == "__main__":
    main()

---

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