6
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<−<-<−
附：不知道为什么流量很少而且好像 ACGO 数据问题目前阅读量和回复数莫名一致的第二篇
有帮助，赞一个