D. Berserk Monsters 题解

1. 题目回顾

有 $n$ 个怪物排成一排，第 $i$ 个怪物攻击力为 $a_i$，防御力为 $d_i$。战斗共进行 $n$ 轮，每轮：

• 每个存活怪物对左右最近的存活怪物各造成等于其攻击力的伤害；
• 若某个存活怪物本回合受到的伤害之和严格大于 $d_i$，则死亡。

要求输出每轮死亡的怪物数量。

$n \le 3\times 10^5$，$\sum n \le 3\times 10^5$。

2. 关键观察

暴力模拟每一轮遍历所有怪物会达到 $O(n^2)$，不可行。观察到以下性质：

• 只有上一轮死亡怪物左右的存活怪物，在本轮受到的伤害才会发生变化。因为其他存活怪物的左右最近存活邻居并没有改变，它们受到的伤害总和与上一轮相同（如果它们上一轮没死，本轮依然不会死，除非防御值会变化，但防御值固定）。
• 因此，我们只需维护一个待检查集合，初始时包含所有怪物。每一轮，我们只检查待检查集合中的怪物，判断它们是否会死亡。死亡的怪物从存活集合中移除，并将它们左右最近的存活怪物加入下一轮的待检查集合。

由于每个怪物最多死亡一次，每一轮检查的怪物总数不超过 $n$ + 死亡怪物数，所以总检查次数是 $O(n)$ 级别。

3. 算法流程

使用两个 set<int> 结构：

• lft：存放所有存活怪物的下标（包括虚拟边界 $0$ 和 $n+1$）。
• cur：存放本轮需要检查的怪物下标。

初始时，lft 包含 $0,1,2,\dots,n,n+1$，cur 包含 $1,2,\dots,n$。

模拟 $n$ 轮（或直到没有死亡怪物发生为止，但题目要求输出 $n$ 个整数，即使后面几轮为 $0$ 也要输出）：

1. 创建一个集合 del 记录本轮死亡的怪物，ncur 记录下一轮要检查的怪物（即死亡怪物左右最近的存活邻居）。
2. 遍历 cur 中的每个下标 $i$：
   • 在 lft 中找到 $i$ 的位置，获取其左邻居 prv 和右邻居 nxt。
   • 计算 $i$ 受到的伤害总和 $damage = a_{prv} + a_{nxt}$（注意边界 $0$ 和 $n+1$ 的 $a$ 值设为 $0$，这样边界不造成伤害；标程中边界设置为 $0$ 的辅助值）。
   • 如果 $damage > d_i$，则将 $i$ 加入 del，同时将 prv 和 nxt 加入 ncur（前提是它们是合法怪物下标，即 $1\le \text{prv},\text{nxt}\le n$）。
3. 输出 del.size()。
4. 从 lft 中删除 del 中的所有下标。
5. 更新 cur = ncur（为下一轮准备）。

重复上述过程 $n$ 次，即使中途 cur 为空，后续输出均为 $0$。

4. 复杂度分析

• 每个怪物最多进入 cur 常数次（死亡时其邻居入队，邻居最多两个）。总检查次数为 $O(n)$。
• 每次检查涉及 set 的查找、前后元素获取，复杂度 $O(\log n)$。
• 总体时间复杂度 $O(n \log n)$，在 $n$ 总和 $3\times 10^5$ 内完全可行。
• 空间复杂度 $O(n)$。

5. 代码实现（附注释）

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        // 多开两个位置给边界哨兵，a[0]=a[n+1]=0, d[0]=d[n+1]=无穷大
        vector<int> a(n + 2, 0), d(n + 2, INT_MAX);
        for (int i = 1; i <= n; ++i) cin >> a[i];
        for (int i = 1; i <= n; ++i) cin >> d[i];
        
        set<int> alive, check;
        // 初始化存活集合和待检查集合
        for (int i = 0; i <= n + 1; ++i) {
            alive.insert(i);
            if (1 <= i && i <= n) check.insert(i);
        }
        
        for (int round = 0; round < n; ++round) {
            set<int> dead, next_check;
            for (int i : check) {
                auto it = alive.find(i);
                if (it == alive.end()) continue; // 已经死了
                
                int prv = *prev(it);
                int nxt = *next(it);
                // 计算受到的伤害
                long long damage = (long long)a[prv] + a[nxt];
                if (damage > d[i]) {
                    dead.insert(i);
                    // 将左右存活邻居加入下一轮检查（仅当它们是有效怪物）
                    if (prv >= 1) next_check.insert(prv);
                    if (nxt <= n) next_check.insert(nxt);
                }
            }
            cout << dead.size() << " \n"[round == n - 1];
            // 删除死亡怪物
            for (int x : dead) alive.erase(x);
            check = next_check;
        }
        // 注意上面循环内已输出换行，若输出格式需要每行末尾空格也无妨
    }
    return 0;
}

6. 总结

本题通过维护“待检查”集合，将每轮模拟的复杂度从 $O(n)$ 降至 $O(\text{死亡怪物数})$，并利用 set 快速定位左右邻居，总体效率足以通过大数据限制。这种“只检查可能发生状态变化的元素”的优化思想在模拟类题目中非常常见，值得掌握。