概要

各書棚 \(i\) の価値を \(A_i \times V_i\) として、各クエリについて「区間 \([L_j, R_j]\) の中で \(D_i \leq T_j\) を満たす書棚の価値の合計」を求める問題です。

日付 \(T_j\) 以下で修復済みの書棚だけを対象にして、区間和を高速に求めます。

考察

各計画 \(j\) で求めたい値は、

\[ \sum_{\substack{L_j \leq i \leq R_j \\ D_i \leq T_j}} A_i \times V_i \]

です。

書棚 \(i\) について、得られる利用料は常に \(A_i \times V_i\) です。
したがって、各書棚を次のように考えます。

• 位置: \(i\)
• 有効になる日: \(D_i\)
• 値: \(A_i \times V_i\)

クエリでは、「日付 \(T_j\) までに有効になった書棚」のうち、位置が \([L_j, R_j]\) にあるものの合計を求めればよいです。

素朴に各クエリごとに \(L_j\) から \(R_j\) まで調べると、最悪で \(O(NQ)\) かかります。
\(N+Q \leq 2 \times 10^5\) なので、これは間に合いません。

そこで、クエリを日付 \(T_j\) の昇順に処理します。

日付が小さいクエリから順に見ていくと、対象となる書棚は少しずつ増えていくだけです。
つまり、修復完了日 \(D_i\) が小さい順に書棚を追加していけば、各書棚は一度だけ処理すれば済みます。

追加済みの書棚について、位置 \(i\) に値 \(A_i \times V_i\) を置いておけば、クエリは区間和

\[ \text{sum}(L_j, R_j) \]

として求められます。

区間和を高速に求めるために、Fenwick Tree（BIT）を使います。

アルゴリズム

次の手順で処理します。

1. 各書棚について、以下の情報を作る

   • 修復完了日 \(D_i\)
   • 位置 \(i\)
   • 値 \(A_i \times V_i\)

2. 書棚を \(D_i\) の昇順にソートする

3. 各クエリについて、以下の情報を作る

   • 日付 \(T_j\)
   • 区間 \([L_j, R_j]\)
   • クエリ番号 \(j\)

4. クエリを \(T_j\) の昇順にソートする

5. Fenwick Tree を用意する
   Fenwick Tree には「現在の日付までに修復済みの書棚の値」を位置ごとに追加していく

6. ソート済みクエリを順に処理する

   • 現在のクエリの日付を \(T\) とする
   • \(D_i \leq T\) となる書棚をすべて Fenwick Tree に追加する
   • Fenwick Tree で区間 \([L, R]\) の和を求める
   • 答えを元のクエリ番号の位置に保存する

Fenwick Tree では、区間和は次のように求めます。

\[ \text{sum}(L, R) = \text{prefix\_sum}(R) - \text{prefix\_sum}(L-1) \]

例えば、日付 \(T=5\) のクエリを処理するときは、\(D_i \leq 5\) の書棚だけが Fenwick Tree に追加されています。
その状態で区間和を取れば、条件を満たす書棚の合計だけを得られます。

計算量

• 時間計算量: \(O((N+Q)\log N)\)
  • 書棚のソートに \(O(N\log N)\)
  • クエリのソートに \(O(Q\log Q)\)
  • 各書棚の追加、各クエリの区間和取得にそれぞれ \(O(\log N)\)
• 空間計算量: \(O(N+Q)\)

実装のポイント

• クエリは \(T_j\) の昇順に並べ替えて処理しますが、出力は入力順に行う必要があります。
  そのため、クエリ番号 qi を一緒に保持しておき、答えは ans[qi] に保存します。

• Fenwick Tree は 1-indexed で実装すると、書棚番号 \(1\) から \(N\) をそのまま使えて便利です。

• 書棚を追加するときは、条件が \(D_i \leq T_j\) なので、while items[p][0] <= t: とします。
  第 \(D_i\) 日目から貸し出し可能なので、等号を含める点に注意します。

• 答えは最大で \(2 \times 10^{13}\) になるため、他の言語では 64 bit 整数型を使う必要があります。Python では通常の int で問題ありません。

  ソースコード

import sys

data = list(map(int, sys.stdin.buffer.read().split()))
idx = 0

N = data[idx]
Q = data[idx + 1]
idx += 2

items = []
for i in range(1, N + 1):
    a = data[idx]
    d = data[idx + 1]
    v = data[idx + 2]
    idx += 3
    items.append((d, i, a * v))

queries = []
for qi in range(Q):
    l = data[idx]
    r = data[idx + 1]
    t = data[idx + 2]
    idx += 3
    queries.append((t, l, r, qi))

items.sort()
queries.sort()

bit = [0] * (N + 1)

def add(i, x):
    while i <= N:
        bit[i] += x
        i += i & -i

def prefix_sum(i):
    s = 0
    while i > 0:
        s += bit[i]
        i -= i & -i
    return s

ans = [0] * Q
p = 0

for t, l, r, qi in queries:
    while p < N and items[p][0] <= t:
        _, pos, val = items[p]
        add(pos, val)
        p += 1
    ans[qi] = prefix_sum(r) - prefix_sum(l - 1)

print("\n".join(map(str, ans)))

---

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