概要

各書棚の寄与を \(A_i \times V_i\) とみなし、
「\(D_i \le T\) の書棚だけを有効にした状態で区間和を答える」問題です。
クエリを日付 \(T\) でオフラインソートし、Fenwick Tree（BIT）で高速に区間和を求めます。

考察

求めたい値は各クエリ \((L, R, T)\) に対して

\( \sum_{\substack{L \le i \le R \\ D_i \le T}} A_iV_i \)

です。

1. 素朴解が遅い理由

各クエリごとに区間 \([L,R]\) をなめて \(D_i \le T\) を判定すると、
最悪で \(O(NQ)\) になります。
制約は \(N+Q \le 2\times 10^5\) なので、これは間に合いません。

2. 重要な気づき

クエリの日付 \(T\) が小さい順に見ていくと、
「利用可能な書棚集合」は単調に増えるだけです（減らない）。

• ある時点までに \(D_i \le T\) となった書棚は有効
• 次のより大きい \(T\) では、さらに一部の書棚が有効になるだけ

この「単調増加」を使えば、毎回最初から判定し直す必要がありません。

3. 区間和は BIT で管理

有効になった書棚 \(i\) の重み \(w_i=A_iV_i\) を、位置 \(i\) に追加していく。
すると、その時点でのクエリ答えは単に区間和

\( \text{sum}(L,R) \)

になるので、BIT で高速に処理できます。

アルゴリズム

1. 各書棚を \((D_i,\ i,\ w_i=A_iV_i)\) として配列に入れる。
2. 各クエリを \((T_j,\ L_j,\ R_j,\ id)\) として配列に入れる（\(id\) は元の順番）。
3. 書棚を \(D\) 昇順、クエリを \(T\) 昇順でソート。
4. ポインタ \(p\) を書棚側先頭に置く。
5. クエリを小さい \(T\) から順に処理：
   • while p < N and shelves[p].d <= T:
     • BIT の位置 idx に w を加算（有効化）
     • p++
   • BIT で区間和 sum(R)-sum(L-1) を求め、ans[id] に保存
6. ans を元のクエリ順に出力。

イメージ例

• 日付順でクエリを見ると、BIT には「その日までに修復完了した書棚の売上」だけが載っている。
• だからクエリは「その時点の BIT 上で区間和を取るだけ」。

計算量

• 時間計算量: \(O((N+Q)\log N)\)
  （ソート \(O(N\log N + Q\log Q)\)、各書棚追加と各クエリ回答がそれぞれ \(\log N\)）
• 空間計算量: \(O(N+Q)\)

実装のポイント

• \(A_iV_i\) や総和は大きくなるため long long を使う。

• BIT は 1-indexed で実装すると扱いやすい（入力の棚番号とも一致）。

• クエリはソートで順番が崩れるので、id を持って元の順で出力する。

• while (D_i <= T) で「その時点で有効になる書棚をまとめて追加」するのが肝です。

  ソースコード

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

struct Fenwick {
    int n;
    vector<long long> bit;
    Fenwick(int n = 0) { init(n); }
    void init(int n_) {
        n = n_;
        bit.assign(n + 1, 0);
    }
    void add(int idx, long long val) {
        for (; idx <= n; idx += idx & -idx) bit[idx] += val;
    }
    long long sumPrefix(int idx) const {
        long long res = 0;
        for (; idx > 0; idx -= idx & -idx) res += bit[idx];
        return res;
    }
    long long sumRange(int l, int r) const {
        if (l > r) return 0;
        return sumPrefix(r) - sumPrefix(l - 1);
    }
};

struct Shelf {
    int d, idx;
    long long w;
    bool operator<(const Shelf& other) const {
        return d < other.d;
    }
};

struct Query {
    int t, l, r, id;
    bool operator<(const Query& other) const {
        return t < other.t;
    }
};

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

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

    vector<Shelf> shelves;
    shelves.reserve(N);

    for (int i = 1; i <= N; ++i) {
        long long A, V;
        int D;
        cin >> A >> D >> V;
        shelves.push_back({D, i, A * V});
    }

    vector<Query> queries;
    queries.reserve(Q);
    for (int j = 0; j < Q; ++j) {
        int L, R, T;
        cin >> L >> R >> T;
        queries.push_back({T, L, R, j});
    }

    sort(shelves.begin(), shelves.end());
    sort(queries.begin(), queries.end());

    Fenwick fw(N);
    vector<long long> ans(Q);

    int p = 0;
    for (const auto& qu : queries) {
        while (p < N && shelves[p].d <= qu.t) {
            fw.add(shelves[p].idx, shelves[p].w);
            ++p;
        }
        ans[qu.id] = fw.sumRange(qu.l, qu.r);
    }

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

    return 0;
}

---

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