Sweetlemon 的博客

Sweetlemon 的博客

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

posted on 2020-07-16 11:25:36 | under 半题解 |

好久没有用这样的模式了,说明你偷懒好久了。

[HEOI2016/TJOI2016]排序

题意就不叙述了,见上方链接。

首先转化一下模型。题目要求把序列的一段排序,那可以认为是有若干个有序段(初始时有 $n$ 个单元素的有序段),每次分裂和合并一些有序段,每次分裂的有序段不超过两个(类似珂朵莉树的区间染色)。

于是“平衡树”一类想法马上涌上来,然后……就没有然后了。(当然这题确实有类似平衡树的做法,不过用的不是平衡树,而是权值线段树的分裂和合并。这是因为线段树合并的过程就是销毁重复节点的过程,总时间不超过创建这些节点的时间;但两棵平衡树似乎不能足够快速地合并,因为合并的时候并不保证能销毁节点。详见 【模板】线段树分裂

平衡树做不了,那么就没法做了 重新看一下题,看看有没有什么蹊跷之处?

诶,这题为什么只询问一个位置上的元素呢?这是不是意味着,我们并不需要维护整个序列

当然,也许不能想到只维护单个元素的做法,那么不妨从整体考虑。

我们知道,“排序”主要有几种方法:基于比较的排序, $\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)$。当然我们也可以用线段树实现,常数较小。