COGS1763(BZOJ2653) middle 主席树+二分 数据结构

COGS1763(BZOJ2653) middle 主席树+二分

一般的主席树都是建立权值线段树,然后用每个版本划分区间位置,但是这道题就不太一样。首先,考虑要求的是左右端点在一定区间内的中位数,那么这个询问中,左右区间夹着的一段是一定要取的,而左右两端则不定。 考虑在一段区间中,大于等于中位数的数有len/2个,那么,先离散数据,按照区间位置建立主席树,叶子节点···
BZOJ4552 [Tjoi2016&Heoi2016]排序 二分答案+线段树 数据结构

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

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