原博客

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

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

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)$。应该是能跑到飞起的。