概要

\(N\) 台の各バスについて「弁当が足りているか」を判定し、与えられた \(M\) 個の区間 \([L_j, R_j]\) 内に「弁当が足りないバス」が 1 台も存在しないかを高速に判定する問題です。

考察

1. 個別のバスの判定

まず、各バス \(i\) が「配布可能」か「配布不可」かは、与えられた \(S_i\) と \(P_i\) を比較することで簡単にわかります。 - \(S_i \geq P_i\) ならば配布可能（OK） - \(S_i < P_i\) ならば配布不可（NG）

2. 素朴なアプローチ

各休憩プラン（クエリ）に対して、毎回 \(L_j\) から \(R_j\) までのバスを 1 台ずつ確認していく方法が考えられます。 しかし、この方法では 1 つのクエリにつき最大で \(N\) 回の確認が必要になります。クエリの数は \(M\) 個あるため、最悪の場合の計算量は \(O(N \times M)\) となります。 本問題では \(N, M \leq 2 \times 10^5\) であるため、計算回数は最大で \(4 \times 10^{10}\) 回に達し、制限時間内に終わりません。

3. 累積和による高速化

「区間内に NG なバスが 1 台でも存在するか」を高速に判定するために、累積和の考え方を利用します。

まず、各バスの状態を次のような数値に置き換えます。 - 配布不可（NG）なバス \(i\) の場合： \(A_i = 1\) - 配布可能（OK）なバス \(i\) の場合： \(A_i = 0\)

このとき、ある区間 \([L, R]\) 内に配布不可なバスが存在するかどうかは、「区間内の \(A_i\) の総和が 1 以上であるか」を調べることと同義になります。

区間の総和を高速に求めるために、あらかじめ累積和配列 \(pref\) を作成します。 - \(pref[k] = A_1 + A_2 + \dots + A_k\) （先頭から \(k\) 台目までの NG バスの総数）

これを用意しておけば、任意の区間 \([L, R]\) における NG バスの個数は以下の計算により \(O(1)\) で求められます。 - 区間内の NG 数 \(= pref[R] - pref[L-1]\)

この値が \(0\) であればそのプランは Yes（配布可能）、\(1\) 以上であれば No（配布不可）と判定できます。

アルゴリズム

1. 各バス \(i = 1, \dots, N\) について、\(S_i < P_i\) かどうかを判定する。
2. 判定結果を \(0\) または \(1\) の配列 \(A\) とし、その累積和配列 \(pref\) を構築する。
3. 各クエリ \((L_j, R_j)\) に対して、\(pref[R_j] - pref[L_j-1]\) を計算する。
4. 計算結果が \(0\) なら Yes、そうでなければ No を出力する。

計算量

• 時間計算量: \(O(N + M)\)
  • 累積和の構築に \(O(N)\)、各クエリの回答に \(O(1)\) かかるため、全体で \(O(N + M)\) となり、十分に高速です。
• 空間計算量: \(O(N)\)
  • 入力データおよび累積和配列を保持するために \(O(N)\) のメモリを使用します。

実装のポイント

• 高速な入出力: Python では \(N, M\) が \(2 \times 10^5\) 規模になると、標準の input() では間に合わないことがあります。sys.stdin.read().split() などを使って一括で読み込むのが効果的です。

• インデックスの調整: 問題文は 1-indexed（1始まり）ですが、プログラムの配列は 0-indexed（0始まり）であることが多いため、累積和の範囲指定（特には左端 \(L-1\)）に注意が必要です。

  ソースコード

import sys

def solve():
    # 競技プログラミングにおいて、入力を一度に読み込んで処理するのは高速化の一般的な手法です。
    # sys.stdin.read().split() は、すべての空白文字（スペース、改行など）で分割された文字列のリストを返します。
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # すべての入力文字列を整数のリストに変換します。
    # これにより、インデックスによる高速なアクセスが可能になります。
    data = list(map(int, input_data))
    
    # バスの台数 N と休憩プランの数 M を取得します。
    N = data[0]
    M = data[1]
    
    # 弁当の数 S_i と生徒の人数 P_i のデータが始まる位置（オフセット）を設定します。
    # S_1, S_2, ..., S_N は data[2] から data[N+1] まで
    # P_1, P_2, ..., P_N は data[N+2] から data[2N+1] までに格納されています。
    s_offset = 2
    p_offset = 2 + N
    
    # 各バスにおいて弁当が足りない（S_i < P_i）かどうかを判定し、累積和を計算します。
    # pref[k] は、バス 1 からバス k までの間で弁当が不足しているバスの総数を表します。
    # これにより、任意の区間 [L, R] における不足バスの有無を O(1) で判定できます。
    pref = [0] * (N + 1)
    for i in range(N):
        # バス (i+1) が弁当不足（配布不可）かどうかをチェック
        if data[s_offset + i] < data[p_offset + i]:
            pref[i+1] = pref[i] + 1
        else:
            pref[i+1] = pref[i]
            
    # クエリ（休憩プラン）が始まる位置を設定します。
    query_start = 2 + 2 * N
    results = []
    
    # 各休憩プランについて判定を行います。
    for j in range(M):
        # L_j と R_j は 1-indexed で与えられます。
        L = data[query_start + 2 * j]
        R = data[query_start + 2 * j + 1]
        
        # 区間 [L, R] 内に弁当不足のバスが 1 台も存在しない場合、
        # pref[R] - pref[L-1] が 0 になります。
        if pref[R] - pref[L-1] == 0:
            results.append("Yes")
        else:
            results.append("No")
            
    # 判定結果を改行区切りで一括出力します。
    sys.stdout.write("\n".join(results) + "\n")

if __name__ == "__main__":
    solve()

---

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