描述
有N个位置，M个操作。操作有两种，每次操作如果是1 a b c的形式表示在第a个位置到第b个位置，每个位置加入一个数c
如果是2 a b c形式，表示询问从第a个位置到第b个位置，第C大的数是多少。
分析
- 今天终于看懂了一个整体二分的题目. 发现这真是一种很BT的做法.
- 二分答案区间(L, R), 判断中间值M = L+(R-L)/2. 每次清空线段树(直接在根节点上打删除标记, 不要用memset直接清, 会T..). 线段树维护的是在区间(a, b)中比二分的答案M大的数有多少. 处理在(l, r)中的操作, 如果是插入(a, b, c), 判断c和M的大小,
c大于M的话在线段树(a, b)区间打增加标记表示+1, 同时操作类型标记为1, c不大于M操作类型标记为0; 如果是查询(a, b, c)操作, 当在线段树(a, b)区间和大于c则说明比M大的超过k个, 那么答案一定比M大, 操作类型标记为1, 否则标记为0.
- 将所有标记为0的点去下一层(L, M)继续 (可以直接按类型sort, 也可以借鉴归并排序的思想O(n)的归并), 标记为1的点去(M+1, R)继续二分.
- 当答案区间(L = R)时, 操作区间所有的查询操作的答案都为L.
- 另 : 1. 在线段树操作时传入太多参数会严重拖慢效率.
- 2. 在结构体里定义的宏在外面一样用.
代码
BZOJ-3110-K大数查询-ZJOI2013-整体二分
原文：http://blog.csdn.net/qq_21110267/article/details/44596719
