Overview

This problem requires efficiently counting how many books within the range \([L, R]\) have a return due date \(D_i\) that is less than or equal to a specified date \(T\). If the count exceeds \(K\), output \(-1\).

Analysis

Essence of the Problem

Each query reduces to a two-dimensional counting query: “In the subarray \(D[L..R]\), how many elements have a value at most \(T\)?”

Issues with the Naive Approach

Naively scanning from \(L\) to \(R\) for each query costs \(O(N)\) per query, resulting in \(O(NQ)\) total. When \(N, Q \leq 10^5\), this requires up to \(10^{10}\) operations, causing TLE.

Strategy for the Solution

To efficiently answer “how many elements in a range are at most a given value,” a Merge Sort Tree is effective. This is a data structure based on a segment tree where each node stores the elements of its corresponding range as a sorted array. By using binary search during queries, we can count elements efficiently.

Algorithm

Building the Merge Sort Tree

1. Build a segment tree for an array \(D\) of size \(N\). Leaf node \(i\) stores \([D_i]\) (a list with a single element).
2. Each internal node stores the merged result of the sorted arrays from its left and right children. This is the same operation as in merge sort.

For example, if \(D = [5, 3, 8, 1]\):

        [1, 3, 5, 8]       ← Root (entire range)
       /            \
   [3, 5]          [1, 8]   ← Internal nodes
   /    \           /    \
 [5]   [3]        [8]   [1]  ← Leaf nodes

Processing Queries

To find the number of elements satisfying \(D_i \leq T\) in the range \([L, R]\):

1. Decompose the range \([L, R]\) into \(O(\log N)\) nodes on the segment tree.
2. For each node’s sorted array, call bisect_right(array, T) to find the number of elements at most \(T\).
3. The sum of these counts is the answer \(c\).

Since bisect_right uses binary search, it takes \(O(\log N)\) per node, and there are \(O(\log N)\) nodes, so each query takes \(O(\log^2 N)\).

Final Decision

If the computed \(c\) is at most \(K\), output \(c\); if \(c\) exceeds \(K\), output \(-1\).

Complexity

• Build time complexity: \(O(N \log N)\) (each element participates in merges \(O(\log N)\) times, once per level of the segment tree)
• Per-query time complexity: \(O(\log^2 N)\) (\(O(\log N)\) nodes × binary search \(O(\log N)\) per node)
• Overall time complexity: \(O(N \log N + Q \log^2 N)\)
• Space complexity: \(O(N \log N)\) (total number of elements in sorted arrays across the entire segment tree)

When \(N = Q = 10^5\), \(\log_2 N \approx 17\), so this is sufficiently fast.

Implementation Notes

• The segment tree size is set to the smallest power of 2 that is at least \(N\), simplifying index calculations. Out-of-range leaves are filled with empty lists [].

• The merge operation uses a manual merge of two sorted lists instead of Python’s sorted, improving the constant factor.

• Input is read all at once using sys.stdin.buffer.read() for faster I/O.

• Since the book numbers in the problem are 1-indexed, we convert to 0-indexed by using L-1 and R-1 during queries.

  Source Code

import sys
from bisect import bisect_right

def main():
    input_data = sys.stdin.buffer.read().split()
    idx = 0
    N = int(input_data[idx]); idx += 1
    K = int(input_data[idx]); idx += 1
    Q = int(input_data[idx]); idx += 1
    
    D = [int(input_data[idx + i]) for i in range(N)]
    idx += N
    
    # Build a merge sort tree (persistent segment tree alternative)
    # For each node in a segment tree over [0, N-1], store sorted list of D values
    # Then for query [L, R] with threshold T, count elements <= T using bisect
    
    size = 1
    while size < N:
        size *= 2
    
    # Build merge sort tree
    tree = [None] * (2 * size)
    for i in range(N):
        tree[size + i] = [D[i]]
    for i in range(N, size):
        tree[size + i] = []
    
    for i in range(size - 1, 0, -1):
        # Merge two sorted lists
        left = tree[2 * i]
        right = tree[2 * i + 1]
        if not left:
            tree[i] = right
        elif not right:
            tree[i] = left
        else:
            # Merge
            merged = []
            a, b = 0, 0
            la, lb = len(left), len(right)
            while a < la and b < lb:
                if left[a] <= right[b]:
                    merged.append(left[a])
                    a += 1
                else:
                    merged.append(right[b])
                    b += 1
            if a < la:
                merged.extend(left[a:])
            else:
                merged.extend(right[b:])
            tree[i] = merged
    
    # Query: count elements <= T in D[L..R] (0-indexed)
    def query(l, r, T):
        # l, r are 0-indexed, inclusive
        res = 0
        l += size
        r += size + 1
        while l < r:
            if l & 1:
                res += bisect_right(tree[l], T)
                l += 1
            if r & 1:
                r -= 1
                res += bisect_right(tree[r], T)
            l >>= 1
            r >>= 1
        return res
    
    out = []
    for _ in range(Q):
        L = int(input_data[idx]); idx += 1
        R = int(input_data[idx]); idx += 1
        T = int(input_data[idx]); idx += 1
        
        c = query(L - 1, R - 1, T)
        if c > K:
            out.append("-1")
        else:
            out.append(str(c))
    
    sys.stdout.write("\n".join(out) + "\n")

main()

---

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