可以 \textrm{K}，\textrm{N CH}_4 记得点赞，否则概率删评/mgx
更坏的阅渎体检
前言
初学 OI 的你通过二分解决了 k 小值问题，但面对区间第 k 小问题你束手无策！!1
小时候，你玩二分；长大后，二分玩你。你准备怎么办？
啥是整体二分
在询问答案具有单调性时，二分的思路是，\textrm{Solve}(l,r) 表示我二分此问题的答案时，已经知晓了 ans \in [l, r)，需要做进一步的递归。此时如果有一种手段 \textrm{check}(x) 表示判断 ans \ge x 是否是合法的，这个问题就得到了解决：令 mid = \frac{l+r}{2}，\textrm{check}(mid) 后执行 \textrm{Solve}(l,mid) 或 \textrm{Solve}(mid,r) 之一，直到边界情况（l=r）。
但面对多个询问，这种方式效率低下。考虑一种方式：\textrm{Solve}(l,r,Q) 表示同时解决集合 Q 内的所有询问（已知答案的值域在 [l,r]），利用数据结构对 mid 进行复杂度与 |Q|、[l,r] 有关的处理，而后对集合内所有询问执行 \textrm{check}(mid)，将所有询问分为两组 Q_1, Q_2 分别表示 ans<mid 的与 \ge mid 的，再调用 \textrm{Solve}(l,mid,Q_1) 与 \textrm{Solve}(mid,r,Q_2) 递归解决下去。
例 0 (P3834)
题意：给一个长度为 n 的序列，q 次区间 [L,R] 查询 k 小。
保证 n, q \leq 10^5，要求线性空间。
直观的想法是，将序列中的 $> mid$ 的数看做 $1$，否则看做 $0$，询问 $(L,R,k)$ 即判断 $[L,R]$ 的区间和与 $k$ 的大小关系。最为朴素的实现是直接在原序列中枚举每个元素，做一个前缀和，时间复杂度是无法承受的。
观察性质，我们现在要解决的是形如「区间内 $<x$ 的数有多少个」的问题，贡献是可加的，不妨将其看做值域在 $(-\infty,l)$ 与 $[l,mid]$ 两部分中的数的和，而前者已经在之前的分治中求出（不然不会分治到当前区间），后者可以暴力枚举序列中 $[l,mid]$ 中的数做单点加。利用树状数组维护区间和，就可以对每个询问 $O(\log n)$ 判断。
分析这样做的复杂度：一个重要的结论是，分治深度为 $O(\log n)$ 级别。对于某个序列中的元素 $x$，最多有 $O(\log n)$ 个 $\textrm{Solve}$ 的区间包含之，也就是最多做 $O(\log n)$ 次对于这个数的单点加。而对于某个询问，最多只会被判断 $O(\log n)$ 次，也最多只会被“划分” $O(\log n)$ 次，故这种做法时间复杂度为 $O((n+q)\log ^2 n)$，空间复杂度 $O(n+q)$。
同样这题有 $O(n \log n)$ 的整体二分做法，在后面会提到。
### 例 0.5 (P2617)
> 题意：例 0，带单点修改（将 $pos$ 上的数修改为 $x$）。
数据范围同例 0。
$\textrm{Sol}$：带上了时间轴，看起来不是静态二分能处理的问题，实则容易。
在分治时，我们分的是**值域**，对询问 check 的**时间**顺序是没有要求的，此时整体二分的优越性得以体现：可以将询问按照时间轴排序。如果我们能把修改也放到这个时间轴当中并在线地按照时间轴执行，那么处理询问时的答案就是真实的了。修改的权值如何定义？
一次修改 $(pos,x)$，可以看做在 $pos$ 位置删除了一个 $a_{pos}$，并添加了一个 $x$，通过这种拆成一删一插的方式，使得拆完之后的两个修改拥有了值域上的属性，可以放进去二分。具体而言：$\textrm{Solve}(l,r,Q)$ 中的 $Q$ 此时表示的修改与询问的集合，并已经按照时间排序。先让树状数组呈现「仅 $[l,mid]$ 中的数为 $1$，其他为 $0$」的状态，再按时间顺序执行 $Q$ 内的询问与修改。询问按照问出的值划分，修改的权值是确定的，直接划分。时间复杂度依然是 $O((n+q)\log^2 n)$。
[Code](https://www.luogu.com.cn/record/65458945)
### 实现
整体二分有两个好：常数小；线性空间。实现的时候特别注意这两点。
对于「将询问分成两部分」这一点和 CDQ 分治很相似，可以仿照 CDQ 分治的写法，将此次分治需要处理的询问排在区间 $[L,R]$ 之内，可以减小常数与代码难度。给一下我的代码（例题 0.5），仅供参考。
```cpp
void solve(int l,int r,int L,int R){
//[l,r] 为值域区间，[L,R] 为此次需处理的询问区间
if(l>r||L>R)return;
if(l==r){//边界判断
FOR(i,L,R)if(q[i].o)ans[q[i].id]=l;
return;
}
int mid=(l+r)/2,sl=L-1,sr=R+1;
FOR(i,L,R){
if(q[i].o){//询问
qry(q[i].l,q[i].r);
if(rs>=q[i].k)t[++sl]=q[i];
else q[i].k-=rs,t[--sr]=q[i];
}
//修改
else if(q[i].r>mid)t[--sr]=q[i];
else t[++sl]=q[i],q[i].work(1);
}
//记得清空
FOR(i,L,sl)t[i].work(-1),q[i]=t[i];
FOR(i,sr,R)q[i]=t[R+sr-i];
solve(l,mid,L,sl),solve(mid+1,r,sr,R);
}
```
#### 练习 (P3250)
> 题意：$n$ 个节点的树，$m$ 次操作：
>- 添加/删除一条 $u\to v$，权值为 $w$ 的路径；
>- 询问不包含 $x$ 的路径的最大权值。
>
> 保证 $n\leq 10^5$, $m \leq 2\times 10^5$。
$\textrm{Tip}$：二分的肯定是权值（答案），如何在分治时检查答案与 $mid$ 的大小关系？
### 例 1 (P3527)
> 题意：给定一个环，每个节点有一个所属国家。$k$ 个操作，$(l,r,x)$ 表示对 $[l,r]$ 中每个点权 $+a$ ($0<a\leq 10^9$)，求第 $i$ 个国家最早在多少次操作之后所属点权和 $\ge p_i$。
保证 $n,k \leq 3\times 10^5$。
$\textrm{Sol}$：此题需要二分的显然是每个国家的合法时间，具体的判断方式是：执行了 $[1,mid]$ 的操作后判断此国家的点权是否到达其上限。
同样的，我们可以整体二分，$\textrm{Solve}(l,r,Q)$ 的意义自然就是：已经知晓 $Q$ 集合内的国家的答案 $\in [l,r]$，需要进一步分治下去。暴力的想法是，直接执行时间 $[l,mid]$ 内的所有区间加，而对于每个国家，统计答案时枚举其拥有的点权，单点求值后暴力加起来判断。区间加单点求值，树状数组可以维护。
由于分治深度 $O(\log n)$，一个国家的点最多被暴力枚举到 $O(\log n)$ 次，一个操作也最多被执行 $O(\log n)$ 次，故时间复杂度 $O((n+k) \log^2 n)$，不够优秀。
实际上在处理 $[l,mid]$ 的修改时，树状数组的部分是不必要的。有个暴力做法是维护差分数组，然后扫一遍这个序列做前缀和得到答案，这样是 $O(n)$ 的，但我们只关心“关键点”（即 $Q$ 内所有国家拥有的点）的点权。我们将一个区间加差分成两个单点修改，将这些单点修改和单点询问（即关键点）按照其修改的位置排序，就能 $O(|Q|+r-l)$ 得到所有关键点的值。而排序这一步，在分治的时候已经保证了它的有序，向下分成的两部分自然也是有序的。这样就得到了一个 $O(n \log n)$ 的做法。
上面提到的静态区间 $k$ 小值的问题也可以使用这种，类似于一维偏序贡献差分后离散化的方式解决，留给读者当做练习。
[Code](https://www.luogu.com.cn/record/65976111)
### 练习 (P7560)
> 题意：$n$ 家食品店，$m$ 次操作：
>- 加入事件：编号 $\in [L,R]$ 内的所有食品店中，**都**有编号为 $C$ 的家庭的 $K$ 个人加入队尾。
>- 离开事件：编号 $\in [L,R]$ 内的所有食品店中，如果队列有超过 $K$ 个人，那么队列的前 $K$ 个人离开队列，否则队列里的所有人离开队列。
>- 白嫖事件：输出编号为 $A$ 的食品店队列中第 $B$ 个人的家庭。
>
> 保证 $n,m \leq 2 \times 10^5$。
$\textrm{Tip}$：离开事件相当于没有，维护每个队列在离开了多少个即可，然后仿照上题可以得到 $O((n+m) \log n)$ 的整体二分做法，相信读者可以完成。
## 整体二分求解单调序列
从一类这样的问题引入：将一个长度为 $n$ 的序列划分为 $m$ 个连续段，一个连续段 $[i,j]$ 有其价值 $w(i,j)$，求连续段价值之和最大值。容易写出一个这样的方程：$f_{i,j}=\max \{f_{i-1,k-1} +w(k,j)\}$。相信读者一定知道，如果 $w$ 满足四边形不等式，那么 $f$ 具有决策单调性，就是说对于同一层（$i$ 相等）的 $f_{i,j}$，记其决策点为 $g_j$，则 $g$ 单调不减。
介绍整体二分的另一种运用，若已知所求答案序列 $ans$ 具有**单调性**，可以采取这样的做法：$\textrm{Solve}(l,r,L,R)$ 表示已知 $ans_{[l,r]}$ 的值都在 $[L,R]$ 之中，取 $mid = \frac{l+r}{2}$，在合理的复杂度（e.g. $O(R-L+r-l)$）内得到 $ans_{mid}$ 的值 $M$，然后执行 $\textrm{Solve}(l,mid-1,L,M)$, $\textrm{Solve}(mid+1,r,M,R)$，将分治进行下去。分治树依然只有 $O(\log n)$ 层，复杂度及其证明留给读者思考。
### 例 2 (CF868F)
> 题意：给定长度为 $n$ 的序列 $a$，要把它分成 $k$ 个子段。每个子段的费用是其中相同元素的对数，求所有子段的费用之和的最小值。
保证 $n\leq 10^5$, $k \leq 20$。
$\textrm{Sol}$：用 $f_{i,j}$ 表示在前 $j$ 个元素分为了 $i$ 段的最小费用。令 $w(l,r)$ 表示 $a_{[l,r]}$ 中相等元素对数，有转移 $f_{i,j}=\max \{f_{i-1,k-1} +w(k,j)\}$。
$w(l,r)$ 满足四边形不等式（并不困难，读者自证），故 $f$ 每一层的转移都有决策单调性。现在仅考虑转移 $f_{x-1} \rightarrow f_{x}$ 这一层，令 $\textrm{Solve}(l,r,L,R)$ 表示已知 $f_{x,[l,r]}$ 的决策点在 $[L,R]$ 之中，进行下一步分治：计算出 $f_{x,mid}$ 决策点位置 $p$，而后 $\textrm{Solve}(l,mid-1,L,p)$, $\textrm{Solve}(mid+1,r,p,R)$。
$f_{x,mid}$ 决策点位置如何计算？直接暴力枚举 $[L,R]$ 中每一个位置计算即可，由于分治树深度 $O(\log n)$，故每一个点只会被枚举到 $O(\log n)$ 次，而暴力枚举时 $w(i,mid)$ 的计算看起来就比较棘手。考虑类似于莫队，维护左右两个指针并在移动时计算内部的答案。$mid$ 一定作为右指针移动的目标，而分治时相邻两次 $mid$ 的改变量加起来应与 $r-l$ 同级，故右端点移动次数 $O(n \log n)$；左端点一定从上一次分治的某个端点移动而来，在此次分治内移动次数与 $R-L$ 同级，也是 $O(n \log n)$。故一层的转移是 $O(n \log n)$ 的，总复杂度 $O(nk \log n)$。
代码写起来非常顺畅，几乎没有细节。
```cpp
inline ll calc(int l,int r){
//类似于莫队，移动左右指针
while(nl>l)res+=cnt[a[--nl]]++;
while(nr<r)res+=cnt[a[++nr]]++;
while(nl<l)res-=--cnt[a[nl++]];
while(nr>r)res-=--cnt[a[nr--]];
return res;
}
void solve(int x,int l,int r,int L,int R){
//解决第 x 层的转移
if(L==R){
FOR(i,l,r)dp[x][i]=dp[x-1][L-1]+calc(L,i);
return;
}
if(l>r)return;
rgi mid=(l+r)/2,mi=L;
dp[x][mid]=dp[x-1][L-1]+calc(L,mid);
//暴力计算 dp[x][mid] 决策点
FOR(i,L+1,min(R,mid)){
ll rs=dp[x-1][i-1]+calc(i,mid);
if(rs<dp[x][mid])dp[x][mid]=rs,mi=i;
}
solve(x,l,mid-1,L,mi),solve(x,mid+1,r,mi,R);
}
```
[Code](https://codeforces.ml/contest/868/submission/140003291)
## 整体二分维护不可加贡献
现在回顾例 0 中的一句话：
> **贡献是可加的**，不妨将其看做值域在 $(-\infty,l)$ 与 $[l,mid]$ 两部分中的数的和，而前者已经在之前的分治中求出...
这很丑陋，因为贡献不需要可加啊？我们可以这样子操作：每次 $\textrm{Solve}(l,r,Q)$ 时，先执行 $[l,mid)$ 的修改，解决 $Q$ 的询问并将 $Q$ 分为两半，然后**不清空**，向右 $\textrm{Solve}(mid,r,Q_2)$，再**撤销**掉 $[l,mid)$ 的操作，执行 $\textrm{Solve}(l,mid,Q_1)$。
这种做法的不同之处在于，$\textrm{Solve}$ 前保证了左端点之前的修改已经被执行，进而直接获得「执行了 $(-\infty,mid)$ 内的修改」这个状态，做完后撤销回去。好处就是，询问的答案不需要分多次可加的贡献得到，而是可以直接查询，这样就可以维护一类并不是很好拆分的贡献，比如**图连通性**。
### 例 3 (CF603E)
> 题意：给定一张 $n$ 个点的无向图，初始没有边。依次加入 $m$ 条带权的边，每次加入后询问：是否存在一个边集使得图中所有点的度数均为奇数。若存在，则输出边集中的最大边权的最小值。
保证 $n \leq 10^5$, $m \leq 3\times 10^5$。
$\textrm{Sol}$：首先是一波人类智慧操作，结论是：存在合法边集当且仅当所有连通块大小均为偶数。
- 必要性：连通块大小为奇数时若存在方案，则保留合法边集后此连通块度数之和为奇数，矛盾。
- 充分性：每个联通块内仅保留 DFS 树，自底向上 DP，必然可以构造方案。
然后考虑无修改的情况：连通块大小均为偶数时，再添加一些边后依然满足条件，所以按边权从小到大排序后，有用的边一定是一个前缀，并且具有单调性。而此题「带修改，多询问」，并且询问的答案有很好的性质：单调不增。自然想到整体二分。
我们用数据结构（可撤销并查集）维护连通块，观察到答案序列单调，考虑使用上文求解单调序列的方式：$\textrm{Solve}(l,r,L,R)$ 表示已知 $ans_{[l,r]}$ 在 $[L,R]$ 之中，并且权值 $<L$ 且时间 $<l$ 的边已经加在并查集中，我需要进一步分治下去。令 $mid = \frac{l+r}{2}$，考虑求出 $ans_{mid}$ 的值 $p$ 后，分别分治做 $\textrm{Solve}(l,mid-1,L,p)$，$\textrm{Solve}(mid+1,r,p,R)$。
怎样才能求得 $ans_{mid}$？考虑最为朴素的做法：将时间 $\leq mid$ 的边按照权值从小到大加入到并查集中，第一个连通块大小均为偶数的时刻即为 $ans_{mid}$。而此时已经保证了权值 $<L$ 且时间 $<l$ 的边已经加在并查集中，只需要按顺序加入：
1. 时间 $\in [l,mid]$ 且权值 $<L$ 的边。这部分边不影响答案，先直接加入。
2. 权值 $\in [L,R]$ 且时间 $\leq mid$ 的边，加到图合法为止。
图第一次合法时得出了 $ans_{mid}$ 的答案 $p$，此时我们撤销到这次 $\textrm{Solve}$ 之前，加入上文 1 中的边并递归 $\textrm{Solve}(mid+1,r,L,p)$，然后撤销之，加入 2 中的边并递归 $\textrm{Solve}(l,mid,p,R)$。每次 $\textrm{Solve}$ 的复杂度是 $O((R-L+r-l) \log n)$，分治层数 $O(\log n)$，故总复杂度 $O(m \log^2 n)$，空间复杂度 $O(n+m)$。
另：我们同样可以二分答案这一维，去检验所有询问的答案是否 $\ge mid$，做法基本一致。其本质是，在整体二分时若需要维护两个指针，则过程中二分其中一维，两个指针的总变化量是 $O(n \log n)$ 的。
[Code](https://codeforces.com/contest/603/submission/141027175)
### 练习 (LCT 模板题 QAQ)
> $n$ 点 $m$ 边无向连通图，每条边有二元组权值 $(x,y)$，求 $\max x+\max y$ 的 MST。（即最小化生成树上所有边的 $\max x+\max y$）
>
> $n,m \leq 10^5$。
$\textrm{Tip}$：摘一段上面的话：
> 在整体二分时若需要维护两个指针，则过程中二分其中一维，两个指针的总变化量是 $O(n \log n)$ 的。
### 例 4 (P5163 阉割版)
> 题意：给定一张 $n$ 个点的有向图，依次加入 $m$ 条有向边，对于每条边询问一个最早的时刻，使得其两端位于一个强联通分量内。
保证 $n \leq 10^5$, $m \leq 2\times 10^5$。
$\textrm{Sol}$：如果知道做法是整体二分，那么这道阉割版就很容易了。依然是 $\textrm{Solve}(l,r,Q)$ 表示已知 $Q$ 集合的边的答案在 $[l,r]$ 内，需要进一步分治，现在考虑解决的问题是，如何得知加入了 $[1,mid]$ 的边之后，$Q$ 集合内哪些边两端合并在一个 SCC 内。
动态加边维护 SCC 并非易事，可以考虑的是利用性质把 SCC 变成别的什么东西，比如用并查集把 SCC 变成一个连通块（缩点）后，在新图上建边跑 SCC 结果依然正确，这就启发我们使用并查集维护缩点之后的图。
具体而言，$\textrm{Solve}$ 时维护加入 $[1,l)$ 的边的图的**缩点后的状态**，而后在缩点后的图上加入时间 $[l,mid]$ 的边，与 $Q$ 内时间 $<l$ 的边，跑一遍 SCC 并分治下去，利用和上题一样的路数撤销。由于加入的边数是 $O(r-l+|Q|)$ 级别，故 SCC 的部分总复杂度 $O((n+m)\log m)$，瓶颈在于维护 SCC 的并查集，复杂度 $O((n+m)\log^2 m)$。
读者可能会怀疑时间 $\leq l$ 的图缩点之后，某些边 $E$ 没被加上而导致最后求得的 SCC 不正确（因为我没学懂的时候也有这个疑问！），其实很简单：而 $E$ 在 $< l$ 的（缩点后的）图中不存在就证明其答案一定 $\ge l$，所以它要么在此次被添加，要么没被添加但是对此次答案不影响。
[Code](https://www.luogu.com.cn/record/66243712)（完整版）
## 总结
从个人视角出发，整体二分这种分治算法的精髓就在于，可以通过简单的手段将需要求解的答案序列分成了两部分递归求解，从递归层数的角度出发保证复杂度正确性。
整体二分思想的运用当然是极为广泛的，如保序回归问题在求解带有限制区间的部分时就运用了整体二分。上文作为入门教程，较为简易而内容不多，提及的只是冰山一角，抛砖引玉。