概要

本棚の特定の範囲 \([L, R]\) にある本のうち、指定された日付 \(T\) までに返却されている本の冊数を数え、その数が \(K\) 以下なら冊数を、そうでなければ \(-1\) を出力する問題です。

考察

この問題は、各本 \(i\) について「位置 \(i\)」と「返却日 \(D_i\)」という2つのパラメータがあり、クエリごとに「位置が \([L, R]\) の範囲内」かつ「返却日が \(T\) 以下」という2つの条件を満たす要素を数える、2次元の領域クエリの問題と捉えることができます。

素朴なアプローチ

各クエリに対して、範囲 \([L, R]\) の本を一つずつ確認し、返却日が \(T\) 以下であるか判定すると、最悪の場合 \(O(N \times Q)\) の計算量となります。\(N, Q \leq 10^5\) であるため、計算回数は最大 \(10^{10}\) 回に達し、実行時間制限に間に合いません。

効率的なアプローチ（オフライン処理）

クエリが与えられた順に答える必要がない（オンラインである必要がない）ことに注目します。 日付 \(T\) が小さい順にクエリを処理することにすれば、本も返却日 \(D_i\) が早い順に「書架に追加」していくだけで済みます。

1. 本を返却日 \(D_i\) の昇順にソートします。
2. クエリを日付 \(T_j\) の昇順にソートします。
3. 日付の早いクエリから順に見ていき、そのクエリの日付 \(T_j\) までに返却される本をすべてデータ構造（フェニック木など）に追加します。
4. データ構造を用いて、範囲 \([L_j, R_j]\) に含まれる本の総数を取得します。

このように「時間を進めながら状態を更新していく」手法は、平面走査（スイープライン）やオフラインクエリ処理と呼ばれます。

アルゴリズム

以下の手順で解を求めます。

1. 準備:
   • 各本の情報を (返却日, 本の番号) のペアとしてリストに格納し、返却日の昇順にソートします。
   • 各クエリの情報を (日付, L, R, 元のインデックス) のタプルとしてリストに格納し、日付の昇順にソートします。
2. フェニック木（Binary Indexed Tree: BIT）の初期化:
   • 長さ \(N+1\) の BIT を用意します。これは「現在書架にある本」の位置に \(1\) を立て、範囲和を高速に計算するために使います。
3. クエリの処理:
   • ソートしたクエリを順に処理します。
   • 現在のクエリの日付 \(T_j\) 以下の返却日を持つ本を、未追加のものから順にすべて BIT に追加します（位置 \(i\) に \(+1\) する）。
   • BIT を用いて、範囲 \([L_j, R_j]\) の合計値（sum(R_j) - sum(L_j - 1)）を求めます。これが書架にある本の冊数 \(c_j\) です。
   • \(c_j \leq K\) なら \(c_j\) を、そうでなければ \(-1\) を答えとして記録します。
4. 出力:
   • すべてのクエリを処理した後、元のインデックス順に答えを出力します。

計算量

• 時間計算量: \(O((N + Q) \log N + Q \log Q)\)
  • 本とクエリのソートに \(O(N \log N + Q \log Q)\) かかります。
  • BIT への追加（\(N\) 回）と範囲和の取得（\(Q\) 回）にそれぞれ \(O(\log N)\) かかるため、全体で \(O((N + Q) \log N)\) です。
• 空間計算量: \(O(N + Q)\)
  • 本、クエリ、BIT、結果を格納する配列に \(O(N + Q)\) のメモリを使用します。

実装のポイント

• 高速な入出力: \(N, Q\) が大きいため、Python では sys.stdin.read().split() や sys.stdout.write() を使用することで入出力のボトルネックを回避できます。

• 1-indexed: フェニック木は通常 1-indexed で実装するため、本の番号（\(1\) 〜 \(N\)）をそのままインデックスとして利用できます。

• オフライン処理の復元: クエリをソートして処理するため、最後に元の順番で出力できるよう、ソート前に元のインデックスを保持しておく必要があります。

  ソースコード

import sys

def solve():
    # Read all input data and split into strings
    raw_data = sys.stdin.read().split()
    if not raw_data:
        return
    
    # Convert all strings to integers efficiently
    data = list(map(int, raw_data))
    
    # N: Number of books, K: Cart capacity, Q: Number of queries
    N = data[0]
    K = data[1]
    Q = data[2]
    
    # Store books as tuples of (return_date, shelf_index)
    # Book i's return date D_i is at data[3 + (i-1)]
    books = []
    for i in range(N):
        books.append((data[3 + i], i + 1))
    
    # Sort books by their return date for offline processing
    books.sort(key=lambda x: x[0])
    
    # Store queries as tuples of (T, L, R, original_index)
    # Queries start from data[3 + N]
    queries = []
    offset = 3 + N
    for j in range(Q):
        L = data[offset + 3*j]
        R = data[offset + 3*j + 1]
        T = data[offset + 3*j + 2]
        queries.append((T, L, R, j))
    
    # Sort queries by their date T to process chronologically
    queries.sort(key=lambda x: x[0])
    
    # Fenwick Tree (Binary Indexed Tree) to count books on the shelf
    # bit[i] stores counts of books returned in specific index ranges
    bit = [0] * (N + 1)
    results = [0] * Q
    book_ptr = 0
    
    # Process queries offline: as T increases, more books are returned to the shelf
    for T, L, R, q_idx in queries:
        # Add all books returned on or before date T into the BIT
        while book_ptr < N and books[book_ptr][0] <= T:
            idx = books[book_ptr][1]
            while idx <= N:
                bit[idx] += 1
                idx += idx & (-idx)
            book_ptr += 1
        
        # Calculate the number of books in shelf range [L, R] using BIT
        # prefix_sum(R)
        s_r = 0
        idx_r = R
        while idx_r > 0:
            s_r += bit[idx_r]
            idx_r -= idx_r & (-idx_r)
        
        # prefix_sum(L-1)
        s_l = 0
        idx_l = L - 1
        while idx_l > 0:
            s_l += bit[idx_l]
            idx_l -= idx_l & (-idx_l)
        
        # Total books returned in interval [L, R] by date T
        count = s_r - s_l
        
        # Compare count with cart capacity K
        if count <= K:
            results[q_idx] = count
        else:
            results[q_idx] = -1
    
    # Output all results in the original query order
    sys.stdout.write('\n'.join(map(str, results)) + '\n')

if __name__ == '__main__':
    solve()

この解説は gemini-3-flash-thinking によって生成されました。