上次有人说这种做法常数大,其实好像并不是。
我们的线段树只需要两种操作:
单点赋值修改
维护区间最值
但是维护区间最值一定是维护所有元素的最小值,因此时间复杂度为 $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)$。应该是能跑到飞起的。