概要

道路上の各車の通行区間に含まれる損傷タイルの枚数を高速に求め、それが閾値 \(T\) 以上かどうかを判定する問題です。累積和（prefix sum） を用いることで、各クエリに \(O(1)\) で答えることができます。

考察

素朴なアプローチとその問題点

最も単純な方法は、各車の通行区間 \([L_i, R_i]\) について、タイル \(L_i\) から \(R_i\) まで1枚ずつ損傷しているか確認することです。しかし、この方法では1台の車あたり最大 \(O(N)\) の計算が必要で、\(K\) 台すべてに対して行うと最悪 \(O(N \times K) = O(2 \times 10^5 \times 2 \times 10^5) = O(4 \times 10^{10})\) となり、制限時間に間に合いません。

重要な気づき

求めたいのは「区間 \([L_i, R_i]\) に含まれる損傷タイルの枚数」です。これは 区間の合計値 を求める問題であり、累積和 を事前に構築しておけば、各クエリに \(O(1)\) で答えられます。

具体例として、\(N = 7\) でタイル \(2, 5, 6\) が損傷している場合を考えます：

区間 \([3, 6]\) の損傷タイル数は \(\text{prefix}[6] - \text{prefix}[2] = 3 - 1 = 2\) と即座に求まります。

アルゴリズム

1. 損傷配列の構築: 長さ \(N+1\) の配列 damage を用意し、損傷タイル番号 \(B_j\) に対して damage[B_j] = 1 とする。
2. 累積和の構築: 配列 prefix を用意し、\(\text{prefix}[i] = \text{prefix}[i-1] + \text{damage}[i]\) と計算する。\(\text{prefix}[i]\) はタイル \(1\) からタイル \(i\) までの損傷タイルの合計枚数を表す。
3. 各クエリへの回答: 車 \(i\) の通行区間 \([L_i, R_i]\) に含まれる損傷タイルの枚数は \(\text{prefix}[R_i] - \text{prefix}[L_i - 1]\) で求まる。この値が \(T\) 以上なら YES、そうでなければ NO を出力する。

計算量

• 時間計算量: \(O(N + M + K)\)
  • 損傷配列の構築に \(O(M)\)、累積和の構築に \(O(N)\)、\(K\) 個のクエリへの回答に \(O(K)\)
• 空間計算量: \(O(N)\)
  • 損傷配列と累積和配列にそれぞれ \(O(N)\)

実装のポイント

• 累積和の添字に注意: prefix[0] = 0 として、区間 \([L, R]\) の合計を prefix[R] - prefix[L-1] で求める。\(L = 1\) の場合も prefix[0] = 0 により正しく計算できる。

• 高速入出力: \(K\) が最大 \(2 \times 10^5\) と大きいため、Python では sys.stdin.readline による入力高速化と、結果をリストに溜めて最後にまとめて sys.stdout.write で出力することで、TLE を回避している。

• 損傷タイルの番号が昇順とは限らない点に注意が必要だが、累積和を構築する際はタイル番号の位置にフラグを立てるだけなので、順序は関係ない。

  ソースコード

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

この解説は claude4.6opus-thinking によって生成されました。