概要

棚番号の区間とページ数の下限を指定したクエリに対して、条件を満たす本の冊数から非負整数 \(K\) を引いた値（負の場合は0）を求める問題です。

考察

素朴なアプローチとして、各クエリごとに全ての本をチェックすると、計算量が \(O(Q \times M)\) となり、\(Q\) と \(M\) が最大 \(10^5\) なので \(10^{10}\) 回の操作が必要となり、時間内に実行できません。

重要な観察は、クエリをページ数の下限 \(T_j\) でソートすることで、効率的に処理できる点です。ページ数の大きい本から順にデータ構造に追加していき、各クエリでは「現在データ構造にある本のうち、棚番号が区間 \([L_j, R_j]\) 内にある本の数」を求めれば、これがまさにページ数が \(T_j\) 以上の本の冊数になります。

アルゴリズム

1. 前処理:

   • 本をページ数の降順でソート
   • クエリをページ数の下限 \(T_j\) の降順でソート

2. Fenwick Tree (BIT):

   • 棚番号をインデックスとするFenwick Treeを用意
   • ページ数の大きい本から順に、対応する棚番号の位置に1を加算

3. クエリ処理:

   • クエリを \(T_j\) の降順で処理
   • 現在のクエリの \(T_j\) 以上のページ数を持つ本を全てFenwick Treeに追加
   • Fenwick Treeで区間 \([L_j, R_j]\) の和を求め、\(max(和 - K, 0)\) を結果に格納

計算量

• 時間計算量: \(O((M + Q) \log N)\)
  • ソート: \(O(M \log M + Q \log Q)\)
  • Fenwick Treeの操作: 各本の追加と各クエリの処理が \(O(\log N)\)
• 空間計算量: \(O(N + M + Q)\)

実装のポイント

• 本とクエリを別々にソートする必要があります

• クエリは元の順序で出力するため、元のインデックスを保持しておきます

• Fenwick Treeは1-indexedで実装します

• ページ数が同じ本の処理順序は問題に影響しないため、安定ソートである必要はありません

  ソースコード

import sys

class Fenw:
    def __init__(self, n):
        self.n = n
        self.tree = [0] * (n+1)
    
    def update(self, index, delta):
        i = index
        while i <= self.n:
            self.tree[i] += delta
            i += i & -i
            
    def query(self, index):
        s = 0
        i = index
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
    
    def range_query(self, l, r):
        return self.query(r) - self.query(l-1)

def main():
    data = sys.stdin.read().split()
    it = iter(data)
    N = int(next(it)); M = int(next(it)); Q = int(next(it)); K = int(next(it))
    books = []
    for i in range(M):
        s = int(next(it)); d = int(next(it))
        books.append((s, d))
        
    queries = []
    for j in range(Q):
        l = int(next(it)); r = int(next(it)); t = int(next(it))
        queries.append((t, l, r, j))
        
    # 本をページ数で降順ソート
    books.sort(key=lambda x: x[1], reverse=True)
    # クエリをTで降順ソート
    queries.sort(key=lambda x: x[0], reverse=True)
    
    fenw = Fenw(N)
    res = [0] * Q
    idx = 0
    # ページ数が大きい本から追加していく
    for t_val, l, r, orig_idx in queries:
        while idx < M and books[idx][1] >= t_val:
            s = books[idx][0]
            fenw.update(s, 1)
            idx += 1
        count = fenw.range_query(l, r)
        res[orig_idx] = max(count - K, 0)
        
    for ans in res:
        print(ans)

if __name__ == "__main__":
    main()

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