概要

区間 \([L_j, R_j]\) 内の書棚のうち \(D_i \leq T_j\) を満たすものの \(A_i \times V_i\) の合計を、各クエリについて高速に求める問題です。オフラインクエリ処理とBIT（Binary Indexed Tree）を組み合わせて解きます。

考察

素朴なアプローチの問題点

各クエリについて区間 \([L_j, R_j]\) を走査し、条件 \(D_i \leq T_j\) を満たす書棚を探すと、最悪 \(O(N \times Q)\) かかります。\(N + Q \leq 2 \times 10^5\) という制約から \(N\) と \(Q\) がともに \(10^5\) 程度になりうるため、\(O(N \times Q) \approx 10^{10}\) となり TLE します。

重要な気づき

クエリの条件 \(D_i \leq T_j\) に注目します。もしクエリを \(T_j\) の小さい順に処理するなら、「修復が完了した書棚」は単調に増えていきます。つまり、\(T_j\) が増えるたびに新たに条件を満たす書棚が追加されるだけで、削除されることはありません。

これにより、書棚を \(D_i\) の小さい順にソートしておけば、クエリの \(T_j\) が進むにつれて書棚を順番にデータ構造に「追加」していくだけで済みます。

解決方針

• クエリをオフライン（事前にすべて読み込んで並べ替え）で処理する
• 区間和を高速に求めるために BIT（Fenwick Tree）を使う

アルゴリズム

1. 前処理: 各書棚の利用料合計 \(W_i = A_i \times V_i\) を計算する。
2. 書棚のソート: 書棚を \(D_i\)（修復完了日）の昇順にソートする。
3. クエリのソート: クエリを \(T_j\)（日付）の昇順にソートする。
4. オフライン処理:
   • ポインタ ptr を用意し、ソート済みの書棚を順に管理する。
   • 各クエリ \(j\) を \(T_j\) の小さい順に処理する。
     • \(D_i \leq T_j\) を満たす未追加の書棚を BIT の位置 \(i\) に \(W_i\) を加算する。
     • BIT で区間 \([L_j, R_j]\) の合計を求め、答えとする。
5. 出力: 元のクエリ順に答えを出力する。

具体例

書棚が3つで、\((D_1, D_2, D_3) = (3, 1, 2)\)、\(W = (100, 200, 50)\) とします。

• クエリ「\(T=2, [1,3]\)」を処理するとき、\(D_i \leq 2\) を満たす書棚 \(2\)（\(D=1\)）と書棚 \(3\)（\(D=2\)）がBITに追加済み。区間 \([1,3]\) の和は \(200 + 50 = 250\)。

計算量

• 時間計算量: \(O((N + Q) \log N)\)
  • 書棚のソート: \(O(N \log N)\)
  • クエリのソート: \(O(Q \log Q)\)
  • 各書棚のBIT更新: 合計 \(O(N \log N)\)
  • 各クエリのBIT区間和取得: 合計 \(O(Q \log N)\)
• 空間計算量: \(O(N + Q)\)

実装のポイント

• BITは1-indexedで管理: 書棚番号は問題文で1始まりなので、BITの添字とそのまま対応させられる。内部配列では order[ptr] + 1 で1-indexedに変換している。

• オーバーフローに注意: \(A_i \times V_i\) は最大 \(10^4 \times 10^4 = 10^8\) で、区間内の書棚数が最大 \(2 \times 10^5\) あるため合計は最大 \(2 \times 10^{13}\) になりうる。long long を使う必要がある。

• クエリの元の順番を保持: ソートして処理した後、元の順番で出力するために ans[j] 配列に格納する。

  ソースコード

#include <bits/stdc++.h>
using namespace std;

struct BIT {
    int n;
    vector<long long> tree;
    BIT(int n) : n(n), tree(n + 1, 0) {}
    void update(int i, long long val) {
        for (; i <= n; i += i & (-i))
            tree[i] += val;
    }
    long long query(int i) {
        long long s = 0;
        for (; i > 0; i -= i & (-i))
            s += tree[i];
        return s;
    }
    long long query(int l, int r) {
        return query(r) - query(l - 1);
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, Q;
    cin >> N >> Q;

    vector<int> A(N), D(N), V(N);
    vector<long long> W(N);
    for (int i = 0; i < N; i++) {
        cin >> A[i] >> D[i] >> V[i];
        W[i] = (long long)A[i] * V[i];
    }

    // Sort shelves by D
    vector<int> order(N);
    iota(order.begin(), order.end(), 0);
    sort(order.begin(), order.end(), [&](int a, int b) {
        return D[a] < D[b];
    });

    // Read queries
    vector<int> L(Q), R(Q), T(Q);
    for (int j = 0; j < Q; j++) {
        cin >> L[j] >> R[j] >> T[j];
    }

    // Sort queries by T
    vector<int> qorder(Q);
    iota(qorder.begin(), qorder.end(), 0);
    sort(qorder.begin(), qorder.end(), [&](int a, int b) {
        return T[a] < T[b];
    });

    BIT bit(N);
    vector<long long> ans(Q);
    int ptr = 0;

    for (int j : qorder) {
        while (ptr < N && D[order[ptr]] <= T[j]) {
            bit.update(order[ptr] + 1, W[order[ptr]]);
            ptr++;
        }
        ans[j] = bit.query(L[j], R[j]);
    }

    for (int j = 0; j < Q; j++) {
        cout << ans[j] << '\n';
    }

    return 0;
}

---

この解説は claude4.6opus-thinking によって生成されました。