BZOJ4552 [Tjoi2016&Heoi2016]排序 二分答案+线段树

发布于 2017-07-26  2.49k 次阅读


[toggle hide="yes" title="题目" color=""][/toggle]

因为只有最后的一次查询,所以可以二分答案。

二分最终答案M,将序列中大于等于M的数用1替代,其余为0,构建线段树,这样,对一段区间排序时,可以直接统计区间内有多少个1,然后将区间修改为0、1两部分,即可完成排序工作。最后,如果q位置为1,说明答案大于等于q,移动左区间即可。

[toggle hide="no" title="代码" color=""]

 

[/toggle]


Narcissus | HZOIer | zhuohaoyu1228@gmail.com | QQ 943382974