概要

各問い合わせ \((L,R,T)\) について、「区間 \([L,R]\) にある本のうち返却予定日 \(D_i \le T\) を満たす本の数 \(c\)」を数え、\(c \le K\) なら \(c\)、超えるなら \(-1\) を出力します。

考察

本 \(i\) が日付 \(T\) に書架にある条件は \(D_i \le T\) です。したがって各問い合わせは - 配列 \(D\) に対して - 条件 \(D_i \le T\) を満たす要素が - インデックス区間 \([L,R]\) にいくつあるか

という 「しきい値つき区間個数クエリ」 になっています。

素朴に各問い合わせごとに \(i=L..R\) を走査すると、最悪で \(O(NQ)\)（\(10^{10}\)）となり間に合いません。また、\(T\) が問い合わせごとに異なるため、単純な前計算（例えば日付ごとの累積）も日付が最大 \(10^9\) で不可能です。

重要な気づきは次の2点です： 1. 条件 \(D_i \le T\) は、\(T\) が増えるほど「書架にある本」が単調に増える。 2. 問い合わせを \(T\) の昇順に処理すれば、「新たに書架に戻った本」だけを追加していけばよい。

つまり、オフライン処理（クエリをソートしてまとめて処理） によって高速化できます。

アルゴリズム

方針（オフライン + BIT）

1. 本を \((D_i, i)\) の形で持ち、\(D_i\) の昇順にソートする。
2. 問い合わせを \((T_j, L_j, R_j, j)\) の形で持ち、\(T_j\) の昇順にソートする（\(j\) は元の順番に戻すため）。
3. Fenwick Tree（BIT）を用意し、BIT の位置 \(i\) には「本 \(i\) がすでに書架にあるなら 1、なければ 0」を入れる。
4. ソート済みクエリを小さい \(T\) から順に見ていき、現在の \(T\) 以下の \(D_i\) を持つ本をすべて BIT に追加する（\(add(i,1)\)）。
   • これにより、BIT は「日付 \(T\) 時点で書架にある本の位置」を表すようになる。
5. 問い合わせ \((L,R,T)\) の答え \(c\) は、BIT の区間和 \(sum(R)-sum(L-1)\) で得られる。
6. \(c \le K\) なら \(c\)、そうでなければ \(-1\) を記録し、最後に元の順で出力する。

具体例イメージ

例えば \(D=[3,1,4,1,5]\) のとき、\(T=1\) なら \(D_i \le 1\) の位置（2,4）だけが 1 になります。
次に \(T=3\) なら位置 1 も追加され、(1,2,4) が 1 になります。
この「\(T\) を増やすと 1 が増える」性質を、ソート + 追加処理で効率よく実現しています。

計算量

• 時間計算量:
  ソートが \(O(N\log N + Q\log Q)\)、各本の追加が合計 \(N\) 回で \(O(N\log N)\)、各問い合わせの区間和が \(Q\) 回で \(O(Q\log N)\)。
  よって全体で \(O((N+Q)\log N)\)（同程度の \(\log\) とみなしてよい）。
• 空間計算量: \(O(N+Q)\)（本・問い合わせ配列、BIT、答え配列）

実装のポイント

• BIT は 1-indexed なので、本の位置 \(i\) はそのまま \(1..N\) で管理します（コードでは \((D[i], i+1)\)）。

• 問い合わせはソートで順番が変わるため、元の問い合わせ番号 \(j\) を一緒に持ち、ans[j] に入れて最後に順に出力します。

• 「本の追加」はポインタ p を使い、books[p].date <= T の間だけ進めることで、各本をちょうど1回だけ BIT に追加します。これが高速化の肝です。

  ソースコード

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()

この解説は gpt-5.2-high によって生成されました。