この問題はクエリ先読み＋セグメントツリーにより解くことができます。

まずは次の問題を考えます。

問題：\(N\) 個の棚があり、最初全て空である。以下の2種類のクエリを順に処理せよ

• \(i\) が与えられる。棚 \(i\) に本を 1 冊置く
• \(L,R\) が与えられる。番号が \(L\) 以上 \(R\) 以下である棚に置かれている本の数を求める

この問題はセグメントツリーや Fenwick Tree を用いて解くことができます。

元の問題を考えます。 \(Q\) 回の検索を先読みすることで、検索は \(T\) の降順に行われるとしてよいです。このとき、問題は次のように読み替えることができます。

問題：\(N\) 個の棚があり、最初全て空である。また、棚に置かれていない本が \(M\) 冊ある。以下のクエリを順に処理せよ

• まだ棚に置かれていない本のうち、ページ数が \(T\) 以上の本を指定された棚に置く。その後、棚の番号が \(L\) 以上 \(R\) 以下である棚に置かれている本の数を求める

クエリが \(T\) の降順に与えられることから、本を棚から取り除く必要がないことに注意してください。

この問題は予め本をページ数の降順にソートしておくことで、先に述べた問題と同じになるため解くことができます。

計算量は \(O(Q\log Q+Q\log N+M\log M)\) となります。

実装例 (C++)

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

int main() {
  int n, m, q, k;
  cin >> n >> m >> q >> k;

  vector<pair<int,int>>ds(m);
  for(int i=0; i<m; i++){
    int s, d;
    cin >> s >> d;
    s--;
    ds[i] = {d, s};
  }
  sort(ds.rbegin(), ds.rend());

  vector<tuple<int,int,int,int>>query(q);
  for(int i=0; i<q; i++){
    int l, r, t;
    cin >> l >> r >> t;
    l--;
    query[i] = {t, l, r, i};
  }
  sort(query.rbegin(), query.rend());

  vector<int>ans(q);
  int pos = 0;
  atcoder::fenwick_tree<int>seg(n);
  for(auto [t, l, r, i]: query){
    while(pos < m && ds[pos].first >= t){
      seg.add(ds[pos].second, 1);
      pos++;
    }
    ans[i] = max(seg.sum(l, r) - k, 0);
  }

  for(int i=0; i<q; i++){
    cout << ans[i] << endl;
  }
}

実装例 (Python)

from atcoder.fenwicktree import FenwickTree
N, M, Q, K = map(int, input().split())

DS = []
for _ in range(M):
  S, D = map(int, input().split())
  S -= 1
  DS.append((D, S))
DS.sort(reverse=True)

query = []
for i in range(Q):
  L, R, T = map(int, input().split())
  L -= 1
  query.append((T, L, R, i))
query.sort(reverse=True)

ans = [0] * Q
pos = 0
seg = FenwickTree(N)
for t, l, r, i in query:
  while pos < M and DS[pos][0] >= t:
    seg.add(DS[pos][1], 1)
    pos += 1
  ans[i] = max(seg.sum(l, r) - K, 0)

print(*ans, sep="\n")