UOJ Logo zx2003的博客

博客

关于 新年的族谱树 一题的一个问题

2019-02-11 21:26:23 By zx2003

题目链接

官方题解链接

"平衡树启发式分离 $n$ 个元素的时间复杂度也是 $O(nlogn)$ 的”需要每次分离的集合都是有序的。

然后在本题中,每次分离的集合A并不是有序的,如果直接用快排,那复杂度为$AlogA$,于是复杂度变成了$O(nklog^2n)$。

这可咋办?

评论

AwD
…… 可以直接在平衡树上排序哇: 首先在平衡树上,对于每个要删除的节点,把在从它到根的链上的所有节点都打个标记。 然后直接DFS被标记过的节点,按顺序记录下需要删除的节点,这样就排好序了~ 由于被标记的节点肯定在删除的过程中会被访问到,这个东西的复杂度显然是严格不高于删除的复杂度的 …… 于是复杂度它就对了! 不过话说回来,sort 实际上是非常快的,写那么麻烦干什么 233

发表评论

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