Energy stones - 题解

标签与难度

标签: 扫描线, 数据结构, 树状数组, 集合, 差分思想, 离线处理难度: 2200

题目大意喵~

你好呀，未来的算法大师！我是你们的向导我，今天我们要解决一个关于能量石的有趣问题，喵~

森林里有 $N$ 颗能量石，编号从 1 到 $N$ 。每颗能量石 $i$ 都有三个属性：

初始能量 $E_i$
每秒能量增长率 $L_i$
能量上限 $C_i$

这意味着，在没有被吸收的情况下，能量石 $i$ 在 $t$ 秒后的能量是 $\min(C_i, E_i + L_i \times t)$ 。

我们的大胃王CNZ要进行 $M$ 次能量吸收。第 $j$ 次吸收发生在 $t_j$ 秒，吸收的是一个连续区间 $[S_j, T_j]$ 内所有能量石的能量。一旦被吸收，这些能量石的能量就会瞬间归零，然后从 0 开始重新以每秒 $L_i$ 的速率增长。

我们的任务是计算出经过这 $M$ 次吸收后，CNZ总共获得了多少能量，喵~

解题思路分析

这道题看起来有点复杂，因为每块石头的能量状态都在不断变化，直接模拟肯定会超时呢。所以，我们需要换个角度思考，喵~

不以时间顺序来处理每一次吸收，我们换个主角，来关注每一颗能量石的“一生”。对于第 $i$ 颗能量石，它对总答案的贡献是多少呢？

它的贡献就是它在每次被吃掉的瞬间所含有的能量总和。

假设对于第 $i$ 颗能量石，所有会吃到它的操作的发生时间点，按从小到大排序后是 $t_1, t_2, \dots, t_p$ 。

在第一次被吃掉的 $t_1$ 时刻，它从第 0 秒开始积攒能量，所以它的能量是 $\min(C_i, E_i + L_i \cdot t_1)$ 。
在第二次被吃掉的 $t_2$ 时刻，它从上一次被吃掉的 $t_1$ 时刻能量归零后开始积攒，经过了 $t_2 - t_1$ 秒。所以这次贡献的能量是 $\min(C_i, 0 + L_i \cdot (t_2 - t_1))$ 。
同理，第 $k$ 次（ $k > 1$ ）被吃掉时，贡献的能量是 $\min(C_i, L_i \cdot (t_k - t_{k-1}))$ 。

所以，第 $i$ 颗石头贡献的总能量就是：

\text{TotalEnergy}_i = \min(C_i, E_i + L_i \cdot t_1) + \sum_{k=2}^{p} \min(C_i, L_i \cdot (t_k - t_{k-1}))

这个思路很棒，但是对每颗石头都找出所有相关的操作时间、排序、再计算，还是太慢啦。不过，我们注意到了一个关键点：当我们从第 $i$ 颗石头移动到第 $i+1$ 颗石头时，那个吃掉它的操作时间集合（也就是 $t_1, t_2, \dots, t_p$ ）变化是很小的！只有那些刚好以 $i$ 为终点或者以 $i+1$ 为起点的操作才会影响这个集合。

这不就是扫描线的思想嘛！我们可以把石头的编号 $1, 2, \dots, N$ 看作一条数轴，从左到右扫描。

我们维护一个“当前活跃”的吃操作时间集合。当我们扫描到石头 $i$ 时，这个集合就包含了所有会吃掉石头 $i$ 的操作的时间点。

事件点: 对于每个操作 $(t_j, S_j, T_j)$ ，我们可以看作在数轴的 $S_j$ 位置发生了一个“开始”事件（把 $t_j$ 加入活跃集合），在 $T_j+1$ 位置发生了一个“结束”事件（把 $t_j$ 从活跃集合中移除）。
数据结构: 我们需要一个能动态维护这个时间集合，并支持快速计算上面那个总和公式的数据结构。
- 为了维护有序的时间点集合并支持快速增删，std::set 是个完美的选择，喵~ 它可以自动保持时间的有序性。
- 接下来是处理 $\sum_{k=2}^{p} \min(C_i, L_i \cdot (t_k - t_{k-1}))$ 这个求和。令时间差 $\Delta t_k = t_k - t_{k-1}$ ，我们需要计算 $\sum \min(C_i, L_i \cdot \Delta t_k)$ 。这个式子可以拆成两部分：
  - 当 $\Delta t_k < C_i / L_i$ 时，贡献是 $L_i \cdot \Delta t_k$ 。
  - 当 $\Delta t_k \ge C_i / L_i$ 时，贡献是 $C_i$ 。
  令阈值 $T_{\text{cap}} = C_i / L_i$ (如果 $L_i=0$ 则阈值为无穷大)。我们想要求的就是：
  $L_i \times \sum_{\Delta t < T_{\text{cap}}} \Delta t + C_i \times \sum_{\Delta t \ge T_{\text{cap}}} 1$
  这需要我们能快速查询所有小于某个阈值的时间差的总和，以及大于等于某个阈值的时间差的个数。这正是树状数组 (Fenwick Tree) 的拿手好戏！
  我们可以用两个树状数组：
  - bit_count: 维护每个时间差值出现的次数。
  - bit_sum: 维护每个时间差值的总和。
