题目分析

维护一个怪物集合，支持动态添加、删除，查询前 $g$ 层中等级 $\le l$ 且难度 $\le d$ 的所有怪物，求击杀这些怪物的最小初始血量。

---

核心思路

1. 怪物击杀顺序优化

关键观察：怪物可以分为两类：

• 净收益型：$b \ge a$（打完后血量增加或不变）
• 净消耗型：$b < a$（打完后血量减少）

最优顺序：

1. 先打所有净收益型怪物，按 $a$ 从小到大（消耗小的先打）
2. 再打所有净消耗型怪物，按 $b$ 从大到小（回血多的后打）

2. 初始血量计算

对于怪物集合 $S$，按最优顺序排列后，初始血量 $H$ 需满足：

$$H \ge \max_{1\le k\le |S|} \sum_{i=1}^k (a_i - b_i) $$

即 $H = -\min(\text{前缀和})$

---

算法实现详解

1. 数据结构设计

怪物信息

struct node {
    int x, y, z, a, b, num;  // 层数,等级,难度,消耗,回血,编号
};

查询信息

struct ask {
    int x, y, z, tim;  // 层数上限,等级上限,难度上限,时间
};

状态节点

struct Node {
    ll Min, sum;  // 最小前缀和,总和
};

2. 分块处理

将怪物分成大小为 $B=14$ 的块：

int B = 14;
for (int i = 1; i <= n; i += B)
    solve(i, min(n, i + B - 1));

3. 块内预处理

状态压缩DP

for (int i = 1; i < (1 << (r-l+1)); i++) {
    int x = i - low(i), y = Lg2[low(i)] + l;
    f[i] = merge((Node){-a[y].a, a[y].b - a[y].a}, f[x]);
}

预处理所有子集的最优顺序对应的 $(Min, sum)$。

前缀和优化

for (int i = l; i <= r; i++)
    X[a[i].x] |= (1 << (i-l));  // 位掩码记录

for (int i = 1; i <= 10000; i++)
    X[i] |= X[i-1];  // 前缀或

快速得到满足 $x \le g$ 的怪物集合。

4. 时间线处理

vector<op> now;
for (int i = l; i <= r; i++) {
    now.pb((op){1, beg[a[i].num], i-l});  // 添加事件
    now.pb((op){2, nd[a[i].num], i-l});   // 删除事件
}
sort(now.begin(), now.end(), Cmp);  // 按时间排序

维护当前活跃的怪物集合 state，对每个查询：

ans[i] = merge(ans[i], f[state & X[Q[i].x] & Y[Q[i].y] & Z[Q[i].z]]);

---

关键函数详解

怪物排序

bool cmp(node x, node y) {
    if (sgn(x.b-x.a) == sgn(y.b-y.a)) {
        if (sgn(x.b-x.a)) 
            return x.a < y.a;      // 收益型：消耗小的优先
        return x.b > y.b;          // 消耗型：回血多的优先
    } else 
        return sgn(x.b-x.a) > sgn(y.b-y.a);  // 收益型先于消耗型
}

状态合并

Node merge(Node x, Node y) {
    return (Node){
        min(x.Min, x.sum + y.Min),  // 更新最小前缀和
        x.sum + y.sum               // 更新总和
    };
}

---

复杂度分析

• 预处理：$O(\frac{n}{B} \cdot 2^B)$，$B=14$ 时 $2^{14}=16384$ 可接受
• 查询：$O(q \cdot \frac{n}{B})$，每个查询处理所有块
• 总复杂度：$O(\frac{n}{B} \cdot (2^B + q))$，对于 $n,q \le 50000$ 可接受

---

算法标签

主要算法：

• 分块
• 状态压缩DP
• 位运算优化

相关技术：

• 离线处理
• 前缀和优化
• 贪心排序

---

代码亮点

1. 分块处理：将大问题分解为可处理的小块
2. 状态压缩：用位掩码表示怪物子集
3. 前缀或：快速计算满足范围条件的怪物集合
4. 时间线扫描：统一处理添加删除操作
5. 最优性证明：严格的怪物击杀顺序保证解最优

---

总结

这道题通过分块+状态压缩的巧妙结合，解决了动态怪物集合的最优击杀问题。核心在于：

• 将怪物按净收益/消耗分类并排序
• 分块预处理所有子集的血量需求
• 利用位运算快速响应多维范围查询

算法在时间复杂度和实现复杂度之间取得了良好平衡，能够高效处理大规模输入。