BZOJ-3110-K大数查询-ZJOI2013-整体二分

描述

有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,c)操作,当在线段树(a,b)区间和大于c则说明比M大的超过k个,那么答案一定比M大,操作类型标记为1,否则标记为0.
• 将所有标记为0的点去下一层(L,M)继续 (可以直接按类型sort,也可以借鉴归并排序的思想O(n)的归并),标记为1的点去(M+1,R)继续二分.
• 当答案区间(L = R)时,操作区间所有的查询操作的答案都为L.
• 另 : 1. 在线段树操作时传入太多参数会严重拖慢效率.
• ? ? ? 2. 在结构体里定义的宏在外面一样用.