概要

各貸し出し計画について、区間 \([L_j, R_j]\) の中で \(D_i \leq T_j\) を満たす書棚の利益 \(A_i \times V_i\) の合計を求める問題です。

「日付 \(T\) までに修復済みの書棚だけを有効にする」と考え、クエリを日付順に処理します。

考察

計画 \(j\) の答えは次の式です。

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

ここで、書棚 \(i\) の利益を

\[ W_i = A_i \times V_i \]

とおくと、問題は「\(D_i \leq T_j\) を満たす位置 \(i\) の重み \(W_i\) について、区間和を求める」問題になります。

素朴に各クエリごとに \(L_j\) から \(R_j\) まで全探索すると、最悪で \(O(NQ)\) かかります。
\(N + Q \leq 2 \times 10^5\) なので、これは間に合いません。

重要な気づきは、日付 \(T\) が大きくなるほど、条件 \(D_i \leq T\) を満たす書棚は増えるだけであることです。

例えば、クエリを \(T\) の昇順に処理するとします。

• ある時点で \(T = 5\) のクエリを処理する
• その次に \(T = 8\) のクエリを処理する

このとき、新たに追加されるのは \(6 \leq D_i \leq 8\) の書棚だけです。
すでに \(D_i \leq 5\) の書棚は追加済みなので、再計算する必要がありません。

したがって、

1. 書棚を \(D_i\) の昇順に並べる
2. クエリを \(T_j\) の昇順に並べる
3. 現在の日付までに修復済みになった書棚を Fenwick Tree に追加する
4. クエリの区間和を Fenwick Tree で求める

という方法で高速に解けます。

アルゴリズム

まず、各書棚について以下の情報を持ちます。

• 修復完了日 \(D_i\)
• 位置 \(i\)
• 利益 \(W_i = A_i \times V_i\)

これらを書棚リストとして、\(D_i\) の昇順にソートします。

また、各クエリについて以下の情報を持ちます。

• 左端 \(L_j\)
• 右端 \(R_j\)
• 日付 \(T_j\)
• 元のクエリ番号 \(j\)

クエリも \(T_j\) の昇順にソートします。
ただし、出力は入力順に行う必要があるため、元のクエリ番号を保存しておきます。

Fenwick Tree には、現在のクエリの日付 \(T\) までに修復済みの書棚の利益だけを入れます。

処理の流れは以下の通りです。

1. 書棚を \(D_i\) の昇順にソートする
2. クエリを \(T_j\) の昇順にソートする
3. Fenwick Tree を空で用意する
4. 書棚リストの先頭を指すポインタ \(p\) を用意する
5. クエリを日付の昇順に処理する
   • まだ追加していない書棚のうち、\(D_i \leq T_j\) を満たすものをすべて Fenwick Tree に追加する
   • Fenwick Tree で区間 \([L_j, R_j]\) の和を求める
   • 答えを元のクエリ番号の位置に保存する
6. 最後に答えを入力順に出力する

Fenwick Tree では、位置 \(i\) に値 \(W_i\) を追加し、区間和

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

によって \([L, R]\) の合計を求めます。

計算量

• 時間計算量: \(O(N \log N + Q \log Q + (N + Q) \log N)\)
• 空間計算量: \(O(N + Q)\)

実装のポイント

• 答えは最大で \(2 \times 10^{13}\) なので、int ではなく long long を使います。

• \(A_i \times V_i\) も long long で計算します。

• Fenwick Tree は 1-indexed で扱うと、書棚番号 \(1, 2, \ldots, N\) と対応して実装しやすいです。

• クエリをソートすると入力順が崩れるため、元のクエリ番号 id を保存しておきます。

• 条件は \(D_i \leq T_j\) です。第 \(D_i\) 日目を含むので、比較は < ではなく <= にします。

  ソースコード

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

---

この解説は gpt-5.5-xhigh によって生成されました。