概要

各バスで「弁当が生徒数以上あるか」を判定し、その条件を満たさないバスが区間内に1台でもあるかどうかを、各クエリ（休憩プラン）ごとに高速に調べる問題です。

考察

バス \(i\) が配布可能かどうかは \(S_i \ge P_i\) で一発判定できます。休憩プラン \((L, R)\) が配布可能である条件は、

• 区間 \([L, R]\) に 配布不可（\(S_i < P_i\)）のバスが 1台も含まれない

と言い換えられます。

素朴に各クエリごとに \(i=L..R\) を全探索して「配布不可のバスがあるか」を調べると、最悪で \(O(NM)\) になり、\(N, M \le 2\times 10^5\) では到底間に合いません。

そこで、「配布不可のバスの個数」を区間で素早く数えられるようにします。区間内の配布不可バス数が \(0\) なら Yes、\(1\) 以上なら No です。

アルゴリズム

1. 各バスについて、配布不可なら \(1\)、配布可能なら \(0\) の配列 \(bad[i]\) を作る（\(1 \le i \le N\)）。
   • \(bad[i] = 1 \iff S_i < P_i\)
2. \(bad\) の累積和（前計算）\(pref\) を作る：
   • \(pref[0]=0\)
   • \(pref[i] = pref[i-1] + bad[i]\)
3. クエリ \((L, R)\) に対して、区間 \([L, R]\) の配布不可バス数は
   • \(pref[R] - pref[L-1]\) で求まる。
4. これが \(0\) なら区間内に配布不可バスが存在しないので Yes、そうでなければ No。

具体例

例えば \(bad = [0, 1, 0, 1, 0]\)（2番と4番のバスが配布不可）なら、 - \([1,3]\) の配布不可数は \(1\)（2番がある）→ No - \([3,3]\) の配布不可数は \(0\) → Yes

計算量

• 時間計算量: 前計算 \(O(N)\)、各クエリ \(O(1)\) なので合計 \(O(N+M)\)
• 空間計算量: 累積和配列などで \(O(N)\)

実装のポイント

• 入力は \(1\)-index の区間 \([L, R]\) ですが、Pythonの配列は \(0\)-index なので、累積和 \(pref\) を長さ \(N+1\) にし、\(pref[i]\) を「先頭から \(i\) 台までの合計」として扱うとミスが減ります。

• 区間和は必ず \(pref[R] - pref[L-1]\) になる（\(L=1\) のときも \(pref[0]\) が使える）ように設計します。

• 出力はまとめて "\n".join(...) で高速化しています。

  ソースコード

import sys

def main():
    input = sys.stdin.readline
    N, M = map(int, input().split())
    S = list(map(int, input().split()))
    P = list(map(int, input().split()))

    pref = [0] * (N + 1)
    for i in range(1, N + 1):
        bad = 1 if S[i - 1] < P[i - 1] else 0
        pref[i] = pref[i - 1] + bad

    out = []
    for _ in range(M):
        L, R = map(int, input().split())
        out.append("Yes" if pref[R] - pref[L - 1] == 0 else "No")

    sys.stdout.write("\n".join(out))

if __name__ == "__main__":
    main()

---

この解説は gpt-5.2-high によって生成されました。