题目内容

塔子哥所在的国家有 $n$ 个城市，这 $n$ 个城市排成一列，按顺序编号为 $1,2,3,...,n$。然而，由于历史原因和地理条件等多种原因，这些城市之间并没有相互连接的铁路，导致交通十分不便。

为了改善这种情况，政府决定修建一些铁路来提高城市之间的交通效率。具体来说，政府计划在未来的 $T$ 天内进行一系列铁路建设工作。每一天，政府会进行如下操作之一：

思路:并查集

考虑将$n$个城市看成图上的$n$个节点。那么

• 每次将两个城市之间连通，相当于在点 $u$ 和点 $v$ 之间连一条边
• 每次查询一个城市可以向左和向右到达的最远城市，这启发我们并查集合并时需要维护两个值，一个合并时总是指向值更小的，一个合并时总是指向值更大的。即维护集合最大最小值

具体的，假设要合并的两个集合为$x,y$ , 显然有$max(x \cup y) = max(max(x) , max(y))$,最小值同理. 所以要在合并集合的过程中维护最值。我们只需要取两者的最值即可完成计算。

知识点学习：并查集