概要

各区間に対して、損傷したタイルの数を数え、それが閾値以上かどうかを判定する問題。

考察

この問題では、各車の通行区間 \([L_i, R_i]\) に対して、損傷しているタイルがいくつ含まれているかを高速に求める必要があります。

素朴な方法として、毎回 \([L_i, R_i]\) の範囲にある損傷タイルの数を線形探索で数える方法がありますが、これは最大で \(O(N)\) の計算が必要になり、最悪ケースで全体で \(O(K \cdot N)\) となり、制約が大きいため時間内に終わりません（\(K, N \leq 2 \times 10^5\)）。

そこで、損傷タイルのリストをソートしておき、二分探索を用いることで各区間における損傷タイルの数を高速に求めることができます。具体的には、ソートされた損傷タイルのリスト上で、区間 \([L_i, R_i]\) に含まれる要素の個数を以下のように求めます：

• \(L_i\) 以上の最小のインデックス：bisect_left
• \(R_i\) 以下の最大のインデックス＋1：bisect_right

この2つの差が、区間に含まれる損傷タイルの個数になります。

例えば、損傷タイルが [3, 7, 10, 15] で、区間が [5, 12] のとき： - bisect_left(B, 5) → インデックス 1（要素 7） - bisect_right(B, 12) → インデックス 3（要素 15 の位置） - 差は \(3 - 1 = 2\) → 区間に含まれるのは 7 と 10 の2枚

この方法により、各クエリに対して \(O(\log M)\) で答えが求められるようになります。

アルゴリズム

1. 損傷タイルのリスト \(B\) をソートする。
2. 各車の通行区間 \([L_i, R_i]\) に対して以下を行う：
   • bisect_left(B, L_i) で \(L_i\) 以上の最小のインデックスを得る。
   • bisect_right(B, R_i) で \(R_i\) 以下の最大のインデックス＋1を得る。
   • その差が損傷タイルの個数。
   • 個数が \(T\) 以上なら YES、そうでなければ NO を出力。

計算量

• 時間計算量: \(O(M \log M + K \log M)\)
  
  • ソートに \(O(M \log M)\)、各クエリ処理に \(O(\log M)\) を \(K\) 回行う。
• 空間計算量: \(O(M)\)
  
  • 損傷タイルのリストを保持するのに必要な領域。

実装のポイント

• 損傷タイルのリストは事前にソートしておく必要がある。

• bisect_left と bisect_right の使い分けに注意（境界条件の扱いが異なる）。

• Python では bisect モジュールを使うと簡単に実装できる。

  ソースコード

import bisect

# 入力読み込み
N, M, K, T = map(int, input().split())
B = list(map(int, input().split()))
B.sort()

# 各車について処理
for _ in range(K):
    L, R = map(int, input().split())
    # 損傷タイルの中で [L, R] に含まれる個数をカウント
    left_idx = bisect.bisect_left(B, L)
    right_idx = bisect.bisect_right(B, R)
    count = right_idx - left_idx
    if count >= T:
        print("YES")
    else:
        print("NO")

この解説は qwen3-coder-480b によって生成されました。