【BZOJ 3551】[ONTAK2010] Peaks加强版

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=3551
神犇题解:http://blog.csdn.net/popoqqq/article/details/41348785

解题报告

这题强制在线,所以不能直接上启发式合并
或者强行可持久化也可以?
不过我们有更加优美的东西:Kruskal重构树

就是按照边权排序,然后做Kruskal
如果需要加边,那么我们新建一个结点,权值设为这条边的权值
然后把原来的两个点连到这个点下面当儿子
于是任意两点之间的最大边权就是他们的LCA的权值了

对于原题来讲,我们可以先倍增到最浅的可以到达的祖先
那么这个祖先的子树就是可以到达的所有点了
考虑DFS序,问题变为区间k大,这是主席树的经典应用
于是这题就做完啦!

今天上午考试考了一道类似的题目,然而忘了这个做法
是用的线段树合并+标记永久化,虽然能A但显然不如这个优雅

2 thoughts to “【BZOJ 3551】[ONTAK2010] Peaks加强版”

  1. Hello there! This is kind of off topic but I need some guidance from an established blog. Is it very hard to set up your own blog? I’m not very techincal but I can figure things out pretty quick. I’m thinking about making my own but I’m not sure where to begin. Do you have any points or suggestions? Thank you

发表评论

电子邮件地址不会被公开。 必填项已用*标注