Overview

This problem asks us to efficiently compute, for each query, the sum of \(A_i \times V_i\) over all bookshelves within the range \([L_j, R_j]\) that satisfy \(D_i \leq T_j\). We solve it by combining offline query processing with a BIT (Binary Indexed Tree).

Analysis

Problems with the Naive Approach

If we scan the range \([L_j, R_j]\) for each query and search for bookshelves satisfying the condition \(D_i \leq T_j\), the worst case is \(O(N \times Q)\). Given the constraint \(N + Q \leq 2 \times 10^5\), both \(N\) and \(Q\) can be on the order of \(10^5\), resulting in \(O(N \times Q) \approx 10^{10}\), which will TLE.

Key Insight

Focus on the query condition \(D_i \leq T_j\). If we process queries in increasing order of \(T_j\), the set of “repaired bookshelves” grows monotonically. In other words, as \(T_j\) increases, bookshelves that satisfy the condition are only added, never removed.

By sorting bookshelves in increasing order of \(D_i\), as the query’s \(T_j\) progresses, we only need to “add” bookshelves sequentially into the data structure.

Solution Strategy

• Process queries offline (read all queries in advance and sort them)
• Use a BIT (Fenwick Tree) to efficiently compute range sums

Algorithm

1. Preprocessing: Compute the total usage fee \(W_i = A_i \times V_i\) for each bookshelf.
2. Sort bookshelves: Sort bookshelves in ascending order of \(D_i\) (repair completion date).
3. Sort queries: Sort queries in ascending order of \(T_j\) (date).
4. Offline processing:
   • Maintain a pointer ptr to manage the sorted bookshelves sequentially.
   • Process each query \(j\) in increasing order of \(T_j\).
     • For all unadded bookshelves satisfying \(D_i \leq T_j\), add \(W_i\) to position \(i\) in the BIT.
     • Query the BIT for the sum over the range \([L_j, R_j]\) and record it as the answer.
5. Output: Output the answers in the original query order.

Concrete Example

Suppose there are 3 bookshelves with \((D_1, D_2, D_3) = (3, 1, 2)\) and \(W = (100, 200, 50)\).

• When processing the query “\(T=2, [1,3]\)”, bookshelves \(2\) (\(D=1\)) and \(3\) (\(D=2\)) satisfying \(D_i \leq 2\) have already been added to the BIT. The sum over the range \([1,3]\) is \(200 + 50 = 250\).

Complexity

• Time complexity: \(O((N + Q) \log N)\)
  • Sorting bookshelves: \(O(N \log N)\)
  • Sorting queries: \(O(Q \log Q)\)
  • BIT updates for each bookshelf: \(O(N \log N)\) in total
  • BIT range sum queries for each query: \(O(Q \log N)\) in total
• Space complexity: \(O(N + Q)\)

Implementation Notes

• BIT is managed with 1-indexing: Since bookshelf numbers are 1-based in the problem statement, they directly correspond to BIT indices. Internally, order[ptr] + 1 is used to convert to 1-indexed.

• Beware of overflow: \(A_i \times V_i\) can be at most \(10^4 \times 10^4 = 10^8\), and since there can be up to \(2 \times 10^5\) bookshelves in a range, the total can reach up to \(2 \times 10^{13}\). Using long long is necessary.

• Preserve original query order: Since queries are sorted for processing, store results in an ans[j] array to output them in the original order.

  Source Code

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

---

This editorial was generated by claude4.6opus-thinking.