Overview

This is a problem where you count the number of books \(C_j\) that are on shelves within the specified range \([L_j, R_j]\) and have at least \(T_j\) pages, then compute \(\max(C_j - K, 0)\).

Analysis

Let’s consider a naive approach (brute force) where for each query, we check all books to see if they satisfy the conditions. In this case, since we check \(M\) books per query, the overall time complexity is \(O(MQ)\). Given the constraints \(M, Q \leq 10^5\), in the worst case this requires about \(10^{10}\) operations, which will exceed the time limit (TLE).

The key to solving this problem efficiently lies in “having two conditions (shelf number and page count)” and “all queries being given in advance (offline processing)”.

If there were no condition “page count at least \(T_j\)” and we only needed to find “the number of books on shelves in the range \([L_j, R_j]\)”, we could use a data structure like a Fenwick Tree (Binary Indexed Tree, BIT) to process each query in \(O(\log N)\).

To handle the page count condition efficiently, we use a technique of sorting both books and queries in descending order of page count (query pre-reading / event sorting). By processing in descending order, we can replace the condition “page count at least \(T_j\)” with the state “books added so far,” effectively reducing two complex conditions to a single condition (dimension reduction).

Algorithm

The processing is performed in the following steps:

1. Data Preparation and Sorting

   • Sort the book data in descending order of page count \(D_i\).
   • Sort the query data in descending order of the page count lower bound \(T_j\). At this time, since we need to output answers in the original order, we also store the original query index \(j\) alongside each query.

2. Data Structure Initialization

   • Prepare a BIT (Fenwick Tree) that uses shelf numbers as indices and manages the number of books on each shelf. We start from a state where no books have been placed (all zeros).

3. Query Processing

   • Process queries in order from the largest page count lower bound \(T_j\).
   • If there are remaining books with page count at least \(T_j\) for the current query, add those books to the BIT (increment by \(+1\) at the shelf \(S_i\) where the book is located).
   • After all additions are done, use the BIT to compute the range sum over \([L_j, R_j]\). This gives the count \(C_j\) of books satisfying the conditions.
   • Compute \(\max(C_j - K, 0)\) as the answer and store it at the position corresponding to the original query index \(j\).

4. Output Results

   • Output the stored answers in order.

Concrete Example

Suppose there are 3 books: (page count, shelf number) = (500, 2), (300, 4), (100, 3), and the query is (at least 200 pages, shelves 2 to 4).

• Since we add books with at least 200 pages to the BIT, the 500-page book (shelf 2) and the 300-page book (shelf 4) are added.
• At this point, the BIT has 1 book on shelf 2 and 1 book on shelf 4.
• Finally, computing the range sum for shelves 2 to 4, we find the total is 2 books.

Complexity

• Time Complexity: \(O(M \log M + Q \log Q + (M + Q) \log N)\)
  • Sorting books and queries takes \(O(M \log M + Q \log Q)\).
  • Each book is added to the BIT exactly once, so updates take \(O(M \log N)\) in total.
  • For each query, we retrieve a range sum from the BIT, so responses take \(O(Q \log N)\) in total.
  • Overall, this is very fast and easily fits within the time limit.
• Space Complexity: \(O(N + M + Q)\)
  • The BIT array uses \(O(N)\), and storing books and queries uses \(O(M + Q)\) memory.

Implementation Notes

• Preserving Original Indices: Since sorting queries scrambles the original order, it is important to include the original index j in the tuple as (T_j, L_j, R_j, j) at input time.

• Fast I/O: In competitive programming, when reading a large amount of input in Python, using sys.stdin.read().split() allows for very fast input reading.

• BIT Range Sum: The sum over the range \([L, R]\) is computed as (sum from 1 to R) - (sum from 1 to L-1). Implementing the BIT as 1-indexed (indices starting from 1) allows for clean bit operations.

  Source Code

import sys

def solve():
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    N = int(input_data[0])
    M = int(input_data[1])
    Q = int(input_data[2])
    K = int(input_data[3])
    
    idx = 4
    books = []
    for _ in range(M):
        S_i = int(input_data[idx])
        D_i = int(input_data[idx+1])
        books.append((D_i, S_i))
        idx += 2
        
    queries = []
    for j in range(Q):
        L_j = int(input_data[idx])
        R_j = int(input_data[idx+1])
        T_j = int(input_data[idx+2])
        queries.append((T_j, L_j, R_j, j))
        idx += 3
        
    books.sort(key=lambda x: x[0], reverse=True)
    queries.sort(key=lambda x: x[0], reverse=True)
    
    ans = [0] * Q
    
    tree = [0] * (N + 1)
    def add(i, delta):
        while i <= N:
            tree[i] += delta
            i += i & (-i)
            
    def query(i):
        s = 0
        while i > 0:
            s += tree[i]
            i -= i & (-i)
        return s

    book_idx = 0
    for T_j, L_j, R_j, j in queries:
        while book_idx < M and books[book_idx][0] >= T_j:
            add(books[book_idx][1], 1)
            book_idx += 1
        
        c = query(R_j) - query(L_j - 1)
        ans[j] = c - K if c > K else 0
        
    print('\n'.join(map(str, ans)))

if __name__ == '__main__':
    solve()

This editorial was generated by gemini-3.1-pro-thinking.