@[noip](/user/3296)
by dead_X @ 2021-09-20 14:59:40
<https://www.luogu.com.cn/problem/P6018>
和这个有关系？
by fjy666 @ 2021-09-20 15:00:29
是dX诶
by 幽灵特工 @ 2021-09-20 15:00:42
不过用融合树做排序突破 $\Omega(n\log n)$ 没有什么用，因为 RS-vEB 和压位 trie 用来排序都比这个强吧。
by 年年有年 @ 2021-09-20 15:03:31
@[年年有年](/user/377973) 基数排序就是线性的吧？
by YamadaRyou @ 2021-09-20 15:05:37
@[WA王子](/user/203008) 我想过这个。很迷惑的一点是，虽然字长 $w=\Theta(\log n)$，那么能否认为 $O(\log_n W)=O(1)$ 呢？$W$ 为值域。
by 年年有年 @ 2021-09-20 15:07:50
@[年年有年](/user/377973) 我记着算导上有鸡排复杂度的证明吧/kk
by YamadaRyou @ 2021-09-20 15:14:24
我看看。
by 年年有年 @ 2021-09-20 15:16:00
按照算导的说法，$O(\dfrac w r(n+2^r))$。看起来 $r=\Theta(\log n)$ 就可以线性排序了。
by 年年有年 @ 2021-09-20 15:23:09
尽管我持怀疑态度，不过还是先用着这个结论吧。这样我的四毛子就 work 了。！
by 年年有年 @ 2021-09-20 15:23:52