在许多信息学竞赛问题中，往往复杂度瓶颈在于排序（例如虚树按照 $\texttt{dfn}$ 排序时），能否优化至线性呢？

可以类似桶排序的思路做到单组 $\mathcal{O}(n+V)$，但是这显然太耗时间了，发现桶排序扫描的过程需要执行 $T$ 次，而 $\mathcal{O}(n)$ 却是不可避免的，所以考虑优化扫描桶的过程。

阅读更多……