UOJ Logo Euler_function的博客

博客

关于某个排序的再度思考

2024-03-27 19:44:27 By Euler_function

原博客

上次有人说这种做法常数大,其实好像并不是。

我们的线段树只需要两种操作:

  1. 单点赋值修改

  2. 维护区间最值

但是维护区间最值一定是维护所有元素的最小值,因此时间复杂度为 $O(1)$。

单点赋值修改时间复杂度为 $O(\log n)$。

因为 $n$ 次查询,总时间复杂度 $O(n \log n)$。

这样常数应该是小于 $1$ 的。

下面的部分是我还没有完全确定的,如果写错了不要喷,我太菜了。

一个小优化

考虑维护最后一个队列,然后一个队列空了就把最后一个队列队首移过来,理论上应该是可以有一些效率提升的。但是我目前比较忙,还没把代码写完,还没测试。

但是求逆序对不能加这个优化。

逆序对

这种排序应该是可以求逆序对的,因为每个队列单调,并且每个队列都在原数列里连续,因此在求出最小值的时候,在该队列前面所有队列的 size 之和就是当前元素对逆序对数的贡献,可以写个树状数组维护,每个数时间复杂度 $O(\log n)$,总时间复杂度 $O(n \log n)$。

然后这种排序应该最好是 $O(n)$,平均 $O(n \log n)$,最坏 $O(n \log n)$。应该是能跑到飞起的。

Euler_function Avatar