概要

\(N\) 枚のタイルのうち \(M\) 枚が損傷しており、与えられた \(K\) 個の区間 \([L_i, R_i]\) 内に損傷したタイルが \(T\) 枚以上含まれるかどうかを判定する問題です。

考察

素朴なアプローチ

各車について、タイル \(L_i\) から \(R_i\) までを一つずつ確認し、損傷したタイルの数を数える方法が考えられます。 しかし、この方法では最悪の場合（すべての車がタイル \(1\) から \(N\) まで走る場合など）、\(1\) 回の判定に \(O(N)\) かかります。全体の計算量は \(O(K \times N)\) となり、今回の制約（\(N, K \leq 2 \times 10^5\)）では最大で \(4 \times 10^{10}\) 回程度の計算が必要になるため、実行時間制限に間に合いません。

効率的なアプローチ

「特定の範囲内の合計値を高速に求める」という問題設定は、累積和 (Prefix Sum) を用いることで効率化できます。 あらかじめ「左から \(i\) 番目までのタイルに、損傷したタイルが何枚あるか」という情報を計算しておけば、任意の区間 \([L, R]\) に含まれる損傷タイルの枚数を \(O(1)\) で求めることが可能になります。

アルゴリズム

以下の手順で解を求めます。

1. 損傷情報の記録: 長さ \(N+1\) の配列 damaged を用意し、タイル \(B_j\) が損傷していれば damaged[B_j] = 1、そうでなければ 0 とします。
2. 累積和の構築: 長さ \(N+1\) の配列 prefix_sum を作成します。
   • prefix_sum[0] = 0
   • prefix_sum[i] = prefix_sum[i-1] + damaged[i] （\(1 \leq i \leq N\)） これにより、prefix_sum[i] はタイル \(1\) から \(i\) までの損傷タイルの総数になります。
3. クエリの処理: 各車（区間 \([L, R]\)）について、損傷タイルの枚数 count は以下の計算で求められます。
   • count = prefix_sum[R] - prefix_sum[L-1] この count が閾値 \(T\) 以上であれば YES、そうでなければ NO を出力します。

計算量

• 時間計算量: \(O(N + M + K)\)
  • 損傷情報の記録に \(O(M)\)、累積和の構築に \(O(N)\)、各クエリの処理に \(O(1)\) ずつ（計 \(O(K)\)）かかるため、全体で線形時間で処理可能です。
• 空間計算量: \(O(N)\)
  • タイルの情報を保持するための配列（damaged や prefix_sum）に \(O(N)\) のメモリを使用します。

実装のポイント

• 高速な入出力: \(N\) や \(K\) が \(2 \times 10^5\) と大きいため、Python では input() を繰り返すよりも sys.stdin.read().split() などで一括で読み込み、sys.stdout.write() で一括で出力する方が実行時間を大幅に短縮できます。

• インデックスの扱い: タイル番号が \(1\) から始まっているため、累積和の配列を \(N+1\) のサイズで確保し、prefix_sum[L-1] を引くことで区間 \([L, R]\) の和を正しく計算できます。

  ソースコード

import sys

def solve():
    # 入力を一括で読み込み、高速化を図る
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    idx = 0
    N = int(input_data[idx])
    M = int(input_data[idx+1])
    K = int(input_data[idx+2])
    T = int(input_data[idx+3])
    idx += 4
    
    # 損傷したタイルの情報を取得
    damaged = [0] * (N + 1)
    for _ in range(M):
        b = int(input_data[idx])
        damaged[b] = 1
        idx += 1
        
    # 累積和を計算して、ある範囲内の損傷タイル数をO(1)で求められるようにする
    prefix_sum = [0] * (N + 1)
    for i in range(1, N + 1):
        prefix_sum[i] = prefix_sum[i-1] + damaged[i]
        
    # 各車のクエリを処理
    results = []
    for _ in range(K):
        L = int(input_data[idx])
        R = int(input_data[idx+1])
        idx += 2
        
        # [L, R] の範囲に含まれる損傷タイルの枚数
        count = prefix_sum[R] - prefix_sum[L-1]
        
        if count >= T:
            results.append("YES")
        else:
            results.append("NO")
            
    # 結果をまとめて出力
    sys.stdout.write("\n".join(results) + "\n")

if __name__ == "__main__":
    solve()

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