题解：P9067 [Ynoi Easy Round 2022] 虚空处刑 TEST_105

happybob · 2025-07-28 11:21:24 · 题解

将每个极大连通块信息全都记在最浅的那个点上，维护这个连通块的下面连着的点的颜色信息，而不记录父亲信息。维护每种颜色的链表，合并时启发式合并，由于颜色范围很大你需要用个 map 维护每种颜色对应的链表，这样复杂度就是 O(n \log^2 n)，当然我承认确实能过且跑的飞快。一个解决方法是用 unordered_map，不过常数不一定小。

换一个维护方式，map 本质是平衡树。对于下面连着的点维护 (c,i) 的有序集合，c 是颜色，i 是点编号。这样每次定位连通块合并只需要二分找到所有 =c 的那些位置。

启发式合并用 finger search 就是 O(n \log n) 的。