概要

損傷タイルがある一直線の道路について、各クエリ区間 \([L_i, R_i]\) に含まれる損傷タイル数を数え、\(T\) 以上なら YES を出力します。

考察

各車（クエリ）ごとに「区間内の損傷タイル枚数」を求めたい問題です。

素朴にやると、クエリごとに \(L_i\) から \(R_i\) までを走査して損傷を数えることになります。しかし区間長は最大で \(N\)、クエリ数は最大で \(K=2\times 10^5\) なので、最悪の場合 \(O(NK)\) となり到底間に合いません（例：\(N=K=2\times 10^5\) だと \(4\times 10^{10}\) 程度）。

ここで重要な気づきは、損傷タイルの情報は固定であり、複数クエリで何度も「ある区間の和」を尋ねている、という点です。こうした「区間の和」を高速に答える典型手法が累積和（prefix sum）です。

アルゴリズム

1. 長さ \(N\) の配列 damaged を用意し、タイル \(i\) が損傷していれば damaged[i]=1、そうでなければ 0 とする。
2. 累積和配列 pref を作る。
   $\( pref[i] = damaged[1] + damaged[2] + \cdots + damaged[i] \)$
3. 各クエリ \([L, R]\) について、区間内の損傷タイル数は累積和で $\( damaged[L] + \cdots + damaged[R] = pref[R] - pref[L-1] \)\( と \)O(1)$ で求まる。
4. その値が \(T\) 以上なら YES、未満なら NO を出力する。

（例）損傷が [2, 5, 6] のとき damaged = [0,1,0,0,1,1,...] のようになり、クエリ \([3,6]\) の損傷数は pref[6]-pref[2] で求まります。

計算量

• 時間計算量: \(O(N + M + K)\)
  （損傷の反映が \(O(M)\)、累積和構築が \(O(N)\)、各クエリが \(O(1)\) で合計 \(O(K)\)）
• 空間計算量: \(O(N)\)
  （damaged と pref の配列）

実装のポイント

• pref[L-1] を使うため、配列を \(1\)-indexed にし、サイズを N+1 にして pref[0]=0 としておくと簡単です。

• 入力が最大 \(2\times 10^5\) 規模なので、Python では sys.stdin.buffer.read() でまとめて読み取ると高速です。

  ソースコード

import sys

def main():
    it = list(map(int, sys.stdin.buffer.read().split()))
    idx = 0
    N = it[idx]; M = it[idx+1]; K = it[idx+2]; T = it[idx+3]
    idx += 4

    damaged = [0] * (N + 1)
    for _ in range(M):
        b = it[idx]
        idx += 1
        damaged[b] = 1

    pref = [0] * (N + 1)
    s = 0
    for i in range(1, N + 1):
        s += damaged[i]
        pref[i] = s

    out = []
    for _ in range(K):
        L = it[idx]; R = it[idx+1]
        idx += 2
        cnt = pref[R] - pref[L - 1]
        out.append("YES" if cnt >= T else "NO")

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

if __name__ == "__main__":
    main()

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