Overview

This is a problem where we need to efficiently determine the number of damaged tiles contained in each car’s travel interval on a road, and judge whether that count is at least the threshold \(T\). By using a prefix sum, we can answer each query in \(O(1)\).

Analysis

Naive Approach and Its Issues

The simplest method is, for each car’s travel interval \([L_i, R_i]\), to check tiles one by one from \(L_i\) to \(R_i\) to see if each is damaged. However, this method requires up to \(O(N)\) computation per car, and performing this for all \(K\) cars results in a worst case of \(O(N \times K) = O(2 \times 10^5 \times 2 \times 10^5) = O(4 \times 10^{10})\), which will not fit within the time limit.

Key Insight

What we want to find is “the number of damaged tiles contained in the interval \([L_i, R_i]\).” This is a problem of computing a range sum, and by precomputing a prefix sum, we can answer each query in \(O(1)\).

As a concrete example, consider \(N = 7\) where tiles \(2, 5, 6\) are damaged:

The number of damaged tiles in the interval \([3, 6]\) can be immediately obtained as \(\text{prefix}[6] - \text{prefix}[2] = 3 - 1 = 2\).

Algorithm

1. Build the damage array: Prepare an array damage of length \(N+1\), and for each damaged tile number \(B_j\), set damage[B_j] = 1.
2. Build the prefix sum: Prepare an array prefix and compute \(\text{prefix}[i] = \text{prefix}[i-1] + \text{damage}[i]\). Here, \(\text{prefix}[i]\) represents the total number of damaged tiles from tile \(1\) to tile \(i\).
3. Answer each query: The number of damaged tiles contained in car \(i\)’s travel interval \([L_i, R_i]\) is obtained by \(\text{prefix}[R_i] - \text{prefix}[L_i - 1]\). If this value is at least \(T\), output YES; otherwise, output NO.

Complexity

• Time complexity: \(O(N + M + K)\)
  • \(O(M)\) for building the damage array, \(O(N)\) for building the prefix sum, and \(O(K)\) for answering \(K\) queries
• Space complexity: \(O(N)\)
  • \(O(N)\) each for the damage array and the prefix sum array

Implementation Notes

• Be careful with prefix sum indices: Set prefix[0] = 0, and compute the sum over the interval \([L, R]\) as prefix[R] - prefix[L-1]. Even when \(L = 1\), the calculation is correct thanks to prefix[0] = 0.

• Fast I/O: Since \(K\) can be as large as \(2 \times 10^5\), in Python we avoid TLE by using sys.stdin.readline for faster input and by accumulating results in a list and outputting them all at once with sys.stdout.write at the end.

• Note that damaged tile numbers are not necessarily given in ascending order, but this does not matter since when building the prefix sum we simply set a flag at each tile number’s position, regardless of order.

  Source Code

import sys
input = sys.stdin.readline

def main():
    N, M, K, T = map(int, input().split())
    B = list(map(int, input().split()))
    
    # Build prefix sum array for damaged tiles
    damage = [0] * (N + 1)
    for b in B:
        damage[b] = 1
    
    # Prefix sum
    prefix = [0] * (N + 1)
    for i in range(1, N + 1):
        prefix[i] = prefix[i - 1] + damage[i]
    
    out = []
    for _ in range(K):
        L, R = map(int, input().split())
        count = prefix[R] - prefix[L - 1]
        out.append("YES" if count >= T else "NO")
    
    sys.stdout.write("\n".join(out) + "\n")

main()

This editorial was generated by claude4.6opus-thinking.