算法思路

本题需要维护一个动态的图结构，支持添加边、删除最长边和查询最小不公平分数三种操作。关键在于如何高效维护联盟信息并快速计算最小不公平分数。

核心算法

1. 数据结构设计

• 并查集 (DSU)：维护城市之间的连通性，支持路径压缩
• 回滚并查集：记录每次合并操作，支持撤销操作
• 多重集维护：使用桶数组 mp[] 和快速访问数组 q[] 来记录当前所有联盟的大小分布
• 操作分块：将操作分为块处理，平衡时间复杂度和空间复杂度

2. 关键操作实现

添加条约操作

void add(int w, int x, int y) {
    // 使用并查集合并两个城市所在的联盟
    // 更新联盟大小分布
    // 记录操作以便撤销
}

删除最长条约

void del() {
    // 如果最长条约在块内，直接撤销对应操作
    // 如果最长条约在块外，从集合中删除
}

计算最小不公平分数

int get() {
    // 合并块内外所有操作
    // 计算联盟大小分布
    // 贪心配对：尽量让大小相近的联盟配对
    // 撤销临时操作，恢复状态
}

3. 最小不公平分数计算

采用贪心策略：

1. 将联盟按大小排序
2. 如果联盟数量为奇数，让最小的联盟与空联盟配对
3. 剩余联盟两两配对，相邻的两个联盟配对
4. 不公平分数为所有配对的大小差之和

算法标签

• 并查集 (Union-Find)
• 回滚操作 (Rollback DSU)
• 分块思想 (Block Decomposition)
• 贪心算法 (Greedy)
• 离线处理 (Offline Processing)

复杂度分析

• 时间复杂度：$O(Q \sqrt{Q} \alpha(N))$，其中分块大小为 $\sqrt{Q}$
• 空间复杂度：$O(N + Q)$

代码关键点解析

1. 路径压缩优化：在并查集中使用路径压缩加快查找速度
2. 操作记录：st[] 数组记录每次合并操作，支持精确撤销
3. 快速统计：使用桶数组 mp[] 和快速访问数组 q[] 维护联盟大小分布
4. 分块处理：B = 1005 作为分块大小，平衡操作效率

样例验证

对于样例1：

• 初始状态：3个独立城市
• 添加条约后：形成1个大小为3的联盟
• 第一次查询：与空联盟配对，不公平分数为3
• 删除最长条约后：形成两个联盟（大小2和1）
• 第二次查询：两联盟配对，不公平分数为1

该解法通过巧妙的数据结构设计和分块策略，在保证正确性的同时达到了较高的效率，能够处理大规模数据。