因为是求最小生成树，所以我们可以将 mex 改写成任意未出现过的非负整数。按照边权从小到大考虑，则每次是将不包含 $x$ 的所有区间合并。维护每个连通块中区间的最小右端点和最大左端点，即可快速找到需要合并的区间。
时间复杂度 $O(n\log n)$。
QOJ.ac
QOJ
As we are currently experiencing an overwhelming number of web requests for fetching user submissions, we have temporarily disabled the full submissions list. You must now be logged in to view submissions.
Discussion #369 for Problem #14431. Yet Another MST Problem
Type: Editorial
Status: Open
Posted by: jiangly
Posted at: 2025-12-14 07:26:41
Last updated: 2025-12-14 07:26:45
题解
Comments
No comments yet.