luoguP3224 [HNOI2012]永无乡

原题传送门 >Here<

平衡树+启发式合并。

建桥就相当于合并两棵平衡树,查询时查找树中第K小就可以了。

于是只剩下如何合并两棵平衡树的问题了。话说这道题真的很玄学,我本来以为有一种不明觉厉的方法可以迅速整体合并两棵平衡树,但是想了很久也没有想出来。看了各位dalao的博客才发现原来可以暴力把一棵平衡树的点全部拆出来插入到另一棵树上,并且每次合并两棵树时选取节点数少的树拆,据说这样可以保证每个点最多更新logn次(也就是启发式合并)。

然后就可以过了。。。

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×