UOJ Logo kczno1的博客

博客

求助。。关于快乐游戏鸡题解的不懂的地方

2017-01-28 11:13:27 By kczno1

"然后树链剖分以后对于每个点,首先把它的重儿子的线段树拉过来更新一下,然后对于它的每个轻儿子的重链(注意不是轻儿子的子树,否则可能复杂度会多一个log有卡常风险)对应的线段树拉过来更新当前点的线段树就好了。"
为什么可以不把轻儿子的子树拿过来,而是拿轻儿子的重链。。
为什么时间只有一个log。。
upd: 好吧,我应该想通了。
1 按深度的轻重链剖分+选取重儿子,合并轻儿子就是启发式合并
2 两者总时间都是nlogn

证明:

一个点的子树的线段树的元素个数最多只有它子树的深度。

假设所有点的子树的线段树的元素个数=子树的深度,那么实际情况不会 更差.

这样就可以按深度的轻重链剖分+选取重儿子了。

由于每条链只有在top处被拿去合并,所以每条链只被合并了一次。

所以合并总个数O(n),所以总时间O(nlogn)

同时,我们可以发现,启发式合并不会比它更差。

评论

jiazihankk
个人认为这里的轻重链刨分按深度来更好 可参考类似题:bzoj4543: [POI2014]Hotel加强版 的题解 至于“为什么可以不把轻儿子的子树拿过来”,可参考yveh神犇的博客:http://blog.csdn.net/qaq__qaq/article/details/53455462 这样不算线段树,一个O(n),一个O(nlogn) (有概率想错...)
matthew99
写我的做法吧,又简单复杂度又有保证
qcw
@vfk
kczno1
好吧,我应该想通了。 1 按深度的轻重链剖分+选取重儿子,合并轻儿子就是启发式合并 2 两者总时间都是nlogn 证明: 一个点的子树的线段树的元素个数最多只有它子树的深度。 假设所有点的子树的线段树的元素个数=子树的深度,那么实际情况不会 更差。 这样就可以按深度的轻重链剖分+选取重儿子了。 由于每条链只有在top处被拿去合并,所以每条链只被合并了一次。 所以合并总个数O(n),所以总时间O(nlogn) 同时,我们可以发现,启发式合并不会比它更差。
LiuYu_penguin
@kcznol 请问此题的官方题解在哪里能找到呀,萌新初来乍到翻了半天没找到/kk
LiuYu_penguin
@kcznol

发表评论

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