资讯详情

考虑使用线段树合并维护连通块颜色个数信息。
莫队，考虑每次加入一条边，这会导致两个连通块的合并。删除不太好做，做回滚莫队。
现在问题是左端点的撤回可能复杂度是不对的，但是你考虑 \(l\) 撤销的代价不会超过 \([l+1,n-1]\) 这个区间插入 \(l\) 的代价，且这个代价总和根据节点个数均摊是 \(O(n\log n)\) 的。
按照代价带权分块，时间复杂度 \(O(n\sqrt n\log n)\)。

• P6580 [Ynoi2019] 美好的每一天~ 不连续的存在。