"平衡树启发式分离 $n$ 个元素的时间复杂度也是 $O(nlogn)$ 的”需要每次分离的集合都是有序的。
然后在本题中，每次分离的集合A并不是有序的，如果直接用快排，那复杂度为$AlogA$，于是复杂度变成了$O(nklog^2n)$。
这可咋办？
zx2003的博客
博客
关于 新年的族谱树 一题的一个问题
2019-02-11 21:26:23 By zx2003
评论
AwD
…… 可以直接在平衡树上排序哇：
首先在平衡树上，对于每个要删除的节点，把在从它到根的链上的所有节点都打个标记。
然后直接DFS被标记过的节点，按顺序记录下需要删除的节点，这样就排好序了～
由于被标记的节点肯定在删除的过程中会被访问到，这个东西的复杂度显然是严格不高于删除的复杂度的 …… 于是复杂度它就对了！
不过话说回来，sort 实际上是非常快的，写那么麻烦干什么 233
- 2019-02-12 12:07:14
发表评论
可以用@mike来提到mike这个用户，mike会被高亮显示。如果你真的想打“@”这个字符，请用“@@”。
- Universal Online Judge |
鄂公网安备 42010202000505 号 |- 鄂ICP备 14016048 号
Server time: 2024-11-24 04:15:29