我没有做这题，所以复制了 @cjdst 的代码 AC 后才发的题解。不知道帅童介不介意，但是我不介意。此题有三种解法。
1.整体二分。这题是比较一眼的，第一次满足点对连通的答案符合可二分性，我们需要枚举当前 [l,mid][l,mid][l,mid] 这个时间区间内所有加边操作，使用一个并查集判断每个询问中的点对是否满足要求并左右递归，其中 lll 和 midmidmid 分别是整体二分的值域左端点和中间值。这个做法的时间复杂度是 O((n+m)log2(n+m))O((n+m)\log^2(n+m))O((n+m)log2(n+m)) ，其中一个 log\loglog 是可撤销并查集的时间复杂度，因为需要撤销操作。这里需要一个被 cjdst 称为二莫的技巧来维护。
我不会。
我不需要。
我有更优解。
为什么官方题解的思路一样啊（逃）。
注意到 cjdst 的整体二分需要可撤销并查集，但是最懂整体二分的人明显是 Xylophone 而不是 cjdst. 只要把每一层整体二分一起实现，从左到右扫，扫完一层暴力清空，就可以在空间复杂度不变的情况下省去撤销操作。时间复杂度 O((n+m)log(n+m)α(m))O((n+m)\log(n+m)\alpha(m))O((n+m)log(n+m)α(m)).
@hopebetter 为什么是神？祂实现了这个做法。我爱死 hopebetter.
我们要表扬 hb 同志的整体二分精神，但是同时我们也要帮助祂改正明明出整体二分的题却不判紫和不用 Kruskal 重构树的错误。
2.Kruskal 重构树。
这个做法也比较一眼，我们把所有边建成图，边权即是操作的时间，之后建出 Kruskal 重构树，在重构树上求得的 LCA 即是需要的最小时间，因为重构树可以求两点之间路径最大边最小值。由于这个题居然把时间乱序，所以我们需要排序，时间复杂度 O((n+m)log(n+m))O((n+m)\log(n+m))O((n+m)log(n+m)).
3.可持久化并查集。
注意到整体二分的题一般可以用可持久化数据结构。我们可以直接构建可持久化并查集并套一个二分，时间复杂度三个 log\loglog.
代码略略略
