概要

指定された棚の区間 \([L_j, R_j]\) にあり、かつページ数が \(T_j\) 以上である本の冊数 \(C_j\) を数え、\(\max(C_j - K, 0)\) を求める問題です。

考察

各クエリに対して、毎回すべての本を調べて条件を満たすか判定する素朴な方法（全探索）を考えてみましょう。この場合、1回のクエリにつき \(M\) 冊の本を調べるため、全体の計算量は \(O(MQ)\) となります。制約は \(M, Q \leq 10^5\) なので、最悪の場合 \(10^{10}\) 回程度の計算が必要になり、実行時間制限（TLE）に引っかかってしまいます。

この問題を高速に解くための鍵は、「条件が2つ（棚番号とページ数）あること」 と 「クエリが事前にすべて与えられていること（オフライン）」 にあります。

もし「ページ数が \(T_j\) 以上」という条件がなく、「棚の区間 \([L_j, R_j]\) にある本の数」だけを求める問題であれば、Fenwick Tree（Binary Indexed Tree, BIT） などのデータ構造を使って、1回のクエリを \(O(\log N)\) で高速に処理できます。

そこで、ページ数の条件を上手く扱うために、本とクエリをページ数の降順（大きい順）にソート して処理する手法（クエリ先読み・イベントソート）を使います。 大きい順に処理していくことで、「ページ数が \(T_j\) 以上」という条件を「これまでに追加した本」という状態に置き換えることができ、複雑な2つの条件を1つの条件に減らす（次元圧縮する）ことができます。

アルゴリズム

以下の手順で処理を行います。

1. データの準備とソート

   • 本のデータを「ページ数 \(D_i\) の降順」にソートします。
   • クエリのデータを「ページ数の下限 \(T_j\) の降順」にソートします。このとき、出力時に元の順番で答えを返す必要があるため、元のクエリ番号 \(j\) も一緒に保持しておきます。

2. データ構造の初期化

   • 棚の番号をインデックスとし、各棚にある本の冊数を管理する BIT（Fenwick Tree）を用意します。最初は本が1冊も置かれていない状態（すべて0）から始めます。

3. クエリの処理

   • ページ数下限 \(T_j\) が大きいクエリから順番に処理します。
   • 現在のクエリの \(T_j\) 以上のページ数を持つ本がまだ残っていれば、それらの本を BIT に追加します（本が置かれている棚 \(S_i\) の冊数を \(+1\) します）。
   • 追加が終わったら、BIT を使って区間 \([L_j, R_j]\) の和を求めます。これが条件を満たす本の冊数 \(C_j\) になります。
   • 答えとして \(\max(C_j - K, 0)\) を計算し、元のクエリ番号 \(j\) の位置に保存します。

4. 結果の出力

   • 保存した答えを順番に出力します。

具体例

本が (ページ数, 棚番号) = (500, 2), (300, 4), (100, 3) の3冊あり、 クエリが (ページ数200以上, 棚2〜4) だとします。

• ページ数200以上の本をBITに追加するので、500ページの本（棚2）と300ページの本（棚4）が追加されます。
• この時点で BIT は棚2に1冊、棚4に1冊という状態になります。
• 最後に棚2〜4の区間和を計算すると、合計2冊であることがわかります。

計算量

• 時間計算量: \(O(M \log M + Q \log Q + (M + Q) \log N)\)
  • 本とクエリのソートに \(O(M \log M + Q \log Q)\) かかります。
  • 各本は BIT に1回だけ追加されるため、更新に合計 \(O(M \log N)\) かかります。
  • 各クエリに対して BIT の区間和を取得するため、応答に合計 \(O(Q \log N)\) かかります。
  • 全体として非常に高速であり、制限時間内に余裕で間に合います。
• 空間計算量: \(O(N + M + Q)\)
  • BITの配列に \(O(N)\)、本とクエリの保持に \(O(M + Q)\) のメモリを使用します。

実装のポイント

• 元のインデックスの保持: クエリをソートすると元の順番がバラバラになってしまうため、入力の段階で (T_j, L_j, R_j, j) のように元のインデックス j をタプルに含めておくことが重要です。

• 高速な入出力: 競技プログラミングにおいて、Pythonで大量の入力を受け取る場合は sys.stdin.read().split() を使うと非常に高速に読み込むことができます。

• BITの区間和: 区間 \([L, R]\) の和は、(1からRまでの和) - (1からL-1までの和) として計算します。BITは1-indexed（インデックスが1から始まる）で実装するとビット演算が綺麗に書けます。

  ソースコード

import sys

def solve():
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    N = int(input_data[0])
    M = int(input_data[1])
    Q = int(input_data[2])
    K = int(input_data[3])
    
    idx = 4
    books = []
    for _ in range(M):
        S_i = int(input_data[idx])
        D_i = int(input_data[idx+1])
        books.append((D_i, S_i))
        idx += 2
        
    queries = []
    for j in range(Q):
        L_j = int(input_data[idx])
        R_j = int(input_data[idx+1])
        T_j = int(input_data[idx+2])
        queries.append((T_j, L_j, R_j, j))
        idx += 3
        
    books.sort(key=lambda x: x[0], reverse=True)
    queries.sort(key=lambda x: x[0], reverse=True)
    
    ans = [0] * Q
    
    tree = [0] * (N + 1)
    def add(i, delta):
        while i <= N:
            tree[i] += delta
            i += i & (-i)
            
    def query(i):
        s = 0
        while i > 0:
            s += tree[i]
            i -= i & (-i)
        return s

    book_idx = 0
    for T_j, L_j, R_j, j in queries:
        while book_idx < M and books[book_idx][0] >= T_j:
            add(books[book_idx][1], 1)
            book_idx += 1
        
        c = query(R_j) - query(L_j - 1)
        ans[j] = c - K if c > K else 0
        
    print('\n'.join(map(str, ans)))

if __name__ == '__main__':
    solve()

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