Overview

For a straight road with damaged tiles, count the number of damaged tiles in each query interval \([L_i, R_i]\), and output YES if it is at least \(T\).

Analysis

The problem asks us to find the “number of damaged tiles within an interval” for each car (query).

A naive approach would scan from \(L_i\) to \(R_i\) for each query to count the damage. However, the interval length can be up to \(N\) and the number of queries can be up to \(K=2\times 10^5\), so the worst case would be \(O(NK)\), which is far too slow (e.g., when \(N=K=2\times 10^5\), this is about \(4\times 10^{10}\)).

The key observation here is that the damaged tile information is fixed, and multiple queries repeatedly ask for “the sum over some interval.” The classic technique for answering such “interval sum” queries efficiently is the prefix sum.

Algorithm

1. Prepare an array damaged of length \(N\), where damaged[i]=1 if tile \(i\) is damaged, and 0 otherwise.
2. Build a prefix sum array pref.
   $\( pref[i] = damaged[1] + damaged[2] + \cdots + damaged[i] \)$
3. For each query \([L, R]\), the number of damaged tiles in the interval can be computed in \(O(1)\) using the prefix sum: $\( damaged[L] + \cdots + damaged[R] = pref[R] - pref[L-1] \)$
4. If this value is at least \(T\), output YES; otherwise, output NO.

(Example) When the damaged tiles are [2, 5, 6], we have damaged = [0,1,0,0,1,1,...], and the number of damaged tiles for query \([3,6]\) is computed as pref[6]-pref[2].

Complexity

• Time complexity: \(O(N + M + K)\)
  (Marking damage is \(O(M)\), building the prefix sum is \(O(N)\), and each query is \(O(1)\) for a total of \(O(K)\))
• Space complexity: \(O(N)\)
  (The damaged and pref arrays)

Implementation Notes

• Since we use pref[L-1], it is convenient to use \(1\)-indexed arrays with size N+1 and set pref[0]=0.

• Since the input can be up to \(2\times 10^5\) in scale, in Python it is faster to read all input at once using sys.stdin.buffer.read().

  Source Code

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()

This editorial was generated by gpt-5.2-high.