Overview

Given queries that specify a range of shelf numbers and a lower bound on page count, the problem asks to compute the number of books satisfying the conditions minus a non-negative integer \(K\) (or 0 if the result would be negative).

Analysis

A naive approach of checking all books for each query would result in a time complexity of \(O(Q \times M)\). Since both \(Q\) and \(M\) can be up to \(10^5\), this would require \(10^{10}\) operations, which cannot be executed within the time limit.

The key observation is that by sorting queries by their page count lower bound \(T_j\), we can process them efficiently. We add books to a data structure in decreasing order of page count. For each query, we find “the number of books currently in the data structure whose shelf number falls within the interval \([L_j, R_j]\),” which is exactly the number of books with page count at least \(T_j\).

Algorithm

1. Preprocessing:

   • Sort books in decreasing order of page count
   • Sort queries in decreasing order of page count lower bound \(T_j\)

2. Fenwick Tree (BIT):

   • Prepare a Fenwick Tree indexed by shelf number
   • Add books in decreasing order of page count, incrementing by 1 at the position corresponding to each book’s shelf number

3. Query Processing:

   • Process queries in decreasing order of \(T_j\)
   • Add all books with page count at least \(T_j\) of the current query to the Fenwick Tree
   • Query the Fenwick Tree for the sum over the interval \([L_j, R_j]\), and store \(max(\text{sum} - K, 0)\) as the result

Complexity

• Time complexity: \(O((M + Q) \log N)\)
  • Sorting: \(O(M \log M + Q \log Q)\)
  • Fenwick Tree operations: adding each book and processing each query takes \(O(\log N)\)
• Space complexity: \(O(N + M + Q)\)

Implementation Notes

• Books and queries need to be sorted separately

• Since queries must be output in their original order, the original indices must be retained

• The Fenwick Tree is implemented with 1-based indexing

• The processing order of books with the same page count does not affect the result, so a stable sort is not required

  Source Code

import sys

class Fenw:
    def __init__(self, n):
        self.n = n
        self.tree = [0] * (n+1)
    
    def update(self, index, delta):
        i = index
        while i <= self.n:
            self.tree[i] += delta
            i += i & -i
            
    def query(self, index):
        s = 0
        i = index
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
    
    def range_query(self, l, r):
        return self.query(r) - self.query(l-1)

def main():
    data = sys.stdin.read().split()
    it = iter(data)
    N = int(next(it)); M = int(next(it)); Q = int(next(it)); K = int(next(it))
    books = []
    for i in range(M):
        s = int(next(it)); d = int(next(it))
        books.append((s, d))
        
    queries = []
    for j in range(Q):
        l = int(next(it)); r = int(next(it)); t = int(next(it))
        queries.append((t, l, r, j))
        
    # 本をページ数で降順ソート
    books.sort(key=lambda x: x[1], reverse=True)
    # クエリをTで降順ソート
    queries.sort(key=lambda x: x[0], reverse=True)
    
    fenw = Fenw(N)
    res = [0] * Q
    idx = 0
    # ページ数が大きい本から追加していく
    for t_val, l, r, orig_idx in queries:
        while idx < M and books[idx][1] >= t_val:
            s = books[idx][0]
            fenw.update(s, 1)
            idx += 1
        count = fenw.range_query(l, r)
        res[orig_idx] = max(count - K, 0)
        
    for ans in res:
        print(ans)

if __name__ == "__main__":
    main()

This editorial was generated by deepseekv3.