「联合省选 2020 A | B」冰火战士 题解

问题分析

这个问题需要动态维护冰火战士的报名信息，并实时计算最佳场地温度。关键难点在于：

• 动态更新：支持添加和删除战士
• 温度选择：找到使消耗总能量最大的温度
• 高效查询：$Q \leq 2 \times 10^6$ 需要高效算法

核心算法：树状数组 + 二分

1. 问题转化

对于温度 $x$：

• 冰系战士：所有温度 $\leq x$ 的战士可以参赛
• 火系战士：所有温度 $\geq x$ 的战士可以参赛

消耗的总能量为：

$$\text{总能量} = 2 \times \min\left(\sum_{\text{冰系, 温度} \leq x} \text{能量}, \sum_{\text{火系, 温度} \geq x} \text{能量}\right) $$

2. 数据结构设计

使用两个树状数组分别维护冰系和火系战士：

• bit[0]：冰系战士，按温度升序
• bit[1]：火系战士，按温度升序

每个节点存储：

• c：战士数量
• v：能量总和

3. 关键算法步骤

离散化处理

std::sort(l.begin() + 1, l.end());
l.erase(std::unique(l.begin() + 1, l.end()), l.end());

树状数组更新

for (int j = a[i].x; j <= n; j += lowbit(j))
    bit[a[i].k][j] += node(a[i].op, a[i].op * a[i].y);

二分查找最优温度

for (int i = 20; ~i; --i)
    if (p + (1 << i) <= n && (s0 + bit[0][p + (1 << i)]).v <= (s1 - bit[1][p + (1 << i)]).v)
        p += (1 << i), s0 += bit[0][p], s1 -= bit[1][p];

算法复杂度分析

• 离散化：$O(Q \log Q)$
• 每次操作：$O(\log n)$ 更新树状数组
• 每次查询：$O(\log n)$ 二分查找
• 总复杂度：$O(Q \log Q)$

关键优化技术

1. 二进制分组二分

使用 $2^i$ 步长进行二分，避免递归开销：

for (int i = 20; ~i; --i)
    if (p + (1 << i) <= n && condition)
        p += (1 << i);

2. 同时维护冰火信息

在二分过程中同时计算冰系前缀和与火系后缀和：

• 冰系：$s_0 = \sum_{i \leq p} \text{冰能量}$
• 火系：$s_1 = \sum_{i \geq p} \text{火能量}$

3. 边界情况处理

if (std::min(cnt[0], cnt[1]) == 0)
    std::cout << "Peace\n";

算法标签

🏷️ 主要算法

树状数组 (Fenwick Tree)

• 维护前缀和信息
• 支持动态更新和区间查询

二分查找 (Binary Search)

• 在温度空间中寻找最优解
• 使用二进制分组优化

🏷️ 数据处理

离散化 (Discretization)

• 将温度映射到紧凑区间
• 减少数据规模

离线处理 (Offline Processing)

• 预处理所有温度值
• 建立映射关系

🏷️ 优化技术

二进制优化 (Binary Optimization)

• 使用位运算加速二分过程
• 减少循环次数

双指针技巧 (Two Pointers Technique)

• 同时维护冰火双方信息
• 避免重复计算

🏷️ 问题类型

动态维护问题 (Dynamic Maintenance Problem)

• 支持插入和删除操作
• 实时更新查询结果

最优化问题 (Optimization Problem)

• 寻找最大化目标函数的参数
• 考虑多个约束条件

这个解决方案通过巧妙的树状数组结合二分查找，在 $O(Q \log Q)$ 的时间内解决了大规模动态查询问题，体现了数据结构在解决复杂优化问题中的强大能力。