10.5 神秘最小生成树

· · 个人记录

T4

这道题稍微分析一下，我们不难发现，所有边排序处理一边肯定不行。那么我们不妨将这些区间[L_i,R_i]当作一个单位去处理。这个最小生成树的所有点都可以用kruskal算法处理。

但是这道题的难点就在于处理区间。既要统计不同连通块，又要完成合并操作。如何优化？

可以考虑set来维护各个区间，每次加边，就查询左端点所处区间和右端点所处区间，把这些区间删除，再添加⼀个合并后的区间即可

时间复杂度为O(qlogn)