线段树合并一次的复杂度是什么？ - 洛谷

版块P3224 [HN...
楼主LonelinessMan
发帖时间2018-12-12 13:43
题目P3224 [HNOI2012]永无乡

@LonelinessMan 2018-12-12 13:43 回复

不是最坏O(NlogN)吗为什么不会超时。。。

@LonelinessMan 2018-12-12 13:47 回复举报

均摊O（logn）吗？

@Mr_Spade 2018-12-12 13:53 回复举报

是啊

@LonelinessMan 2018-12-12 13:59 回复举报

奥谢谢

@Fading 2018-12-12 14:06 回复举报

最多nlog，均摊nlog

@shadowice1984 2018-12-12 14:19 回复举报

@Fading @LonelinessMan

为啥最坏复杂度是$O(nlogn)$啊难道不是$O(n)$吗……

不是很懂两棵线段树哪里来的$O(nlogn)$级别的节点数……

@Fading 2018-12-12 14:50 回复举报

@shadowice1984 哦我说的是最多"总共"ologn，我可能说得有一点不清楚

@Fading 2018-12-12 14:50 回复举报

@shadowice1984 第一句话无视好了qwq

@LonelinessMan 2018-12-12 18:07 回复举报

@shadowice1984 加上线段树分裂，那合并的复杂度不就不能保证了吗？