十分巧妙的主席树题
思路:
类似于P1168, 有一个使用二分求区间中位数的方法:
对于数x, 将>=x的值标为1, <x的值标为-1.
然后将询问区间的标号加起来, 若和>=0表示中位数可能比x更大, 否则中位数一定比x更小.
对于这题来说, 虽然区间是不固定的, 但也可以借鉴上述思想:
对于数x, 首先区间(b, c)是固定的, 求出这段区间的标号和.
然后对于区间[a,b], 求出这段区间的最大后缀标号和, 同样对于[c,d]求出其最大前缀标号和.
若这三个值的和>=0则说明可能存在符合条件的比x更大的中位数, 否则说明最大的中位数比x更小.
同时注意到如果从小到大对数x建立线段树维护标号, 则每个位置的值只会改变一次, 于是可以使用主席树将这些线段树结合起来.
所以不同于以往在区间上建立值域线段树, 这次是在值域上建立区间的线段树.
注意(b, c)区间有可能不存在.
代码:
1 |
|