UOJ Logo zx2003的博客

博客

关于第284题快乐游戏鸡的疑惑

2017-05-17 22:41:30 By zx2003

vfk的官方题解提供了一种单调队列合并的做法（解法5-2），但给的复杂度式子是O(n+qlogn)，也就是说预处理时间是O(n)。我不太理解。 然后我想了一种构造方法：对于n个点的树，根的左儿子是一条长为n/2-1的链，右儿子则递归处理。然后每个点的w值赋成其深度。 这样，根据xllend3大爷的代码，每次合并至少是O(轻儿子的单调队列长度之和）。 所以，对于这种树，我们有f(n)=f(n/2)+n/2=f(n/2)+O(n),所以f(n)=O(nlogn) 那么，为什么预处理时间是O(n)，我错在哪里？

评论

cnyali_lk
f(n)=f(n/2)+n/2=f(n/4)+n/2+n/4=....=n/2+n/4+n/8+.....=n f(n)=O(n) （听听就好）
zhouyi
$f(n) = f(\frac n 2) + O(n) = O(n)$
immortalCO
每个节点的单调队列（应该是单调栈？）长度是 O(最深的深度) 的，因为同一个深度的节点只会在单调栈中保存一个最大的 而长链剖分后，每一条长链都只会在顶端被遍历一次（这里等价于 for 一边单调栈，单调栈的大小不超过最深的深度 = 长链长度），而每个点属于且仅属于一条长链，因此每条长链的长度之和是 N，因此总复杂度是 O(N)。 // 并不需要用什么 T(n) = ... 的分析啊。。。

发表评论

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

Server time: 2024-04-19 12:09:37