Related
In following contests:
塔子哥所在的国家有 n 个城市,这 n 个城市排成一列,按顺序编号为 1,2,3,...,n。然而,由于历史原因和地理条件等多种原因,这些城市之间并没有相互连接的铁路,导致交通十分不便。
为了改善这种情况,政府决定修建一些铁路来提高城市之间的交通效率。具体来说,政府计划在未来的 T 天内进行一系列铁路建设工作。每一天,政府会进行如下操作之一:
考虑将n个城市看成图上的n个节点。那么
具体的,假设要合并的两个集合为x,y , 显然有max(x∪y)=max(max(x),max(y)),最小值同理. 所以要在合并集合的过程中维护最值。我们只需要取两者的最值即可完成计算。
In following contests: