Overview

This problem asks us to find the total usage fee of books within a specific interval \([L_j, R_j]\) of bookshelves arranged in a row, considering only those whose repair has been completed by a specified date \(T_j\).

For each bookshelf \(i\), if we define the usage fee as \(W_i = A_i \times V_i\), then each query requires computing “the sum of \(W_i\) for all \(i\) satisfying \(L_j \le i \le R_j\) and \(D_i \le T_j\).”

Analysis

Naive Approach and Its Limitations

For each query, one might consider looping through bookshelves \(L_j\) to \(R_j\), checking whether the condition \(D_i \le T_j\) is satisfied, and accumulating the sum. However, in the worst case, this takes \(O(N)\) time per query, resulting in \(O(NQ)\) overall. Given the constraints \(N, Q \le 2 \times 10^5\), \(O(NQ)\) amounts to approximately \(4 \times 10^{10}\) operations, which will not finish within the time limit.

Viewing as a 2D Range Sum

This problem can be viewed as a 2D Range Sum Query by treating each bookshelf as a point \((i, D_i)\) with coordinates “position \(i\)” and “repair date \(D_i\)” on a 2D plane, where we want to find the sum of values within a rectangular region: 1. \(L_j \le \text{position} \le R_j\) 2. \(1 \le \text{repair date} \le T_j\)

For problems with “two conditions” like this, the offline query technique—where we sort and process by one condition (here, the date)—is extremely effective.

Algorithm

By reading all queries in advance and sorting them in ascending order of date, we replace the date condition with a “progressively adding” operation.

1. Preparation:
   • For each bookshelf, precompute the usage fee \(W_i = A_i \times V_i\).
   • Sort all bookshelves in ascending order of their repair completion date \(D_i\).
   • Sort all queries in ascending order of their target date \(T_j\).
2. Data Structure:
   • Prepare a Fenwick Tree (BIT) to efficiently compute range sums over position \(i\).
3. Processing Queries:
   • Iterate through the sorted queries in order.
   • For the current query’s date \(T_j\), add (add) the value \(W_i\) at position \(i\) in the BIT for all bookshelves whose repair date \(D_i \le T_j\).
   • Use the BIT to compute (query) the sum over the interval \([L_j, R_j]\).
   • Since queries are sorted, there is no need to remove bookshelves once added to the BIT, allowing efficient processing.
4. Output:
   • After computing results for all queries, reorder them back to the original query order and output them.

Complexity

• Time Complexity: \(O((N + Q) \log N + (N \log N + Q \log Q))\)
  • Sorting bookshelves and queries takes \(O(N \log N + Q \log Q)\).
  • Adding bookshelves to the BIT is done \(N\) times, and computing each query is done \(Q\) times, each taking \(O(\log N)\), so the main processing is \(O((N + Q) \log N)\).
  • Overall, this is sufficiently fast for the constraint of \(2 \times 10^5\).
• Space Complexity: \(O(N + Q)\)
  • Arrays are needed to store bookshelf information, query information, the BIT, and the results.

Implementation Notes

• Sum of Usage Fees: The usage fee \(A_i \times V_i\) can be at most \(10^4 \times 10^4 = 10^8\). Their total sum can reach \(2 \times 10^{13}\), so in C++ you must use the long long type.

• Offline Processing: Since queries are sorted for processing, you need to retain the original index of each query so that you can identify “which query each answer belongs to” when recording results.

• Fenwick Tree: It is common to implement it as 1-indexed. In this problem, it directly corresponds to the bookshelf numbers \(1 \dots N\).

  Source Code

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

/**
 * この問題は、各書棚 i について (A_i * V_i) という重みを考え、
 * 指定された区間 [L_j, R_j] 内で D_i <= T_j を満たす書棚の重みの総和を求める問題です。
 * これは二次元の矩形領域の和を求める問題（2D Range Sum Query）の一種です。
 * 
 * オフラインクエリの手法を用い、書棚を修復完了日 D_i の昇順に、
 * クエリを計画の日付 T_j の昇順にソートして処理することで、
 * Fenwick Tree (Binary Indexed Tree) を用いて効率的に解くことができます。
 * 計算量は O((N + Q) log N) となり、制約下で十分に高速に動作します。
 */

// 書棚の情報を格納する構造体
struct Shelf {
    int id;      // 書棚の元の位置 (1-indexed)
    int d;       // 修復完了日
    long long w; // 貸し出し時に得られる利用料 (A_i * V_i)
};

// クエリの情報を格納する構造体
struct Query {
    int id;      // クエリの元のインデックス
    int l, r, t; // 範囲 [L_j, R_j] と日付 T_j
};

// Fenwick Tree (Binary Indexed Tree) の実装
struct FenwickTree {
    int n;
    vector<long long> tree;

    FenwickTree(int n) : n(n), tree(n + 1, 0) {}

    // インデックス i (1-indexed) に val を加算する
    void add(int i, long long val) {
        for (; i <= n; i += i & -i) {
            tree[i] += val;
        }
    }

    // 1 から i までの累積和を求める
    long long query(int i) {
        long long res = 0;
        for (; i > 0; i -= i & -i) {
            res += tree[i];
        }
        return res;
    }

    // 範囲 [l, r] の和を求める
    long long query(int l, int r) {
        if (l > r) return 0;
        return query(r) - query(l - 1);
    }
};

int main() {
    // 入出力の高速化
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, Q;
    if (!(cin >> N >> Q)) return 0;

    // 書棚データの読み込み
    vector<Shelf> shelves(N);
    for (int i = 0; i < N; ++i) {
        int a, d, v;
        cin >> a >> d >> v;
        // 各書棚が貸し出された際の合計利用料を計算しておく
        shelves[i] = {i + 1, d, (long long)a * v};
    }

    // クエリデータの読み込み
    vector<Query> queries(Q);
    for (int i = 0; i < Q; ++i) {
        int l, r, t;
        cin >> l >> r >> t;
        queries[i] = {i, l, r, t};
    }

    // 書棚を修復完了日 D_i の昇順にソート
    sort(shelves.begin(), shelves.end(), [](const Shelf& a, const Shelf& b) {
        return a.d < b.d;
    });

    // クエリを日付 T_j の昇順にソート
    sort(queries.begin(), queries.end(), [](const Query& a, const Query& b) {
        return a.t < b.t;
    });

    FenwickTree ft(N);
    vector<long long> results(Q);
    int shelf_ptr = 0;

    // 日付の早いクエリから順に処理
    for (int i = 0; i < Q; ++i) {
        // クエリの日付 T_j までに修復が完了する書棚を Fenwick Tree に追加
        while (shelf_ptr < N && shelves[shelf_ptr].d <= queries[i].t) {
            ft.add(shelves[shelf_ptr].id, shelves[shelf_ptr].w);
            shelf_ptr++;
        }
        // 指定された範囲 [L_j, R_j] の合計利用料を計算
        results[queries[i].id] = ft.query(queries[i].l, queries[i].r);
    }

    // クエリの元の順序で結果を出力
    for (int i = 0; i < Q; ++i) {
        cout << results[i] << "\n";
    }

    return 0;
}

This editorial was generated by gemini-3-flash-thinking.