奇妙的思路——[HEOI2016/TJOI2016] 排序

好久没有用这样的模式了，~~说明你偷懒好久了。~~ [[HEOI2016/TJOI2016]排序](https://www.luogu.com.cn/problem/P2824) 题意就不叙述了，见上方链接。 首先转化一下模型。题目要求把序列的一段排序，那可以认为是有若干个有序段（初始时有 $n$ 个单元素的有序段），每次分裂和合并一些有序段，每次分裂的有序段不超过两个（类似珂朵莉树的区间染色）。 于是“平衡树”一类想法马上涌上来，然后……就没有然后了。（当然这题确实有类似平衡树的做法，不过用的不是平衡树，而是权值线段树的分裂和合并。这是因为线段树合并的过程就是销毁重复节点的过程，总时间不超过创建这些节点的时间；但两棵平衡树似乎不能足够快速地合并，因为合并的时候并不保证能销毁节点。详见 [【模板】线段树分裂](https://www.luogu.com.cn/problem/P5494)） 平衡树做不了，那么~~就没法做了~~ 重新看一下题，看看有没有什么蹊跷之处？ 诶，这题为什么只询问一个位置上的元素呢？这是不是意味着，我们并不需要维护**整个序列**？ 当然，也许不能想到只维护单个元素的做法，那么不妨从整体考虑。 我们知道，“排序”主要有几种方法：基于比较的排序，$\mathrm{O}(n\log n)$ 以上；桶排序，$\mathrm{O}(n+m)$；…… 由此衍生的“合并两个有序序列”的方法，可以有：归并式合并，$\mathrm{O}(n)$ ；桶式合并，$\mathrm{O}(m)$。 这道题，我们如果采用归并式合并，那就没有优化的空间了；如果采用桶式合并呢？ 由于桶式合并一次是 $\mathrm{O}(m)$ 的，因此如果 $m$ 是常数，总复杂度似乎就可以承受了。 这个“常数”是多少呢？$1$ 是没有意义的，那么就 $2$ 吧（bushi 如果我们把“不小于 $v$”的值记为 $1$，“小于 $v$”的值记为 $0$，那么对这样的序列进行排序，我们就可以知道最终的序列中，某个位置的值**是否不小于 $v$**。 这有什么用呢？有了上面的信息，我们就可以二分了呀！ 那么现在考虑如何桶式合并。显然，我们可以使用珂朵莉树，总共合并 $\mathrm{O}(n+m)$ 次，分裂 $\mathrm{O}(m)$ 次，复杂度 $\mathrm{O}((n+m)\log n)$，再乘上二分的复杂度，总复杂度为 $\mathrm{O}(n \log n \log n)$。当然我们也可以用线段树实现，常数较小。