算法流程:
- 预处理: 创建一个事件列表。对于每个操作 $(t_j, S_j, T_j)$ ，在 $S_j$ 处添加一个“加入 $t_j$ ”的事件，在 $T_j+1$ 处添加一个“移除 $t_j$ ”的事件。
- 扫描: 从 $i=1$ 到 $N$ 遍历所有石头： a. 处理第 $i$ 个位置的所有事件，更新 std::set 和两个树状数组。比如，要加入一个时间 $t$ ，我们先在 set 中找到它的前驱 prev_t 和后继 next_t。这会破坏掉原来的时间差 next_t - prev_t，并产生两个新的时间差 t - prev_t 和 next_t - t。我们在树状数组中进行相应的更新。删除操作同理。 b. 当 set 更新完毕后，我们就有了针对石头 $i$ 的所有活跃时间差。利用树状数组快速计算出石头 $i$ 的总贡献，累加到最终答案里。
- 最后输出总答案就好啦！

这样一来，我们把一个复杂的动态问题，转化成了一个有序的、可以用高效数据结构维护的扫描线问题，是不是很巧妙呀？喵~

代码实现

这是我根据上面的思路，精心重构的一份代码~ 每个细节都加了注释，希望能帮助你理解呐！

cpp

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

using namespace std;

// 使用 long long 防止能量总和溢出
using ll = long long;

const int MAX_TIME = 200005; // 时间和时间差的最大可能值

// 树状数组 (Fenwick Tree) 的模板，喵~
struct FenwickTree {
    vector<ll> tree;
    int size;

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

    void update(int idx, ll delta) {
        for (; idx <= size; idx += idx & -idx) {
            tree[idx] += delta;
        }
    }

    ll query(int idx) {
        ll sum = 0;
        for (; idx > 0; idx -= idx & -idx) {
            sum += tree[idx];
        }
        return sum;
    }
};

// 石头的属性
struct Stone {
    ll E, L, C;
};

// 全局变量，方便管理
int N, M;
vector<Stone> stones;
vector<vector<pair<int, int>>> events; // 事件列表
set<int> active_eat_times; // 活跃的吃操作时间集合
FenwickTree bit_count(MAX_TIME);
FenwickTree bit_sum(MAX_TIME);

// 在树状数组中更新一个时间差
void update_diff(int diff, int sign) {
    bit_count.update(diff, sign);
    bit_sum.update(diff, (ll)sign * diff);
}

// 向活跃集合中添加一个时间点
void add_time(int t) {
    active_eat_times.insert(t);
    auto it = active_eat_times.find(t);
    auto prev_it = (it == active_eat_times.begin()) ? active_eat_times.end() : prev(it);
    auto next_it = next(it);

    if (prev_it != active_eat_times.end() && next_it != active_eat_times.end()) {
        // 插入到中间，破坏一个旧差，产生两个新差
        update_diff(*next_it - *prev_it, -1);
        update_diff(t - *prev_it, 1);
        update_diff(*next_it - t, 1);
    } else if (prev_it != active_eat_times.end()) {
        // 插入到末尾
        update_diff(t - *prev_it, 1);
    } else if (next_it != active_eat_times.end()) {
        // 插入到开头
        update_diff(*next_it - t, 1);
    }
}

// 从活跃集合中移除一个时间点
void remove_time(int t) {
    auto it = active_eat_times.find(t);
    auto prev_it = (it == active_eat_times.begin()) ? active_eat_times.end() : prev(it);
    auto next_it = next(it);
    
    active_eat_times.erase(it);

    if (prev_it != active_eat_times.end() && next_it != active_eat_times.end()) {
        // 移除中间的，破坏两个旧差，产生一个新差
        update_diff(t - *prev_it, -1);
        update_diff(*next_it - t, -1);
        update_diff(*next_it - *prev_it, 1);
    } else if (prev_it != active_eat_times.end()) {
        // 移除末尾的
        update_diff(t - *prev_it, -1);
    } else if (next_it != active_eat_times.end()) {
        // 移除开头的
        update_diff(*next_it - t, -1);
    }
}


