概要

本の返却日と問い合わせを処理し、指定された区間内で返却済みの本の冊数が貸出カートの容量以内かを判定する問題です。

考察

各問い合わせでは、区間 \([L_j, R_j]\) 内で \(D_i \leq T_j\) を満たす本の数 \(c_j\) を求める必要があります。素朴に各問い合わせごとに区間内の本を1つずつチェックすると、\(O(NQ)\) 時間かかり、制約条件 \(N, Q \leq 10^5\) では実行時間が超過します。

効率的に処理するためには、以下の観察が重要です： - 返却日 \(D_i\) が早い本から順に書架に戻る - 問い合わせの日付 \(T_j\) が大きいほど、多くの本が返却済みになる - 問い合わせを \(T_j\) の昇順に処理することで、返却済みの本を順次追加できる

アルゴリズム

1. 前処理:

   • 本を返却日 \(D_i\) の昇順にソートし、インデックスと対応を記録する
   • 問い合わせを日付 \(T_j\) の昇順にソートする

2. フェンウィック木（BIT）の使用:

   • 書架にある本の状態を管理するため、サイズ \(N\) のフェンウィック木を用意する
   • 返却済みの本に対応する位置に1を加算する

3. 問い合わせ処理:

   • \(T_j\) の小さい問い合わせから順に処理する
   • 現在の \(T_j\) までに返却される本をフェンウィック木に追加する
   • フェンウィック木の区間クエリで \([L_j, R_j]\) 内の返却済み本の数を取得する
   • 取得した値 \(c_j\) が \(K\) 以下なら \(c_j\)、そうでなければ \(-1\) を出力する

計算量

• 時間計算量: \(O((N + Q) \log N)\)
  • 本のソート: \(O(N \log N)\)
  • 問い合わせのソート: \(O(Q \log Q)\)
  • フェンウィック木の更新とクエリ: \(O(N \log N + Q \log N)\)
• 空間計算量: \(O(N + Q)\)

実装のポイント

• 問い合わせを元の出力順序を保持しながらソートするため、インデックスを保存する

• 同じ日付 \(T_j\) の問い合わせが複数ある場合を考慮し、イベントをまとめて処理する

• フェンウィック木は1-indexedで実装するのが一般的だが、0-indexedで実装する場合はインデックス調整に注意する

  ソースコード

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

この解説は deepseekv3 によって生成されました。