概要

本を「ページ数が条件以上かどうか」でまとめて管理し、各検索 \((L,R,T)\) に対して「ページ数 \(\ge T\) の本が棚区間 \([L,R]\) に何冊あるか」を高速に数えて \(\max(C-K,0)\) を出力します。

考察

各検索では条件が 2 つあります：

• 棚番号が区間 \([L,R]\) に入る
• ページ数が \(T\) 以上

素朴にやると、各検索ごとに全ての本 \(M\) 冊を見て条件判定するため \(O(MQ)\) となり、最大で \(10^{10}\) 回程度のチェックが必要になって間に合いません。

ここで重要な観察は次の通りです：

• 検索の「ページ数条件 \(T\)」は検索ごとに変わるが、\(T\) を大きい順に処理すると「ページ数が十分大きい本の集合」は単調に増える。
• ある時点で「ページ数が現在の \(T\) 以上の本」だけをアクティブ（有効）とみなせば、検索は
  • 「アクティブな本が棚区間 \([L,R]\) に何冊あるか」 という 1 次元の区間数え上げに変形できます。

1 次元の区間内個数は、Fenwick Tree（BIT）で「棚番号に 1 を足す」更新と「区間和」を高速に処理できます。

また、最後にシステム不具合として \(K\) を引き、負なら 0 に丸めるだけなので、求めた冊数 \(C\) に対し \(\max(C-K,0)\) を出力すればOKです。

アルゴリズム

オフライン処理（まとめて並べ替えてから処理）で解きます。

1. 本を \((D_i, S_i)\)（ページ数, 棚）として持ち、ページ数 \(D_i\) の 降順にソートする。
2. 検索を \((T_j, L_j, R_j, j)\) として持ち、下限 \(T_j\) の 降順にソートする（元の順番に戻すために index \(j\) を保持）。
3. Fenwick Tree（サイズ \(N\)）を用意する。
   Fenwick Tree には「現在アクティブな本が各棚に何冊あるか」を入れる（棚 \(s\) に 1 加算）。
4. 検索を \(T\) の大きい順に見ていき、各検索 \((T,L,R)\) について：
   • まだ追加していない本のうち、ページ数 \(D \ge T\) を満たす本をすべて Fenwick Tree に追加する（棚 \(S\) に add(S, 1)）。
   • すると Fenwick Tree 上で「ページ数 \(\ge T\) の本」だけが数えられる状態になる。
   • 区間 \([L,R]\) の冊数は sum(R) - sum(L-1) で求まる。
   • 答えは \(\max(\text{cnt} - K, 0)\)。
5. index を使って元の検索順に出力する。

具体例（考え方のイメージ）： - \(T=100\) の検索を処理するときは「ページ数 \(\ge 100\) の本」だけを全部追加して数える。 - 次に \(T=80\) の検索に移ると、追加すべき本は「\(80 \le \text{ページ数} < 100\) の本」だけで、前回追加した分はそのまま使える（単調に増える）。

計算量

• 時間計算量:
  本のソート \(O(M\log M)\)、検索のソート \(O(Q\log Q)\)、Fenwick の更新とクエリが合計 \(O((M+Q)\log N)\)
  よって全体で \(O((M+Q)\log N)\) 程度（支配項はソート込みでもこのオーダー）。
• 空間計算量: \(O(N + M + Q)\)（Fenwick 配列と入力保持）

実装のポイント

• Fenwick Tree は 1-indexed（棚番号が \(1..N\) なのでそのまま扱えて相性が良い）。

• 検索をソートすると出力順が崩れるため、必ず元の index を持って ans[idx] に格納する。

• while books[bi].D >= T: の形で「追加すべき本をまとめて追加」し、各本は高々 1 回だけ Fenwick に入れるようにする。

• 最後の出力は \(\max(\text{cnt}-K,0)\) を忘れない（負になりうる）。

  ソースコード

import sys

class Fenwick:
    __slots__ = ("n", "bit")
    def __init__(self, n):
        self.n = n
        self.bit = [0] * (n + 1)

    def add(self, i, x):
        n = self.n
        bit = self.bit
        while i <= n:
            bit[i] += x
            i += i & -i

    def sum(self, i):
        s = 0
        bit = self.bit
        while i > 0:
            s += bit[i]
            i -= i & -i
        return s

def main():
    data = sys.stdin.buffer.read().split()
    it = iter(data)
    N = int(next(it)); M = int(next(it)); Q = int(next(it)); K = int(next(it))

    books = []
    for _ in range(M):
        s = int(next(it)); d = int(next(it))
        books.append((d, s))
    books.sort(reverse=True)  # by d desc

    queries = []
    for idx in range(Q):
        l = int(next(it)); r = int(next(it)); t = int(next(it))
        queries.append((t, l, r, idx))
    queries.sort(reverse=True)  # by t desc

    fw = Fenwick(N)
    ans = [0] * Q
    bi = 0
    for t, l, r, idx in queries:
        while bi < M and books[bi][0] >= t:
            _, s = books[bi]
            fw.add(s, 1)
            bi += 1
        cnt = fw.sum(r) - fw.sum(l - 1)
        v = cnt - K
        ans[idx] = v if v > 0 else 0

    sys.stdout.write("\n".join(map(str, ans)))

if __name__ == "__main__":
    main()

---

この解説は gpt-5.2-high によって生成されました。