题解：P16545 [EGOI 2026] 狐狸家族 / Fox Families

流水行船CCD · 2026-07-26 22:29:08 · 题解

脑子在哪里。

问题相当于：完全图连通块数量，仅加边。

将边的边权记作这条边被加入的时间，不难发现只有最小生成树边有贡献。

两种思路：Boruvka 和 Kruskal。

两种方法都是直接上 ds 就能做的，但是 Boruvka 我没写，这里就只提一下 Kruskal。

考虑并查集维护当前时刻连通块，当合并两个并查集的时候启发式的把较小连通块的父亲修改，这样子就能维护出每个点所属的连通块（下文称作点的颜色，颜色相同位于同一连通块），相当于需要每次找到颜色不同且边权最小的点对连边，支持单点改颜色。

按时间加入每个区间，考虑区间 [l,r] 能和那些区间连边： [l',r'] \subseteq [l,r] 或 [l,r] \subseteq [l',r']。区间的包含相离是经典 ds 问题。下文讨论 [l,r] \subseteq [l',r'] 的情况，另一种情况类似。将区间记在左端点上，相当于每次在左端点位于 [1,l] 中找 r' 最大的区间，维护区间最大值即可，由于需要满足颜色不同，还需维护区间中与最大值颜色不同的次大值。可以看见另一种情况就是维护最小值。

注意 l 端点相同的需特殊处理，我是在线段树的每个叶子上再开一个内层线段树实现的。

可以看见这个做法完全不吃操作啊，主要是 ds 操作都简单，重复且模板，所以很快就能写完。