BZOJ 4552 [Tjoi2016&Heoi2016] 排序

发布于 2018-01-24  211 次阅读


题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=4552

题意:一个排列,有一个操作序列,为部分排序,问操作后位置为 pos 的数是什么。


这题看到 6000ms 每个点还以为是分块暴力啥的...

考虑如果知道了答案是 x,有什么帮助。

如果希望在排序的过程中只保留 x 的位置信息,可以做到\(O1\),即前面都是比它小的,后面都是比他大的,其他的信息都不计。

所以在定位 x 的过程中只有一个数是大于它还是小于它是有意义的,如果小于等于赋为 0,否则赋为 1,这样一次排序实质上就是两次区间覆盖操作。

用线段树维护即可,最后如果发现 pos 这个位置是 1,则说明他前面应该有更多的 0,所以实际答案比 x 大,否则实际答案小于等于 x,满足二分性,二分 x 即可。

 


一个非常弱的准退役OIER