UOJ Logo matthew99的博客

博客

快乐游戏鸡LCT做法

2017-01-26 19:40:17 By matthew99

首先你得看了题和题解至少算法二之前的部分。

题解地址:http://vfleaking.blog.uoj.ac/blog/2292

我们把每个询问转化为总和减去大于等于最大权值的部分的后缀和。

接着我们按w从大到小加入点,考虑维护每个点的子树中的最小深度

这个怎么维护呢,考虑一个点肯定是更新它到根的路径,所以我们用类似LCT的access的方法更新,我们可以保证随时每个链的最小深度都相同,如果当前的链的最小深度小于用来更新的值就直接退出,否则的话我们就更新,最后再把这些更新了的链连起来。

复杂度显然是$O((n + m)\log{n})$的,用类似证明LCT复杂度的方法证明即可。

答案也很好算,记录一个后缀和即可,你会发现更新的时候也很好打标记,询问也很好处理。

怎样,是不是只要有模板就好写又好调?而且时间效率还不错呢。

代码:http://uoj.ac/submission/123579

评论

AntiLeaf
我比赛的时候想的是平衡树启发式合并维护子树bfs序+二分。应该也可以吧......?

发表评论

可以用@mike来提到mike这个用户,mike会被高亮显示。如果你真的想打“@”这个字符,请用“@@”。