[BZOJ4552][TJOI2016]排序(二分,线段树)

发布于 2018-05-15  227 次阅读


本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:[BZOJ4552][TJOI2016]排序(二分,线段树)

Description

在2016年,佳媛姐姐喜欢上了数字序列。因而他经常研究关于序列的一些奇奇怪怪的问题,现在他在研究一个难题,需要你来帮助他。这个难题是这样子的:给出一个1到n的全排列,现在对这个全排列序列进行m次局部排序,排序分为两种:1:(0,l,r)表示将区间[l,r]的数字升序排序2:(1,l,r)表示将区间[l,r]的数字降序排序最后询问第q位置上的数字。

Tag

二分,线段树

解决思路

当数据值域很小的时候,我们可以用桶来维护值域,直接进行排序,但是这里并没有值域限制。考虑到最后其实只询问一个位置上的答案,不妨二分这个值,将序列中的数,大于它的设为1,小于等于它的设为0。只有0和1的序列很好排序,直接统计数量就好,这里采用支持区间覆盖的线段树来实现。最后看这个位置上的数,如果是0,说明答案小于等于当前二分的值,否则是大于。

代码

本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:[BZOJ4552][TJOI2016]排序(二分,线段树)


HNCJ OIer