概要

\(N\) 日間の気温データに対し、「指定された期間 \([L, R]\) における最大値と最小値の差」を求めるクエリ \(Q\) 個に答える問題です。

考察

もっとも単純な方法は、各クエリごとに \(L\) 日目から \(R\) 日目までを走査して最大値と最小値を調べることです。しかし、この方法では 1 つのクエリに最大で \(O(N)\) の時間がかかります。クエリ数は \(Q\) 個あるため、全体の計算量は \(O(NQ)\) となります。 本問題の制約は \(N, Q \leq 10^5\) であるため、\(NQ \approx 10^{10}\) となり、一般的な制限時間（2秒程度）には到底間に合いません。

そこで、静的な配列に対する範囲クエリ（Range Query）を高速に処理できる手法が必要です。 今回の問題ではデータの更新がないため、Sparse Table（スパーステーブル）というデータ構造を利用することで、各クエリに対して \(O(1)\) で答えることができます。

アルゴリズム

Sparse Table

Sparse Table は、あらかじめ「長さが 2 のべき乗（1, 2, 4, 8…）」の区間に対する計算結果を計算しておく手法です。

1. 前処理:

   • st_max[k][i]：\(i\) 番目から始まる長さ \(2^k\) の区間内の最大値
   • st_min[k][i]：\(i\) 番目から始まる長さ \(2^k\) の区間内の最小値 これらを \(O(N \log N)\) かけて構築します。例えば st_max[k][i] は、st_max[k-1][i] と st_max[k-1][i + 2^{k-1}] の 2 つの値を比較するだけで求められます。

2. クエリ処理: 任意の長さ \(len\) の区間 \([L, R]\) は、「\(2^k \leq len\) を満たす最大の \(2^k\)」 を用いて、2 つの重なり合う区間で完全にカバーできます。

   • 区間 1: \(L\) から長さ \(2^k\)
   • 区間 2: \(R\) から左に（戻って）長さ \(2^k\)

   最大値や最小値（冪等性を持つ演算）は、区間が重なっていても結果が変わらないため、この 2 つの区間の値を比較するだけで、元の区間全体の答えが \(O(1)\) で求まります。

計算量

• 時間計算量: \(O(N \log N + Q)\)
  • 前処理（テーブルの構築）に \(O(N \log N)\)、各クエリの回答に \(O(1)\) かかります。
• 空間計算量: \(O(N \log N)\)
  • 長さ \(N\) の配列に対し、高さ \(\log N\) のテーブルを保持するためです。

実装のポイント

• 高速な入出力: \(N, Q\) が大きいため、Python では sys.stdin.read().split() や sys.stdout.write を使用して入出力を高速化することが重要です。
• ログの事前計算: クエリごとに \(\log\) を計算するのではなく、あらかじめ配列に計算しておくことで定数倍の高速化を図っています。
• Python での高速化: st_min[k] = list(map(min, prev_min, prev_min[offset:])) のように map 関数やスライスをうまく活用することで、Python のループを避け、内部の C 言語レベルの処理を利用して高速にテーブルを構築しています。

ソースコード

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

この解説は gemini-3-flash-preview によって生成されました。