概要

各バスが弁当の配布条件を満たしているかを確認し、休憩プランごとに指定された連続するバス区間内のすべてのバスが条件を満たしているかを判定する問題です。

考察

各休憩プランでは、区間 \([L_j, R_j]\) 内のすべてのバスについて \(S_i \geq P_i\) が成り立つかどうかを確認する必要があります。素朴なアプローチでは、各クエリごとに区間内のすべてのバスをチェックすると、最悪ケースで \(O(N \times M)\) の時間計算量となり、\(N\) と \(M\) が最大 \(2 \times 10^5\) ずつあるため、\(4 \times 10^{10}\) 回の操作が必要となり、実行時間制限に間に合いません。

そこで、各バスについて条件を満たさない場合（\(S_i < P_i\)）を1、満たす場合を0で表した配列を作成し、区間内の最大値が0か1かを効率的に求めることで、各クエリを高速に処理できます。

アルゴリズム

1. 各バス \(i\) について、\(S_i < P_i\) なら1、そうでなければ0を要素とする配列 arr を作成します。
2. セグメント木（区間最大値クエリを処理可能）を構築します。
3. 各休憩プラン \(j\) について、区間 \([L_j-1, R_j)\) の最大値をセグメント木で取得します。
   • 最大値が0の場合：区間内のすべてのバスが条件を満たすため「Yes」
   • 最大値が1の場合：条件を満たさないバスが存在するため「No」

セグメント木を用いることで、各クエリを \(O(\log N)\) で処理できます。

計算量

• 時間計算量: \(O((N + M) \log N)\)
  • セグメント木の構築に \(O(N)\)、各クエリの処理に \(O(\log N)\)
• 空間計算量: \(O(N)\)
  • セグメント木のサイズが \(O(N)\)

実装のポイント

• セグメント木のサイズを2の冪乗に調整することで、完全二分木として実装しています。

• クエリ処理では、区間の最大値を効率的に求めるため、セグメント木の標準的な探索方法（ボトムアップ）を使用しています。

• 入力の読み込みには sys.stdin.read を使用し、高速化を図っています。

  ソースコード

import sys

def main():
    data = sys.stdin.read().split()
    it = iter(data)
    n = int(next(it))
    m = int(next(it))
    S = [int(next(it)) for _ in range(n)]
    P = [int(next(it)) for _ in range(n)]
    
    # 各バスについて、条件を満たすかどうか（S_i >= P_i）を0/1で表現
    # 条件を満たさない（S_i < P_i）場合は1、満たす場合は0
    arr = [0] * n
    for i in range(n):
        if S[i] < P[i]:
            arr[i] = 1
    
    # セグメント木（区間の最大値または合計を求める）を構築
    # ここでは区間に1が存在するかどうか（最大値が1か）を確認すれば十分
    size = 1
    while size < n:
        size <<= 1
    seg = [0] * (2 * size)
    
    # セグ木の構築
    for i in range(n):
        seg[size + i] = arr[i]
    for i in range(size - 1, 0, -1):
        seg[i] = max(seg[2*i], seg[2*i+1])
    
    def query(l, r):
        l += size
        r += size
        res = 0
        while l < r:
            if l & 1:
                res = max(res, seg[l])
                l += 1
            if r & 1:
                r -= 1
                res = max(res, seg[r])
            l //= 2
            r //= 2
        return res
    
    output_lines = []
    for _ in range(m):
        l = int(next(it)) - 1
        r = int(next(it))
        max_val = query(l, r)
        if max_val == 0:
            output_lines.append("Yes")
        else:
            output_lines.append("No")
    
    print("\n".join(output_lines))

if __name__ == "__main__":
    main()

この解説は deepseekv3 によって生成されました。