Tag-整体二分

Icontofig 's Blog // 我们的征程是星辰大海!Away From OI,Come to ICPC(查看友链请点About Me)

 2017-01-15 14:31:30 |  0 Comments  |  整体二分 线段树

[Zjoi2013]K大数查询

Description

有N个位置,M个操作。操作有两种,每次操作如果是1 a b c的形式表示在第a个位置到第b个位置,每个位置加入一个数c 如果是2 a b c形式,表示询问从第a个位置到第b个位置,第C大的数是多少。

Input

第一行N,M 接下来M行,每行形如1 a b c或2 a b c

Output

输出每个询问的结果

Sample Input

2 5 1 1 2 1 1 1 2 2 2 1 1 2 2 1 1 1 2 1 2 3

Sample Output

1 2 1

HINT

【样例说明】第一个操作 后位置 1 的数只有 1 , 位置 2 的数也只有 1 。 第二个操作 后位置 1的数有 1 、 2 ,位置 2 的数也有 1 、 2 。 第三次询问 位置 1 到位置 1 第 2 大的数 是1 。 第四次询问 位置 1 到位置 1 第 1 大的数是 2 。 第五次询问 位置 1 到位置 2 第 3大的数是 1 。
N,M<=50000,N,M<=50000a<=b<=N1 操作中abs(c)<=N2操作中c<=Maxlongint

题解

二分:当遇到的操作是询问操作时,查询线段树里的当前区间,并将当前区间所包含的数的个数as与查询的第k大相比较,如果小于k,那么把当前询问分到左边去,并统计影响k-=as,反之,将它分到右边;当遇到的操作是加入操作时,把要加入的数和mid比较,如果大于mid,那么就把当前操作统计进去,而且当前操作会对右边产生影响,所以要分到右边去,虽然对左边也有影响,但在处理询问时已经处理,就不用考虑了。
数的统计:线段树维护,记录每个区间当前有多少个大于mid的数,“加入”操作里的“统计进去”即是更新当前区间的数的个数(注:不要把线段树的区间和上面把操作分到左右区间混淆,这是不相干的概念,上面分到左右只是为了维护整体二分的序列的有序性)
每次操作完,都要以区间序号为关键字重新排序。
细节:线段树维护时,要考虑线段树每一次二分时,之前的标记等都是不能再使用的,所以要重置,但因为数组过大,如果每一次memset,必然TLE。所以设一个标记数组,每次pushdown前,都要判断当前点的标记是否是1,若是1,把当前点置0,并把当前点的左右儿子重置。这样,每次二分重置时,只用重置根节点即可。
数据范围过大,可能超int。

代码

#include <iostream>
#includ
Title - Artist
0:00