\(B_1, \dots, B_M\) のうち \(L_i\) 以上 \(R_i\) 以下であるものの個数を愚直に数えるには \(\Omega(M)\) や \(\Omega(R_i-L_i)\) の時間がかかるため、毎回愚直に調べると最悪ケースでは TLEします。

\(A_i\) を、タイル \(i\) が損傷しているなら \(1\) 、していないなら \(0\) と定めると、「\(A_{L_i}+\dots+A_{R_i}\) は \(T\) 以下か？」という質問を \(K\) 回解けばよいです。これは区間和を繰り返し求める問題であるため、予め累積和を計算しておくことで質問 1 回あたり \(O(1)\) で答えることができます。よって前計算を含めこの問題を \(O(N+K)\) で解くことができました。

実装例 (C++)

#include<bits/stdc++.h>
using namespace std;

int main(){
  int n, m, k, t;
  cin >> n >> m >> k >> t;
  vector<int>a(n);
  for(int i=0; i<m; i++){
    int b;
    cin >> b;
    b--;
    a[b]=1;
  }

  vector<int>s(n+1);
  for(int i=0; i<n; i++){
    s[i+1] = s[i] + a[i];
  }

  for(int i=0; i<k; i++){
    int l, r;
    cin >> l >> r;
    l--, r--;
    if(s[r+1] - s[l] >= t){
      cout << "YES" << endl;
    }else{
      cout << "NO" << endl;
    }
  }
}

実装例 (Python)

N, M, K, T = map(int, input().split())
B = list(map(int, input().split()))

A = [0] * N
for b in B:
  A[b-1] = 1

S = [0] * (N+1)
for i in range(N):
  S[i+1] = S[i] + A[i]

for _ in range(K):
  L, R = map(int, input().split())
  if S[R] - S[L-1] >= T:
    print("YES")
  else:
    print("NO")