Overview

Manage books by grouping them based on “whether the page count meets the condition or not,” and for each query \((L,R,T)\), efficiently count “how many books with page count \(\ge T\) are in the shelf range \([L,R]\)” and output \(\max(C-K,0)\).

Analysis

Each query has two conditions:

• The shelf number falls within the range \([L,R]\)
• The page count is at least \(T\)

A naive approach would check all \(M\) books for each query, resulting in \(O(MQ)\) time, which requires up to about \(10^{10}\) checks and is too slow.

The key observation is as follows:

• The “page count threshold \(T\)” varies per query, but if we process queries in decreasing order of \(T\), the “set of books with sufficiently large page count” grows monotonically.
• At any point, if we consider only “books with page count \(\ge\) the current \(T\)” as active, then each query becomes:
  • “How many active books are in the shelf range \([L,R]\)?” which is a 1-dimensional range counting problem.

The count within a 1-dimensional range can be efficiently handled using a Fenwick Tree (BIT) with “add 1 at a shelf number” updates and “prefix sum” queries.

Additionally, since we subtract \(K\) due to a system malfunction and round to 0 if negative, we simply output \(\max(C-K,0)\) for the computed count \(C\).

Algorithm

We solve this using offline processing (sort everything first, then process).

1. Store each book as \((D_i, S_i)\) (page count, shelf) and sort in descending order of page count \(D_i\).
2. Store each query as \((T_j, L_j, R_j, j)\) and sort in descending order of threshold \(T_j\) (keeping the original index \(j\) to restore the output order).
3. Prepare a Fenwick Tree (of size \(N\)).
   The Fenwick Tree stores “how many currently active books are on each shelf” (add 1 at shelf \(s\)).
4. Process queries in decreasing order of \(T\), and for each query \((T,L,R)\):
   • Add all not-yet-added books with page count \(D \ge T\) to the Fenwick Tree (add(S, 1) at shelf \(S\)).
   • Now the Fenwick Tree counts exactly the “books with page count \(\ge T\).”
   • The number of books in the range \([L,R]\) is sum(R) - sum(L-1).
   • The answer is \(\max(\text{cnt} - K, 0)\).
5. Use the stored indices to output answers in the original query order.

Concrete example (intuitive idea): - When processing a query with \(T=100\), add all books with “page count \(\ge 100\)” and count them. - When moving to the next query with \(T=80\), only books with “\(80 \le \text{page count} < 100\)” need to be newly added; the previously added books remain (the set grows monotonically).

Complexity

• Time complexity:
  Sorting books \(O(M\log M)\), sorting queries \(O(Q\log Q)\), Fenwick Tree updates and queries total \(O((M+Q)\log N)\)
  Overall \(O((M+Q)\log N)\) (this order dominates even including the sorting).
• Space complexity: \(O(N + M + Q)\) (Fenwick Tree array and input storage)

Implementation Notes

• The Fenwick Tree is 1-indexed (shelf numbers are \(1..N\), so they can be used directly, which is convenient).

• Since sorting queries changes the output order, always store the original index and save results in ans[idx].

• Use the pattern while books[bi].D >= T: to “add all eligible books at once,” ensuring each book is inserted into the Fenwick Tree at most once.

• Don’t forget to output \(\max(\text{cnt}-K,0)\) at the end (the value can be negative).

  Source Code

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

---

This editorial was generated by gpt-5.2-high.