Overview

We treat each bookshelf’s contribution as \(A_i \times V_i\), and solve the problem of “answering range sum queries considering only bookshelves with \(D_i \le T\) as active.”
We sort queries offline by date \(T\) and use a Fenwick Tree (BIT) to efficiently compute range sums.

Analysis

The desired value for each query \((L, R, T)\) is:

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

1. Why the naive solution is too slow

If we iterate over the interval \([L,R]\) for each query and check \(D_i \le T\),
the worst case is \(O(NQ)\).
Given the constraints \(N+Q \le 2\times 10^5\), this won’t pass in time.

2. Key insight

If we process queries in increasing order of date \(T\),
the “set of available bookshelves” only monotonically increases (never decreases).

• Bookshelves with \(D_i \le T\) up to a certain point are active
• For the next larger \(T\), only additional bookshelves become active

By exploiting this “monotonic increase,” we don’t need to re-evaluate from scratch each time.

3. Managing range sums with BIT

We add the weight \(w_i=A_iV_i\) of each newly activated bookshelf \(i\) at position \(i\).
Then, the answer for a query at that point is simply the range sum:

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

which can be efficiently computed with a BIT.

Algorithm

1. Store each bookshelf as \((D_i,\ i,\ w_i=A_iV_i)\) in an array.
2. Store each query as \((T_j,\ L_j,\ R_j,\ id)\) in an array (\(id\) is the original index).
3. Sort bookshelves in ascending order of \(D\), and queries in ascending order of \(T\).
4. Place a pointer \(p\) at the beginning of the bookshelf array.
5. Process queries in increasing order of \(T\):
   • while p < N and shelves[p].d <= T:
     • Add w to the BIT at position idx (activate it)
     • p++
   • Compute the range sum sum(R)-sum(L-1) using BIT, and store it in ans[id]
6. Output ans in the original query order.

Illustrative example

• When processing queries in date order, the BIT only contains “the sales of bookshelves whose repairs have been completed by that date.”
• Therefore, answering a query is simply “computing the range sum on the BIT at that point.”

Complexity

• Time complexity: \(O((N+Q)\log N)\)
  (Sorting: \(O(N\log N + Q\log Q)\), each bookshelf addition and each query answer take \(\log N\) each)
• Space complexity: \(O(N+Q)\)

Implementation notes

• Use long long since \(A_iV_i\) and the sums can become large.

• Implementing BIT as 1-indexed is convenient (it matches the input shelf indices).

• Since sorting disrupts the query order, carry an id to output results in the original order.

• The key is using while (D_i <= T) to “batch-add all bookshelves that become active at that point.”

  Source Code

#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;
}

---

This editorial was generated by gpt-5.3-codex.