Overview

For each lending plan, we need to find the total profit \(A_i \times V_i\) of bookshelves satisfying \(D_i \leq T_j\) within the interval \([L_j, R_j]\).

We consider “only activating bookshelves that have been repaired by date \(T\)” and process queries in order of date.

Analysis

The answer for plan \(j\) is given by the following expression:

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

Here, if we define the profit of bookshelf \(i\) as

\[ W_i = A_i \times V_i \]

then the problem becomes “find the interval sum of weights \(W_i\) at positions \(i\) satisfying \(D_i \leq T_j\).”

If we naively scan from \(L_j\) to \(R_j\) for each query, the worst case is \(O(NQ)\).
Since \(N + Q \leq 2 \times 10^5\), this will not be fast enough.

The key insight is that as the date \(T\) increases, the set of bookshelves satisfying \(D_i \leq T\) only grows.

For example, suppose we process queries in ascending order of \(T\):

• At some point, we process a query with \(T = 5\)
• Next, we process a query with \(T = 8\)

At this point, the only newly added bookshelves are those with \(6 \leq D_i \leq 8\).
Bookshelves with \(D_i \leq 5\) have already been added, so there is no need to recompute them.

Therefore, we can solve this efficiently using the following approach:

1. Sort bookshelves in ascending order of \(D_i\)
2. Sort queries in ascending order of \(T_j\)
3. Add bookshelves that have been repaired by the current date to a Fenwick Tree
4. Compute the interval sum for each query using the Fenwick Tree

Algorithm

First, for each bookshelf, we maintain the following information:

• Repair completion date \(D_i\)
• Position \(i\)
• Profit \(W_i = A_i \times V_i\)

We store these as a bookshelf list, sorted in ascending order of \(D_i\).

Also, for each query, we maintain the following information:

• Left endpoint \(L_j\)
• Right endpoint \(R_j\)
• Date \(T_j\)
• Original query index \(j\)

Queries are also sorted in ascending order of \(T_j\).
However, since output must be in input order, we save the original query index.

The Fenwick Tree only contains the profits of bookshelves that have been repaired by the current query’s date \(T\).

The processing flow is as follows:

1. Sort bookshelves in ascending order of \(D_i\)
2. Sort queries in ascending order of \(T_j\)
3. Initialize an empty Fenwick Tree
4. Prepare a pointer \(p\) pointing to the beginning of the bookshelf list
5. Process queries in ascending order of date:
   • Among bookshelves not yet added, add all those satisfying \(D_i \leq T_j\) to the Fenwick Tree
   • Compute the sum over interval \([L_j, R_j]\) using the Fenwick Tree
   • Store the answer at the position corresponding to the original query index
6. Finally, output the answers in input order

In the Fenwick Tree, we add value \(W_i\) at position \(i\), and compute the sum over \([L, R]\) using:

\[ \text{sum}(R) - \text{sum}(L - 1) \]

Complexity

• Time complexity: \(O(N \log N + Q \log Q + (N + Q) \log N)\)
• Space complexity: \(O(N + Q)\)

Implementation Notes

• The answer can be as large as \(2 \times 10^{13}\), so use long long instead of int.

• Compute \(A_i \times V_i\) using long long as well.

• Using a 1-indexed Fenwick Tree makes it easy to correspond with bookshelf numbers \(1, 2, \ldots, N\).

• Since sorting queries disrupts the input order, save the original query index id.

• The condition is \(D_i \leq T_j\). Since day \(D_i\) is inclusive, use <= instead of < for comparison.

  Source Code

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

struct Fenwick {
    int n;
    vector<long long> bit;

    Fenwick(int n) : n(n), bit(n + 1, 0) {}

    void add(int idx, long long val) {
        for (; idx <= n; idx += idx & -idx) bit[idx] += val;
    }

    long long sum(int idx) const {
        long long res = 0;
        for (; idx > 0; idx -= idx & -idx) res += bit[idx];
        return res;
    }

    long long range_sum(int l, int r) const {
        return sum(r) - sum(l - 1);
    }
};

struct Item {
    int d;
    int pos;
    long long w;
};

struct Query {
    int l, r, t, id;
};

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

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

    vector<Item> items(N);
    for (int i = 1; i <= N; i++) {
        long long A, D, V;
        cin >> A >> D >> V;
        items[i - 1] = {(int)D, i, A * V};
    }

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

    sort(items.begin(), items.end(), [](const Item& a, const Item& b) {
        return a.d < b.d;
    });

    sort(queries.begin(), queries.end(), [](const Query& a, const Query& b) {
        return a.t < b.t;
    });

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

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

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

    return 0;
}

---

This editorial was generated by gpt-5.5-xhigh.