7
NOIP太难了，怎么一堆神犇，等我考上广附或者华附或者广外或者没开挂省实或者正常点的二中六中广雅执信铁一我一定不会废成这个样子
前言
整体二分和CDQ分治是与莫队并列的三大离线算法，本质都是分治，不过思想和使用范围不同，通常可以高效解决平衡树套线段树、BIT套**树这些编码难度较大的问题。它们较少在NOIP和CSP中考察，同时难度也较大（模板题紫），但是可以多做几道紫题不过有助于增进对分治的理解。
第一部分：整体二分
整体二分是一种离线算法 （说了=没说）
整体二分格式：整体二分函数中通常有4个参数，表示答案值域[L,R][L,R][L,R]和所执行的操作/询问的范围[l,r][l,r][l,r]。函数先计算出LLL和RRR的平均值midmidmid，用二分思想猜测midmidmid为答案，并使用数据结构（99%是BIT和线段树）检验每个询问的答案小于midmidmid还是大于midmidmid，小于midmidmid的分到左组，大于midmidmid的分到右组，分别解决，将两个组的答案值域范围缩小一半。当答案值域大小为1时（L=RL=RL=R）将该组所有询问的答案设为LLL(RRR)并返回。
更细致的讲解将在例题中展现，最详细的在后文Dynamic Rankings一题的讲解中
区间第K小
在上一篇关于**树的文章中我们用**树实现了区间第kkk小的查询，这里我们使用复杂度略高的整体二分尝试实现。
先从一个问题入手：
如果只有一次查询，我们要如何解决？
答案很明了：排序二分。我们把所有数从小到大进行排序（不是区间内，并且排序时记录原来的位置），然后使用二分每次猜一个位置midmidmid，如何判断答案在midmidmid的左边还是右边？我们使用树状数组BIT，对于所有在[l,mid][l,mid][l,mid]的数，我们在它原来的位置加一，最后计算在询问区间[l,r][l,r][l,r]中有多少个一（也就是求和），就可以知道答案在midmidmid左边还是右边了。如果数量小于kkk，说明答案猜小了，需要增加midmidmid使统计到的数量增大（统计到的数量其实代表在询问的区间[l,r][l,r][l,r]内有多少个数小于a[mid]a[mid]a[mid]，第kkk小值在区间[l,r][l,r][l,r]内应有k−1k-1k−1个数小于它）否则，缩小midmidmid。
小技巧：当答案大于midmidmid时，我们将lll设为midmidmid，将kkk减去midmidmid，这样就可以减少很多计算量。
如图所示：
时间复杂度为O(Nlog2N)O(Nlog_2N)O(Nlog2 N)
那么如何求解多个询问呢？
注意到每次询问都查验了一个midmidmid，那我们对所有询问查询区间值，然后得出它在midmidmid左边还是右边，分成两组分治完成不就行了吗？
然后就AC了
参考代码：我没写，可以在OI-Wiki中查看。
这个代码真难懂，加点注释罢~
可过P3834
注意：memset单次复杂度为O(N)O(N)O(N)，会*，所以对于每一个+1操作，我们在原来的位置-1就行了
总复杂度为O(Nlog2O(Nlog_2O(Nlog2 2N)^2N)2N)，请读者自己证明
把算法讲清楚实在是太难了，请对照代码理解，初学者怎么都懂不了的请移步左神的整体二分
基本用法
首先可以静态做出我们讲过的P4137 Rmq Problem / mex，解法不细讲因为代码没写而且只是蓝题，可以在阅读完全文后自行思考或者参考题解
接下来正经讲讲题
带修改区间第KKK小
首先考虑**树。
这题不能用普通**树，需要用BIT套**树实现修改操作，本质是用树状数组思想O(log2N)O(log^2N)O(log2N)修改权值线段树的其中一个版本，询问时用O(log2N)O(log^2N)O(log2N)求出区间内的线段树权值和并递归询问。
此题也可用整体二分。
我们把询问和修改操作统称为操作一起二分。
这时我们要用不同写法的整体二分了。不使用排序，二分答案可能的权值（即最小值到最大值），再遍历所有数，把大小小于midmidmid的插入树状数组。
我们更改一下结构体的结构，有一个标记op表示操作类型，op=1意味着查询，op=2意味着将一个数值插入树状数组。当op=1，x意为查询的lll，y表示查询的rrr，k表示查询第kkk小，id表示查询的编号，用于输出答案。当op=2，意为将第x个位置改为y并在BIT的第x位增加k。k=1表示插入一个数，k=-1表示删除一个数。
接下来把修改操作拆分为一个删除操作和一个插入操作。插入操作：在第x个位置添加一个数y，其k=1，用于查询；但是我们有时需要修改，添加一个删除操作，x和y与要删除的操作一致，这样当被删除的操作被执行时这个操作也会执行，上个操作在BIT的x位+1，这个操作又在BIT的x位-1，二者抵消。删除完了重新插入，x相等，y为修改后的值，k=1.
注意到不用初始化，可以将初始化操作全部转化为插入操作。
所有操作一起进行二分。由于y为插入操作插入后的值，如果y>midmidmid，这个操作对答案没有影响（因为你的BIT只计算小于midmidmid的数），分到右组（只有更大的midmidmid查询才会用到这个操作，所以去右组等更大的midmidmid），否则在BIT中实现这个插入/查询操作，并分到左组等更小的midmidmid。
最后，如果l=rl=rl=r，将该组所有查询操作答案设为lll并返回。
有的人可能会疑惑：你要怎么保证每个查询刚好在且仅在它前面所有操作执行完后执行呢？即，你怎么保证执行是按时间顺序的呢？答：你按时间顺序挨个加入操作，分治的分组是从左到右遍历的，并不会改变同一组内两个操作的顺序，你在遍历到修改操作时立刻修改，遍历到查询操作就立刻查询，可以保证其有序性。
虽然比较难理解，但是代码是很透彻的，做整体二分一定要多看代码，弄清每一个细节，这样就能轻松理解。
Code:Code:Code:
注意这里把答案先初始化为-1，如果不是-1说明是有答案的，对这个答案进行输出，实际有更简便的写法，见后文。
该代码复杂度：O(NlogNlogV)O(NlogNlogV)O(NlogNlogV)
所用时间：最长运行测试点197ms，使用O2优化21个测试点总时长2.08s
其它解法：树套树、分块
整体二分因为用的BIT，加上没有大量递归，常数较小，是不错的选择。
二维第KKK小
题目看这里：P1527 [国家集训队] 矩阵乘法
很明显可以用二维BIT的单点修改+区间查询完成，其实并不难，套用模板即可。注意这里使用了基础写法
Code:Code:Code:
（排序写法，初学者较容易理解）
注意该题复杂度为O(N2log3N)O(N^2log^3N)O(N2log3N)，最大一个点247ms
此题其它解法：CDQCDQCDQ分治（O(N2log2N)O(N^2log^2N)O(N2log2N)，好像是吧）、权值线段树套小波树（WaveletTreeWavelet TreeWaveletTree)，时间复杂度O((N2+Q)log2N)O((N^2+Q)log^2N)O((N2+Q)log2N)、小波矩阵（WaveletMartrixWavelet MartrixWaveletMartrix)套小波矩阵，时空复杂度O((N2+Q)log2N)−O(N2logN)O((N^2+Q)log^2N)-O(N^2logN)O((N2+Q)log2N)−O(N2logN)
线段树维护整体二分
P3332 [ZJOI2013] K大数查询
注意到不能用普通BIT进行整体二分插入了，需要一种区间插入数据的数据结构。
没错！变体BIT线段树。
其实也就是换了一个方式实现。由于是线段树，我们不需要一个一个操作清空，而是直接用基础区间增加d+区间设为d的线段树，每次操作前给整个区间（节点1）打上清空tag就行啦。
注意到分治代码略有不同，这是因为求的是第kkk大
Code:Code:Code:
注意tag1是增加tag2是清空
时间复杂度O(Nlog2N)O(Nlog^2N)O(Nlog2N)(因为题目有特殊约定），但是由于是大常数的线段树，最大一个点跑到了273ms。唉！
同时此题还有平衡树套线段树（应该是O(Nlog3N)O(Nlog^3N)O(Nlog3N)吧，常数挺大，一般加标记永久化才可过)、BIT套**树（O(Nlog2N)O(Nlog^2N)O(Nlog2N)，常数较大，可用标记永久化)、分块（O(NNO(N\sqrt NO(NN )等解法。
下集预告
你信心满满地去洛谷搜整体二分的题，搜到了这个东西：
动态逆序对
然而，你很快发现，这道题不能用整体二分（这里指普通整体二分）
它属于另一个领域：
CDQ分治CDQ分治CDQ分治
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
ToToTo bebebe continuedcontinuedcontinued<−<-<−
（（（一打开电脑56条消息通知
有帮助，赞一个