之所以把cdq分治和整体二分放在一起学习,是因为他们两个实在太像了…不管是做法还是代码… 感觉整体二分可能会比cdq分治稍微简单那么一点点?所以先学整体二分. 整体二分是对答案进行二分,其具体操作如下: (比如以ZJOJ2013K大数查询为例)
具体过程
Step1.从(L,R)二分答案.mid=(L+R)>>1,用线段树维护原序列中(a,b)位置比mid大的数有多少个,同时记录对序列的操作分别是什么操作. Step2.执行给定操作. 1.如果操作是插入,比如在a,b位置之间每个数后插入一个数c ①如果cmid就在线段树的(a,b)部分加一,然后修改操作标记为1; ②如果cmid,修改操作标记为0; 2.如果操作是查询,如果线段树(a,b)段的和大于c,那么答案必定比mid大,修改操作标记为1,否则操作标记为0. Step3.进入下一层.所有标记为0的,分入区间(L,mid),标记为1的分入区间(mid+1,R).(这里重新划分后要再排序.可以归并(当然效率很高),不过直接sort也可以的.) 直到二分到L==R,L即为所求答案. 每次二分到新的答案,我们要直接清空线段树.(在根节点打清空标记,否则区间太大用memset会炸掉) 与当前访问区间不相交的另一段区间,其实始终对我们二分的答案有影响,只要记录一下这个影响就可以了,所以不需要去考虑它.
所以我们可以看出来,整体二分就是不断对数列进行划分,划分的标准就是数值的大小.因此其复杂度也是与数列长度正相关的. 时间复杂度的证明可以看2013年国家集训队论文许昊然《浅谈数据结构题的几个非经典解法》 如果您不想翻论文,我很贴心的把那一段证明引用到下面来(其实为了加深理解下面这些我都手打了):
定义T(C,S)表示待二分区间长度为C,待二分序列长度为S,不妨设单次处理时间复杂度则有 T(C,S)=T())+O(f(s)) 解之得 T(C,n) 注,与上文一样该证明只有在时成立.
具体题目后面单独写题解.(你问我为什么不像别人一样把题解当例题写着里面?我要刷访问量和文章量啊233)
，临行之前，面对太多的疑问和不解：为何是一个人？
