BZOJ2733 [HNOI2012] 永无乡


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

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


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

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

 

 

声明:zgz233|版权所有,违者必究|如未注明,均为原创|本网站采用BY-NC-SA协议进行授权

转载:转载请注明原文链接 - BZOJ2733 [HNOI2012] 永无乡


一个oier的博客 |注册功能过几天就修| 博客搬家啦,现在跑的飞快!

标签: , ,