Overview

This problem asks us to efficiently count the number of books whose shelf number falls within a specified range and whose page count is at least a specified value. For each query, we output the answer minus \(K\) (or \(0\) if the result is negative).

Analysis

Naive Approach and Its Issues

The simplest method is, for each query, to scan all books on shelves from \(L_j\) to \(R_j\) and check one by one whether the page count is at least \(T_j\). However, in the worst case a single query may examine all \(M\) books, and across \(Q\) queries the total cost is \(O(MQ)\). When both \(M\) and \(Q\) are \(10^5\), this becomes \(10^{10}\), which is too slow for the time limit.

Key Insight

This problem filters based on two-dimensional conditions:

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

Range queries on shelf numbers are a form that segment trees handle well. Furthermore, if each node maintains a sorted list of page counts, we can efficiently determine “how many books have at least \(T\) pages” using binary search. This combination is known as a Merge Sort Tree.

Algorithm

What is a Merge Sort Tree?

It is a data structure where each node of a segment tree stores a sorted list of all values belonging to the interval that node is responsible for.

Construction

1. Set the segment tree size to the smallest power of 2 that is at least \(N\).
2. Each leaf node corresponds to one shelf and holds a sorted list of the page counts of books on that shelf.
3. Internal nodes are built by merging the lists of their two children (just like in merge sort).

For example, if shelf 1 has [100, 300] and shelf 2 has [200], the parent node managing these shelves stores [100, 200, 300].

Query Processing

To find the number of books with page count at least \(T\) in the shelf range \([L, R]\):

1. Decompose the interval \([L, R]\) into \(O(\log N)\) nodes on the segment tree.
2. For each node’s sorted list, use bisect_left to find the number of elements at least \(T\) in \(O(\log M)\).
3. Sum these up to get \(C_j\), and output \(\max(C_j - K, 0)\).

Concrete Example

Suppose there are 4 shelves with books arranged as follows: - Shelf 1: page counts [50, 200] - Shelf 2: page counts [300] - Shelf 3: page counts [100, 400] - Shelf 4: page counts [150]

For the query \(L=1, R=3, T=150\), among the books on shelves 1–3, those with at least 150 pages are [200, 300, 400] — 3 books. If \(K=1\), the output is \(\max(3-1, 0) = 2\).

Complexity

• Construction time complexity: \(O(M \log N)\) — each element appears in \(O(\log N)\) nodes of the tree, and the total merge cost is \(O(M \log N)\)
• Query time complexity: \(O(\log^2 N)\) per query — binary search \(O(\log M)\) at each of the \(O(\log N)\) nodes
• Overall time complexity: \(O(M \log N + Q \log^2 N)\)
• Space complexity: \(O(M \log N)\) — each element is stored in \(O(\log N)\) nodes

Implementation Notes

• The segment tree size should be a power of 2 that is at least \(N\). Shelf numbers (1-indexed) are directly converted to leaf indices (size + s - 1).

• For building internal nodes, manual merging has better constant factors than Python’s extend.

• Queries convert to half-open intervals \([lo, hi)\) and use the standard segment tree traversal that picks up boundary nodes via lo & 1 and hi & 1.

• bisect_left(arr, T) returns the first position of an element at least \(T\) in a sorted list, so len(arr) - bisect_left(arr, T) gives the number of elements at least \(T\).

• Read input all at once using sys.stdin.buffer.read() and write output collectively using '\n'.join(...) for faster I/O.

  Source Code

import sys
from bisect import bisect_left

def main():
    input_data = sys.stdin.buffer.read().split()
    idx = 0
    N = int(input_data[idx]); idx += 1
    M = int(input_data[idx]); idx += 1
    Q = int(input_data[idx]); idx += 1
    K = int(input_data[idx]); idx += 1
    
    # Merge sort tree: for each node in a segment tree, store sorted list of page counts
    # Segment tree size
    size = 1
    while size < N:
        size *= 2
    
    # Each leaf corresponds to a shelf (1-indexed shelf -> 0-indexed leaf)
    tree = [[] for _ in range(2 * size)]
    
    for i in range(M):
        s = int(input_data[idx]); idx += 1
        d = int(input_data[idx]); idx += 1
        tree[size + s - 1].append(d)
    
    # Sort leaves
    for i in range(size, 2 * size):
        tree[i].sort()
    
    # Build internal nodes by merging children
    for i in range(size - 1, 0, -1):
        # Merge two sorted lists
        left = tree[2 * i]
        right = tree[2 * i + 1]
        merged = []
        li, ri = 0, 0
        ll, rl = len(left), len(right)
        while li < ll and ri < rl:
            if left[li] <= right[ri]:
                merged.append(left[li])
                li += 1
            else:
                merged.append(right[ri])
                ri += 1
        if li < ll:
            merged.extend(left[li:])
        if ri < rl:
            merged.extend(right[ri:])
        tree[i] = merged
    
    # Query: count of elements >= T in shelf range [L, R] (1-indexed)
    # In segment tree, shelf s is at index (size + s - 1)
    # We query range [L-1, R-1] in 0-indexed leaves, which is [size+L-1, size+R-1] in tree
    
    out = []
    for j in range(Q):
        L = int(input_data[idx]); idx += 1
        R = int(input_data[idx]); idx += 1
        T = int(input_data[idx]); idx += 1
        
        # Count elements >= T in range [L, R]
        count = 0
        lo = size + L - 1  # left boundary (inclusive)
        hi = size + R - 1  # right boundary (inclusive)
        lo_node = lo
        hi_node = hi
        
        # Convert to half-open: [lo, hi+1)
        lo = lo
        hi = hi + 1
        
        while lo < hi:
            if lo & 1:
                # lo is a right child, include it
                arr = tree[lo]
                count += len(arr) - bisect_left(arr, T)
                lo += 1
            if hi & 1:
                hi -= 1
                arr = tree[hi]
                count += len(arr) - bisect_left(arr, T)
            lo >>= 1
            hi >>= 1
        
        result = max(count - K, 0)
        out.append(str(result))
    
    sys.stdout.write('\n'.join(out) + '\n')

main()

---

This editorial was generated by claude4.6opus-thinking.