概要

\(N\) 台のバスそれぞれについて弁当が足りているか（\(S_i \geq P_i\)）を前処理し、\(M\) 件の区間クエリに対して「区間内のすべてのバスで弁当が足りているか」を高速に判定する問題です。

考察

問題の言い換え

各バス \(i\) について \(D_i = S_i - P_i\) という差分を計算すると、弁当が足りている条件 \(S_i \geq P_i\) は \(D_i \geq 0\) と同値です。

休憩プラン \(j\) が配布可能である条件は、区間 \([L_j, R_j]\) 内のすべての \(D_i\) が \(0\) 以上であること、すなわち：

\[\min_{L_j \leq i \leq R_j} D_i \geq 0\]

と言い換えられます。つまり、区間最小値（Range Minimum Query） を求める問題に帰着できます。

素朴なアプローチの問題点

各クエリごとに区間 \([L_j, R_j]\) を走査して最小値を求めると、1 クエリあたり最悪 \(O(N)\) かかり、全体で \(O(NM)\) となります。\(N, M\) がともに最大 \(2 \times 10^5\) なので、最悪 \(4 \times 10^{10}\) 回の計算となり TLE になります。

解決策

Sparse Table を使うと、\(O(N \log N)\) の前処理の後、各クエリに \(O(1)\) で区間最小値を答えられます。

アルゴリズム

Sparse Table とは

Sparse Table は、静的な配列に対する区間最小値（または最大値）クエリを高速に処理するデータ構造です。

前処理：

テーブル \(\text{sparse}[k][i]\) を「位置 \(i\) から始まる長さ \(2^k\) の区間の最小値」と定義します。

• \(k = 0\): \(\text{sparse}[0][i] = D_i\)（長さ \(1\) の区間）
• \(k \geq 1\): \(\text{sparse}[k][i] = \min(\text{sparse}[k-1][i],\ \text{sparse}[k-1][i + 2^{k-1}])\)

長さ \(2^k\) の区間を、前半 \(2^{k-1}\) と後半 \(2^{k-1}\) に分割して合成しています。

クエリ：

区間 \([L, R]\)（長さ \(\ell = R - L + 1\)）の最小値を求めるとき、\(k = \lfloor \log_2 \ell \rfloor\) として：

\[\min(\text{sparse}[k][L],\ \text{sparse}[k][R - 2^k + 1])\]

これは区間を 2 つの長さ \(2^k\) の区間で重複を許して覆うテクニックです。\(\min\) 演算は重複があっても正しい結果を返すため、\(O(1)\) で答えが得られます。

具体例

\(N = 5\), \(S = [5, 3, 4, 2, 6]\), \(P = [3, 4, 1, 2, 7]\) のとき：

\(D = [2, -1, 3, 0, -1]\)

クエリ \([1, 3]\)（1-indexed）→ \(D_1, D_2, D_3 = 2, -1, 3\) → 最小値は \(-1 < 0\) → No

クエリ \([3, 4]\)（1-indexed）→ \(D_3, D_4 = 3, 0\) → 最小値は \(0 \geq 0\) → Yes

計算量

• 時間計算量: \(O(N \log N + M)\)（前処理に \(O(N \log N)\)、各クエリに \(O(1)\)）
• 空間計算量: \(O(N \log N)\)（Sparse Table の格納）

実装のポイント

• 1-indexed → 0-indexed の変換: 入力は 1-indexed なので、Sparse Table にアクセスする前に L -= 1, R -= 1 と変換しています。

• 対数テーブルの事前計算: クエリごとに math.log2 を呼ぶと遅いため、log_table 配列を前処理で計算しておくことで高速化しています。

• 出力の一括書き出し: Python では print を \(M\) 回呼ぶと遅いため、結果をリストに溜めて sys.stdout.write で一度に出力しています。

  ソースコード

import sys
input = sys.stdin.readline

def main():
    N, M = map(int, input().split())
    S = list(map(int, input().split()))
    P = list(map(int, input().split()))
    
    # Sparse table for range minimum of (S_i - P_i)
    # If min(S_i - P_i) for i in [L, R] >= 0, then "Yes"
    diff = [S[i] - P[i] for i in range(N)]
    
    import math
    LOG = max(1, math.floor(math.log2(N)) + 1) if N > 0 else 1
    
    sparse = [None] * (LOG + 1)
    sparse[0] = diff[:]
    
    for k in range(1, LOG + 1):
        length = 1 << k
        sparse[k] = [0] * N
        for i in range(N - length + 1):
            sparse[k][i] = min(sparse[k-1][i], sparse[k-1][i + (1 << (k-1))])
    
    # Precompute log2
    log_table = [0] * (N + 1)
    for i in range(2, N + 1):
        log_table[i] = log_table[i // 2] + 1
    
    out = []
    for _ in range(M):
        L, R = map(int, input().split())
        L -= 1
        R -= 1
        length = R - L + 1
        k = log_table[length]
        min_val = min(sparse[k][L], sparse[k][R - (1 << k) + 1])
        out.append("Yes" if min_val >= 0 else "No")
    
    sys.stdout.write('\n'.join(out) + '\n')

main()

---

この解説は claude4.6opus-thinking によって生成されました。