Overview

For each query \((L,R,T)\), count the number \(c\) of books in the range \([L,R]\) whose return date satisfies \(D_i \le T\). If \(c \le K\), output \(c\); otherwise, output \(-1\).

Analysis

The condition for book \(i\) to be on the shelf at date \(T\) is \(D_i \le T\). Therefore, each query becomes: - Given the array \(D\), - count the number of elements satisfying \(D_i \le T\) - within the index range \([L,R]\).

This is a “threshold range counting query”.

Naively scanning \(i=L..R\) for each query results in \(O(NQ)\) (\(10^{10}\)) in the worst case, which is too slow. Additionally, since \(T\) differs for each query, simple precomputation (e.g., cumulative sums per date) is also impossible because dates can be up to \(10^9\).

The key observations are: 1. For the condition \(D_i \le T\), as \(T\) increases, the set of “books on the shelf” monotonically grows. 2. If we process queries in ascending order of \(T\), we only need to incrementally add “books that have newly returned to the shelf.”

In other words, we can speed things up using offline processing (sorting queries and processing them together).

Algorithm

Approach (Offline + BIT)

1. Store books as \((D_i, i)\) and sort them in ascending order of \(D_i\).
2. Store queries as \((T_j, L_j, R_j, j)\) and sort them in ascending order of \(T_j\) (\(j\) is kept to restore the original order).
3. Prepare a Fenwick Tree (BIT), where position \(i\) in the BIT holds 1 if book \(i\) is already on the shelf, and 0 otherwise.
4. Process the sorted queries from smallest \(T\) onward. For each query, add all books with \(D_i\) less than or equal to the current \(T\) to the BIT (\(add(i,1)\)).
   • This way, the BIT represents “the positions of books on the shelf at date \(T\).”
5. The answer \(c\) for query \((L,R,T)\) is obtained as the range sum \(sum(R)-sum(L-1)\) in the BIT.
6. If \(c \le K\), record \(c\); otherwise, record \(-1\). Finally, output the results in the original order.

Concrete Example

For example, when \(D=[3,1,4,1,5]\) and \(T=1\), only positions (2,4) where \(D_i \le 1\) become 1.
Next, when \(T=3\), position 1 is also added, so (1,2,4) become 1.
This property of “more 1s appearing as \(T\) increases” is efficiently realized through sorting + incremental addition.

Complexity

• Time complexity:
  Sorting takes \(O(N\log N + Q\log Q)\), adding each book totals \(N\) times for \(O(N\log N)\), and each query’s range sum totals \(Q\) times for \(O(Q\log N)\).
  Overall: \(O((N+Q)\log N)\) (treating the logarithmic factors as equivalent).
• Space complexity: \(O(N+Q)\) (arrays for books, queries, BIT, and answers)

Implementation Notes

• Since the BIT is 1-indexed, book positions \(i\) are managed directly as \(1..N\) (in the code, stored as \((D[i], i+1)\)).

• Because sorting changes the order of queries, we keep the original query index \(j\) alongside each query, store results in ans[j], and output them in order at the end.

• “Adding books” uses a pointer p, advancing only while books[p].date <= T, so each book is added to the BIT exactly once. This is the key to the speedup.

  Source Code

import sys

class BIT:
    __slots__ = ("n", "bit")
    def __init__(self, n):
        self.n = n
        self.bit = [0] * (n + 1)

    def add(self, i, v):
        n = self.n
        bit = self.bit
        while i <= n:
            bit[i] += v
            i += i & -i

    def sum(self, i):
        s = 0
        bit = self.bit
        while i > 0:
            s += bit[i]
            i -= i & -i
        return s

    def range_sum(self, l, r):
        return self.sum(r) - self.sum(l - 1)

def main():
    input = sys.stdin.readline
    N, K, Q = map(int, input().split())
    D = list(map(int, input().split()))

    books = sorted([(D[i], i + 1) for i in range(N)])  # (date, index)

    queries = []
    for j in range(Q):
        L, R, T = map(int, input().split())
        queries.append((T, L, R, j))
    queries.sort()

    bit = BIT(N)
    ans = [0] * Q
    p = 0
    for T, L, R, qi in queries:
        while p < N and books[p][0] <= T:
            _, idx = books[p]
            bit.add(idx, 1)
            p += 1
        c = bit.range_sum(L, R)
        ans[qi] = c if c <= K else -1

    sys.stdout.write("\n".join(map(str, ans)))

if __name__ == "__main__":
    main()

This editorial was generated by gpt-5.2-high.