void solve(int case_num) {
    cin >> N;
    stones.assign(N + 1, {0, 0, 0});
    for (int i = 1; i <= N; ++i) {
        cin >> stones[i].E >> stones[i].L >> stones[i].C;
    }

    cin >> M;
    events.assign(N + 2, vector<pair<int, int>>());
    for (int i = 0; i < M; ++i) {
        int t, S, T;
        cin >> t >> S >> T;
        events[S].push_back({t, 1});      // 开始事件
        events[T + 1].push_back({t, -1}); // 结束事件
    }
    
    ll total_energy = 0;

    // 开始扫描线~
    for (int i = 1; i <= N; ++i) {
        // 处理当前位置的所有事件
        for (auto const& [time, type] : events[i]) {
            if (type == 1) {
                add_time(time);
            } else {
                remove_time(time);
            }
        }

        if (active_eat_times.empty()) {
            continue; // 这颗石头没人吃，真幸运~
        }

        // 1. 计算第一次被吃时的能量
        int first_eat_time = *active_eat_times.begin();
        total_energy += min(stones[i].C, stones[i].E + stones[i].L * first_eat_time);

        // 2. 计算后续被吃时的能量
        if (stones[i].L == 0 || active_eat_times.size() <= 1) {
            continue; // 如果不增涨能量，或者只被吃一次，就没后续贡献了
        }

        ll T_cap = stones[i].C / stones[i].L;

        // 查树状数组，获取差值信息
        ll sum_small_diffs = 0;
        ll count_small_diffs = 0;
        if (T_cap > 0) {
            sum_small_diffs = bit_sum.query(T_cap);
            count_small_diffs = bit_count.query(T_cap);
        }
        
        ll total_diffs_count = active_eat_times.size() - 1;
        ll count_large_diffs = total_diffs_count - count_small_diffs;

        total_energy += stones[i].L * sum_small_diffs;
        total_energy += stones[i].C * count_large_diffs;
    }
    
    // 清理工作，为下一个测试用例做准备
    active_eat_times.clear();
    // 树状数组也需要重置，最简单的方式就是重新构造
    bit_count = FenwickTree(MAX_TIME);
    bit_sum = FenwickTree(MAX_TIME);

    cout << "Case #" << case_num << ": " << total_energy << endl;
}

int main() {
    // 提高cin/cout效率，喵~
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int T;
    cin >> T;
    for (int i = 1; i <= T; ++i) {
        solve(i);
    }
    return 0;
}

复杂度分析

时间复杂度: $O(N \cdot \log V + M \cdot (\log M + \log V))$
- $N$ 是能量石数量， $M$ 是操作次数， $V$ 是时间的最大值（这里是MAX_TIME）。
- 我们对 $N$ 颗石头进行扫描，这是 $O(N)$ 的外层循环。
- 在循环内部，我们需要处理事件。总共有 $2M$ 个事件，每个事件涉及 std::set 的操作（增、删、查找邻居），这需要 $O(\log M)$ 的时间。同时，每个事件会更新树状数组，需要 $O(\log V)$ 的时间。所有事件处理的总和是 $O(M \cdot (\log M + \log V))$ 。
- 每次扫描到一颗新石头，我们都会对树状数组进行查询，这需要 $O(\log V)$ 。 $N$ 次查询总共是 $O(N \cdot \log V)$ 。
- 所以总时间复杂度就是把这些加起来啦！
空间复杂度: $O(N + M + V)$
- 存储 $N$ 颗石头的属性需要 $O(N)$ 。
- 存储 $M$ 个操作产生的 $2M$ 个事件需要 $O(M)$ 。
- std::set 最多存储 $M$ 个时间点，需要 $O(M)$ 。
- 两个树状数组的大小都和时间最大值 $V$ 相关，需要 $O(V)$ 。
- 所以总空间就是这些部分的总和，喵~

知识点总结

这道题是一个很好的练习，融合了多种算法思想，值得好好回味呢！

离线处理与扫描线: 当问题中的查询可以预先知道，并且按某个维度（本题是石头编号）排序处理会更简单时，就可以考虑离线处理和扫描线。这是一种化动态为静态的强大思想。
差分思想: 问题的核心在于两次被吃之间的“时间差”，而不是绝对时间。抓住这个关键点，可以大大简化问题。
数据结构的组合拳: 单一的数据结构往往难以解决复杂问题。本题巧妙地将 std::set（用于维护有序集合）和树状数组（用于高效区间统计）结合起来，各自发挥长处，最终解决了问题。
树状数组 (Fenwick Tree): 它不仅能求前缀和，还能通过维护差分数组等方式，支持更复杂的区间查询和更新。这里我们用它来统计特定范围内数值的个数和总和，是非常经典的应用。

希望这篇题解能帮到你！继续努力，你一定能成为超厉害的算法大师的，喵~ 加油！

Energy stones - 题解 ​

标签与难度 ​

题目大意喵~ ​

解题思路分析 ​

代码实现 ​

复杂度分析 ​