BZOJ2733 [HNOI2012] 永无乡

发布于 2017-09-21  155 次阅读


题目链接:http://www.lydsy.com/JudgeOnline/submitpage.php?id=2733

题意:带加边询问连通块第 k 小。


对应每一个连通块维护一棵 splay,查询第 k 小是容易的。连通性可以并查集维护。

加边的过程合并了两颗 splay,这个时候上启发式合并复杂度就保证了。当然,数据结构可以换成别的,写 splay 是为了练习一下...

 

 


一个非常弱的准退役OIER