Overview

This problem requires processing book return dates and queries to determine whether the number of returned books within a specified range is within the capacity of a lending cart.

Analysis

For each query, we need to find the count \(c_j\) of books within the range \([L_j, R_j]\) that satisfy \(D_i \leq T_j\). A naive approach of checking each book in the range for every query takes \(O(NQ)\) time, which exceeds the time limit given the constraints \(N, Q \leq 10^5\).

For efficient processing, the following observations are key: - Books with earlier return dates \(D_i\) are returned to the shelves first - The larger the query date \(T_j\), the more books have been returned - By processing queries in ascending order of \(T_j\), we can incrementally add returned books

Algorithm

1. Preprocessing:

   • Sort books in ascending order of return date \(D_i\) and record the correspondence with their indices
   • Sort queries in ascending order of date \(T_j\)

2. Using a Fenwick Tree (BIT):

   • Prepare a Fenwick tree of size \(N\) to manage the state of books on the shelves
   • Add 1 at the position corresponding to each returned book

3. Query Processing:

   • Process queries in ascending order of \(T_j\)
   • Add books that are returned by the current \(T_j\) to the Fenwick tree
   • Use a range query on the Fenwick tree to obtain the number of returned books within \([L_j, R_j]\)
   • If the obtained value \(c_j\) is at most \(K\), output \(c_j\); otherwise, output \(-1\)

Complexity

• Time complexity: \(O((N + Q) \log N)\)
  • Sorting books: \(O(N \log N)\)
  • Sorting queries: \(O(Q \log Q)\)
  • Fenwick tree updates and queries: \(O(N \log N + Q \log N)\)
• Space complexity: \(O(N + Q)\)

Implementation Notes

• Save the original index of each query so that results can be output in the original order after sorting

• When multiple queries share the same date \(T_j\), handle the events collectively

• Fenwick trees are typically implemented with 1-indexed arrays; if using 0-indexed implementation, be careful with index adjustments

  Source Code

import sys
import bisect

def main():
    data = sys.stdin.read().split()
    it = iter(data)
    N = int(next(it)); K = int(next(it)); Q = int(next(it))
    D = [int(next(it)) for _ in range(N)]
    queries = []
    for i in range(Q):
        L = int(next(it)); R = int(next(it)); T = int(next(it))
        queries.append((T, L-1, R-1, i))
    
    indices = list(range(N))
    indices.sort(key=lambda i: D[i])
    sorted_D = [D[i] for i in indices]
    
    ans = [-1] * Q
    queries.sort(key=lambda x: x[0])
    
    from collections import defaultdict
    events = defaultdict(list)
    for idx, (T, L, R, q_idx) in enumerate(queries):
        events[T].append((L, R, q_idx, idx))
    
    unique_T = sorted(set([T for T, _, _, _ in queries]))
    T_to_idx = {t: i for i, t in enumerate(unique_T)}
    
    class Fenw:
        def __init__(self, n):
            self.n = n
            self.tree = [0] * (n+1)
        
        def update(self, index, delta):
            i = index + 1
            while i <= self.n:
                self.tree[i] += delta
                i += i & -i
        
        def query(self, index):
            s = 0
            i = index + 1
            while i > 0:
                s += self.tree[i]
                i -= i & -i
            return s
        
        def range_query(self, l, r):
            if l > r:
                return 0
            return self.query(r) - self.query(l-1)
    
    fenw = Fenw(N)
    ptr = 0
    res_list = [0] * len(queries)
    
    for t_val in unique_T:
        while ptr < N and sorted_D[ptr] <= t_val:
            pos = indices[ptr]
            fenw.update(pos, 1)
            ptr += 1
        
        for (L, R, q_idx, orig_idx) in events[t_val]:
            count = fenw.range_query(L, R)
            if count <= K:
                res_list[orig_idx] = count
            else:
                res_list[orig_idx] = -1
    
    for i in range(len(queries)):
        ans[queries[i][3]] = res_list[i]
    
    for a in ans:
        print(a)

if __name__ == "__main__":
    main()

This editorial was generated by deepseekv3.