概要

この問題は、1列に並んだ書棚の特定の区間 \([L_j, R_j]\) 内にある本のうち、指定された日付 \(T_j\) までに修復が終わっているものの合計利用料を求める問題です。

各書棚 \(i\) について、得られる利用料を \(W_i = A_i \times V_i\) とすると、各クエリでは「\(L_j \le i \le R_j\) かつ \(D_i \le T_j\) を満たす \(W_i\) の総和」を計算することになります。

考察

素朴な解法とその限界

各クエリに対して、書棚 \(L_j\) から \(R_j\) までをループで走査し、条件 \(D_i \le T_j\) を満たすか確認して加算する方法が考えられます。しかし、この方法では最悪の場合、1つのクエリにつき \(O(N)\) の時間がかかり、全体で \(O(NQ)\) となります。 本問題の制約は \(N, Q \le 2 \times 10^5\) であるため、\(O(NQ)\) は最大で \(4 \times 10^{10}\) 程度の計算量となり、制限時間内に終わりません。

2次元の領域和として捉える

この問題は、各書棚を「位置 \(i\)」と「修復日 \(D_i\)」を座標に持つ点 \((i, D_i)\) と見なすと、2次元平面上の矩形領域内にある値の合計を求める問題（2D Range Sum Query）と捉えることができます。 1. \(L_j \le \text{位置} \le R_j\) 2. \(1 \le \text{修復日} \le T_j\)

このような「2つの条件」がある問題では、片方の条件（ここでは日付）でデータをソートして処理するオフラインクエリの手法が非常に有効です。

アルゴリズム

クエリをあらかじめすべて読み込み、日付の昇順に並べ替えて処理することで、日付の条件を「順番に追加していく」という操作に置き換えます。

1. 準備:
   • 各書棚について、利用料 \(W_i = A_i \times V_i\) を計算しておきます。
   • すべての書棚を修復完了日 \(D_i\) の昇順にソートします。
   • すべてのクエリを目標の日付 \(T_j\) の昇順にソートします。
2. データ構造の利用:
   • 位置 \(i\) に関する区間和を高速に計算するため、Fenwick Tree (BIT) を用意します。
3. クエリの処理:
   • ソートしたクエリを順番に見ていきます。
   • 現在のクエリの日付 \(T_j\) 以下の修復日 \(D_i\) を持つ書棚を、すべて BIT の位置 \(i\) に値 \(W_i\) を加算（add）します。
   • BIT を使って、区間 \([L_j, R_j]\) の和を計算（query）します。
   • クエリをソートしているため、一度 BIT に追加した書棚を削除する必要はなく、効率的に進められます。
4. 出力:
   • すべてのクエリの結果を計算した後、元のクエリの順番に並べ直して出力します。

計算量

• 時間計算量: \(O((N + Q) \log N + (N \log N + Q \log Q))\)
  • 書棚とクエリのソートに \(O(N \log N + Q \log Q)\) かかります。
  • 各書棚の BIT への追加が \(N\) 回、各クエリの計算が \(Q\) 回行われ、それぞれ \(O(\log N)\) かかるため、メインの処理は \(O((N + Q) \log N)\) です。
  • 全体として、制約の \(2 \times 10^5\) に対して十分に高速です。
• 空間計算量: \(O(N + Q)\)
  • 書棚の情報、クエリの情報、BIT、および結果の格納に配列が必要です。

実装のポイント

• 利用料の総和: 利用料 \(A_i \times V_i\) は最大で \(10^4 \times 10^4 = 10^8\) です。その総和は \(2 \times 10^{13}\) に達するため、C++ では long long 型を使用する必要があります。

• オフライン処理: クエリをソートして処理するため、答えを記録する際に「どのクエリに対する答えか」を識別できるよう、元のインデックスを保持しておく必要があります。

• Fenwick Tree: 1-indexed で実装するのが一般的です。今回の書棚の番号 \(1 \dots N\) とそのまま対応させることができます。

  ソースコード

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

この解説は gemini-3-flash-thinking によって生成されました。