COGS1763(BZOJ2653) middle 主席树+二分

发布于 2017-08-05  4.56k 次阅读


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

Description
一个长度为n的序列a,设其排过序之后为b,其中位数定义为b[n/2],其中a,b从0开始标号,除法取下整。给你一个
长度为n的序列s。回答Q个这样的询问:s的左端点在[a,b]之间,右端点在[c,d]之间的子序列中,最大的中位数。
其中a<b<c<d。位置也从0开始标号。我会使用一些方式强制你在线。

Input
第一行序列长度n。接下来n行按顺序给出a中的数。
接下来一行Q。然后Q行每行a,b,c,d,我们令上个询问的答案是
x(如果这是第一个询问则x=0)。
令数组q={(a+x)%n,(b+x)%n,(c+x)%n,(d+x)%n}。
将q从小到大排序之后,令真正的
要询问的a=q[0],b=q[1],c=q[2],d=q[3]。
输入保证满足条件。
第一行所谓“排过序”指的是从大到小排序!

Output
Q行依次给出询问的答案。

Sample Input
5
170337785
271451044
22430280
969056313
206452321
3
3 1 0 2
2 3 1 4
3 1 4 0

Sample Output
271451044
271451044
969056313

HINT
0:n,Q<=100
1,...,5:n<=2000
0,...,19:n<=20000,Q<=25000

[/toggle]

一般的主席树都是建立权值线段树,然后用每个版本划分区间位置,但是这道题就不太一样。首先,考虑要求的是左右端点在一定区间内的中位数,那么这个询问中,左右区间夹着的一段是一定要取的,而左右两端则不定。

考虑在一段区间中,大于等于中位数的数有len/2个,那么,先离散数据,按照区间位置建立主席树,叶子节点为1表示该位置的元素大于等于某数,-1表示该位置元素小于某数,这样,查询区间中有多少个大于某数的数字,即可二分。以权值从小到大为轴建立每个主席树,每次只将权值对应的位置修改为-1。这样,root[i]中的1的个数即表示大于i的有多少。查询root[i-1]时,二分中位数的权值,在对应的主席树中查询最大前缀、中缀、后缀和,若其大于等于0,说明大于等于i的元素不少于小于的,就可以接着二分了。

 


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