Overview

This problem requires efficiently answering queries known as “Range Maximum Query (RMQ),” which find the maximum value within a specified range \([L, R]\) over the elevation data of \(N\) given mountains.

Analysis

Naive Approach

For each query, one could scan from \(L\) to \(R\) in a loop to find the maximum value. However, this approach takes up to \(O(N)\) time per query. Since there are \(Q\) queries, the overall time complexity becomes \(O(N \times Q)\). In this problem, \(N, Q \leq 10^5\), so in the worst case, approximately \(10^{10}\) operations would be needed, which would not finish within the time limit.

Efficient Solution

Since the elevation data is never updated (it is static data), by using a data structure called a Sparse Table, we can achieve \(O(N \log N)\) preprocessing time and \(O(1)\) time per query, enabling extremely fast processing.

Algorithm

Sparse Table

A Sparse Table is a technique that precomputes the maximum value over intervals whose lengths are powers of 2 (\(1, 2, 4, 8, \dots\)).

1. Construction (Precomputation):

   • Define \(st[k][i]\) as “the maximum value in the interval of length \(2^k\) starting from index \(i\).”
   • When \(k=0\), the length is \(2^0=1\), so it is simply the original array itself.
   • When \(k > 0\), an interval of length \(2^k\) can be computed by combining “two intervals of length \(2^{k-1}\)”: $\(st[k][i] = \max(st[k-1][i], st[k-1][i + 2^{k-1}])\)$
   • This is repeated for all \(k\) such that \(2^k \leq N\).

2. Query:

   • Let the length of the desired range \([L, R]\) be \(len = R - L + 1\).
   • Choose the largest integer \(k\) satisfying \(2^k \leq len\).
   • The range \([L, R]\) can be fully covered by two intervals: “the interval of length \(2^k\) starting from \(L\)” and “the interval of length \(2^k\) ending at \(R\)” (overlap between them is not a problem).
   • Therefore, the answer is \(\max(st[k][L], st[k][R - 2^k + 1])\).

Complexity

• Time Complexity: \(O(N \log N + Q)\)
  • Construction takes \(O(N \log N)\), and each query answer takes \(O(1)\).
• Space Complexity: \(O(N \log N)\)
  • Required to store the two-dimensional array (table).

Implementation Tips

• Fast I/O: When handling I/O on the order of \(10^5\) in Python, using sys.stdin.read().split() instead of input(), and outputting all at once with sys.stdout.write() at the end, can significantly speed things up.

• Bit Operations: Computing \(2^k\) can be done efficiently by writing 1 << k. Also, when determining \(k\) from the length of the range, using length.bit_length() - 1 is efficient.

• Converting to 0-indexed: The problem statement uses 1-indexed numbering starting from the 1st element, but processing with 0-indexed numbering starting from the 0th element in the program makes calculations smoother.

  Source Code

import sys

def solve():
    # 高速な入力読み込み: すべての入力を一度に読み込み、空白で分割します
    try:
        input_data = sys.stdin.read().split()
    except EOFError:
        return
    
    if not input_data:
        return
    
    # N: 山の数, Q: 問い合わせの数
    N = int(input_data[0])
    Q = int(input_data[1])
    
    # A: 各山の標高 (1-indexedを0-indexedとして扱う)
    # Pythonのリスト内包表記は、大規模な数値リストの作成に高速です
    A = [int(x) for x in input_data[2:2+N]]
    
    # Sparse Table (スパーステーブル) の構築
    # Range Maximum Query (RMQ) を O(1) で行うためのデータ構造
    # st[k][i] は、範囲 [i, i + 2^k) における最大値を保持します
    k_max = N.bit_length()
    st = [None] * k_max
    st[0] = A
    
    for k in range(1, k_max):
        offset = 1 << (k-1)
        prev_st = st[k-1]
        # zipとリスト内包表記を組み合わせて高速に構築します
        # st[k] の長さは N - (1 << k) + 1 となります
        st[k] = [v1 if v1 > v2 else v2 for v1, v2 in zip(prev_st, prev_st[offset:])]
        
    # 問い合わせの処理
    results = []
    query_start = 2 + N
    for i in range(Q):
        # L, R を 0-indexed に変換
        L = int(input_data[query_start + 2*i]) - 1
        R = int(input_data[query_start + 2*i + 1]) - 1
        
        # 範囲の長さ
        length = R - L + 1
        
        # length を超えない最大の 2 のべき乗 2^k を求めます
        # bit_length() を使うことで高速に計算可能です
        k = length.bit_length() - 1
        
        # Sparse Table を用いた RMQ
        # 範囲 [L, R] をカバーする2つの重なり合う 2^k 長の範囲の最大値を比較します
        v1 = st[k][L]
        v2 = st[k][R - (1 << k) + 1]
        
        # 最大値を選択して結果リストに追加
        if v1 > v2:
            results.append(str(v1))
        else:
            results.append(str(v2))
            
    # 全ての結果を改行で連結して一度に出力します（高速化のため）
    sys.stdout.write('\n'.join(results) + '\n')

if __name__ == '__main__':
    solve()

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