通俗易懂整体二分！

本文搬运自我的洛谷博客。

可以 $\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$，要求线性空间。

$\textrm{Sol}$：先定义 $\textrm{Solve}(l,r,Q)$ 表示已知集合 $Q$ 内的询问的答案在 $[l,r]$ 中，考虑如何分治下去，也就是判断 $Q$ 内所有询问的答案与 $mid$ 的大小关系。

直观的想法是，将序列中的 $> 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)$。

查看代码

#include<bits/stdc++.h>
#define FOR(i,a,b) for(int i=a,i##i=b;i<=i##i;++i)
const int N=400010;
int n,m,C,a[N],ans[N],f[N],rs,l,r,k;
char ch[3];
void upd(int x,int v){for(;x<=n;x+=(x&-x))f[x]+=v;}
void qry(int l,int r){
	for(rs=0;r;r&=r-1)rs+=f[r];
	for(--l;l;l&=l-1)rs-=f[l];
}
struct opt{
	int o,l,r,k,id;
	void work(int v){if(!o)upd(l,k*v);}
}q[N],t[N];
void solve(int l,int r,int L,int 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);
}
signed main(){
	scanf("%d%d",&n,&m),memset(ans,-1,sizeof ans);
	FOR(i,1,n)scanf("%d",a+i),q[++C]={0,i,a[i],1};
	FOR(i,1,m){
		scanf("%s%d%d",ch,&l,&r);
		if(ch[0]=='Q')scanf("%d",&k),q[++C]={1,l,r,k,i};
		else q[++C]={0,l,a[l],-1,i},q[++C]={0,l,a[l]=r,1,i};
	}
	solve(0,1e9,1,C);
	FOR(i,1,m)if(~ans[i])printf("%d\n",ans[i]);
	return 0;
}

实现

整体二分有两个好：常数小；线性空间。实现的时候特别注意这两点。

对于「将询问分成两部分」这一点和 CDQ 分治很相似，可以仿照 CDQ 分治的写法，将此次分治需要处理的询问排在区间 $[L,R]$ 之内，可以减小常数与代码难度。给一下我的代码（例题 0.5），仅供参考。

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$ 小值的问题也可以使用这种，类似于一维偏序贡献差分后离散化的方式解决，留给读者当做练习。

查看代码

#include<bits/stdc++.h>
#define rgi register int
#define FOR(i,a,b) for(rgi i=a,i##i=b;i<=i##i;++i)
#define ROF(i,a,b) for(rgi i=a,i##i=b;i>=i##i;--i)
using namespace std;
const int N=1200010;
int n,m,k,b[N],p[N],l,r,w,C,ans[N];
unsigned long long a[N],res;
namespace Reimu_Kawaii{
	char buf[1<<20],*p1,*p2;
	#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<20,stdin),p1==p2)?0:*p1++)
	inline int read(){
		int x=0;char c=getchar();
		while(!isdigit(c))c=getchar();
		while(isdigit(c))x=x*10+c-'0',c=getchar();
		return x;
	}
	inline void write(int x){
		static char buf[15];
		static int len=-1;
		do buf[++len]=x%10+48,x/=10;while(x);
		while(len>=0)putchar(buf[len]),--len;
		putchar('\n');
	}
	#undef getchar
}using namespace Reimu_Kawaii;
struct Q{
	int x,o,id;
	bool operator<(Q B)const{return x==B.x?(!o<!B.o):x<B.x;}
}q[N],t[N];
#define ins(x,y) q[++C]={x,y,i}
#define E b[q[i].x]
void solve(int l,int r,int L,int R){
	if(l>r||L>R)return;
	if(l==r){
		FOR(i,L,R)if(!q[i].o)ans[b[q[i].x]]=l;
		return;
	}
	int mid=(l+r)/2,sl=L-1,sr=R+1;
	FOR(i,L,R){
		if(q[i].id<=mid)res+=q[i].o;
		if(!q[i].o)a[E]+=res;
	}
	FOR(i,L,R){
		if(q[i].o)q[i].id>mid?t[--sr]=q[i]:t[++sl]=q[i];
		else{
			if(a[E]>=p[E])t[++sl]=q[i];
			else t[--sr]=q[i],p[E]-=a[E],a[E]=0;
		}
	}
	FOR(i,L,sl)q[i]=t[i],a[E]=0;
	FOR(i,sr,R)q[i]=t[R+sr-i],a[E]=0;
	res=0,solve(l,mid,L,sl),solve(mid+1,r,sr,R);
}
signed main(){
	m=read(),n=read();
	FOR(i,1,n)b[i]=read(),ins(i,0);
	FOR(i,1,m)p[i]=read();
	FOR(i,1,k=read()){
		l=read(),r=read(),w=read();
		if(l>r)ins(1,w),ins(r+1,-w),ins(l,w);
		else ins(l,w),ins(r+1,-w);
	}
	sort(q+1,q+C+1),solve(1,k+1,1,C);
	FOR(i,1,m)if(ans[i]>k||!ans[i])puts("NIE");
	else write(ans[i]);
	return 0;
}

练习 (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)$。

代码写起来非常顺畅，几乎没有细节。

查看代码

#include<bits/stdc++.h>
#define rgi register int
#define FOR(i,a,b) for(rgi i=a,i##i=b;i<=i##i;++i)
using namespace std;
typedef long long ll;
const int N=1e5+9;
int n,k,a[N],nl=1,nr;
ll dp[23][N],res,cnt[N];
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){
	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);
	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);
}
signed main(){
	scanf("%d%d",&n,&k),dp[1][0]=1e9;
	FOR(i,1,n)scanf("%d",a+i),dp[1][i]=calc(1,i);
	FOR(i,2,k)solve(i,1,n,1,n),dp[i][0]=1e9;
	printf("%lld",dp[k][n]);
	return 0;
}

整体二分维护不可加贡献

现在回顾例 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)$ 的。

查看代码

#include<bits/stdc++.h>
#define FOR(i,a,b) for(int i=a,i##i=b;i<=i##i;++i)
using namespace std;
const int N=600010;
int n,m,ct[N],T,ans[N],rr[N];
struct mem{int t,p,v;};
struct unf{
	int a[N],C=0;mem f[N];
	int& operator[](int x){return a[x];}
	void st(int x,int v){f[++C]={T,x,a[x]},a[x]=v;}
	void rbk(int t){for(;C&&f[C].t>=t;--C)a[f[C].p]=f[C].v;}
}fa,rk,sz;
int rbk(int t){return fa.rbk(t),rk.rbk(t),sz.rbk(t),T=t-1;}
int fd(int x){return fa[x]==x?x:fd(fa[x]);}
int merge(int x,int y){
	int u=fd(x),v=fd(y);
	if(u==v)return !ct[T];
	if(rk[u]<rk[v])swap(u,v);
	ct[T+1]=ct[T]-(sz[u]&sz[v])*2,++T;
	fa.st(v,u),sz.st(u,sz[u]^sz[v]);
	if(rk[u]==rk[v])rk.st(u,rk[u]+1);
	return !ct[T];
}
struct edge{
	int u,v,w,id;
	bool operator<(edge x)const{return w==x.w?id<x.id:w<x.w;}
	void inp(int d){scanf("%d%d%d",&u,&v,&w),id=d;}
	int add(int x){return id<=x?merge(u,v):0;}
}e[N],q[N];
void solve(int l,int r,int L,int R){
	if(L==R)FOR(i,l,r)ans[i]=L;
	if(l>r||L>=R)return;
	int mid=(l+r)/2,t=T+1,y,p=R;
	FOR(i,l,mid)if(rr[i]<L)q[i].add(N);
	y=T+1;
	FOR(i,L,R)if(e[i].add(mid)){p=i;break;}
	ans[mid]=p,rbk(y),solve(mid+1,r,L,p),rbk(t);
	FOR(i,L,p-1)e[i].add(l-1);
	solve(l,mid-1,p,R),rbk(t);
}
signed main(){
	scanf("%d%d",&n,&m),ct[0]=n,e[m+1]={0,0,-1,N};
	FOR(i,1,n)fa[i]=i,sz[i]=1;
	FOR(i,1,m)e[i].inp(i),q[i]=e[i];
	sort(e+1,e+m+1);
	FOR(i,1,m)rr[e[i].id]=i;
	solve(1,m,1,m+1);
	FOR(i,1,m)printf("%d\n",e[ans[i]].w);
	return 0;
}

练习 (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$，所以它要么在此次被添加，要么没被添加但是对此次答案不影响。

查看代码（完整版）

#include<bits/stdc++.h>
#define rgi register int
#define pbk push_back
#define FOR(i,a,b) for(rgi i=a,i##i=b;i<=i##i;++i)
#define ROF(i,a,b) for(rgi i=a,i##i=b;i>=i##i;--i)
#define mid ((l+r)>>1)
#define lc ls[k]
#define rc rs[k]
#define lson lc,l,mid
#define rson rc,mid+1,r
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int N=2e5+7,inf=1e9+7;
int n,m,Q,T,vl[N],o,u,v,ans[N];
vector<ll>Rs;
int rt[N<<5],ls[N<<5],rs[N<<5],ct[N<<5],C;
ll s[N<<5];
void upd(int x,int v,int w,int& k,int l=0,int r=inf){
	if(l>x||r<x)return;
	s[k?k:k=++C]+=v,ct[k]+=w;
	if(l!=r)upd(x,v,w,lson),upd(x,v,w,rson);
}
ll qry(int x,int& k,int l=0,int r=inf){
	if(!x||!k)return 0;
	if(l==r)return min(ct[k],x)*1ll*l;
	if(ct[rc]>=x)return qry(x,rson);
	return qry(x-ct[rc],lson)+s[rc];
}
int mg(int x,int y){
    if(!x||!y)return x^y;
    ls[x]=mg(ls[x],ls[y]),rs[x]=mg(rs[x],rs[y]);
    return s[x]+=s[y],ct[x]+=ct[y],x;
}
map<pii,int>mp;
struct mem{int t,p,v;};
struct unf{
	int a[N],C=0;mem f[N];
	int& operator[](int x){return a[x];}
	void st(int x,int v){f[++C]={T,x,a[x]},a[x]=v;}
	void rbk(int t){for(;C&&f[C].t>t;--C)a[f[C].p]=f[C].v;}
}fa,rk;
int rbk(int t){return fa.rbk(t),rk.rbk(t),T=t;}
int fd(int x){return fa[x]==x?x:fd(fa[x]);}
void merge(int x,int y){
	int u=fd(x),v=fd(y);
	if(u==v)return;
	if(rk[u]<rk[v])swap(u,v);
	if(rk[u]==rk[v])rk.st(u,rk[u]+1);
	fa.st(v,u);
}
vector<int>a[N],b[N],f;
int vis[N],K;
struct opt{
	int o,u,v,id;
	void work(){
		int F=rt[fd(u)];
		if(o==2)upd(vl[u],-vl[u],-1,F),vl[u]-=v,upd(vl[u],vl[u],1,F);
		if(o==3)Rs.pbk(qry(v,F));
	}
	void link(){
		int x=fd(u),y=fd(v);
		if(x==y)return;
		a[x].pbk(y),b[y].pbk(x);
		if(!vis[x])f.pbk(x),vis[x]=1;
		if(!vis[y])f.pbk(y),vis[y]=1;
	}
}q[N],e[N];
vector<opt>V[N],t;
int sq[N],W;
void dfs(int x){
	vis[x]=1;
	for(rgi to:a[x])if(!vis[to])dfs(to);
	sq[++W]=x;
}
void Dfs(int x){
	vis[x]=0;
	for(rgi to:b[x])if(vis[to])Dfs(to),merge(x,to);
}
void work(){
	for(rgi k:f)vis[k]=0;
	for(rgi k:f)if(!vis[k])dfs(k);
	ROF(i,W,1)if(vis[sq[i]])Dfs(sq[i]);
	for(rgi k:f)a[k].clear(),b[k].clear();
	W=0,f.clear();
}
void solve(int l,int r,vector<opt>t){
	if(e[l].o==e[r].o){
		for(opt k:t)ans[k.id]=e[l].o;
		return;
	}
	vector<opt>L[2];
	int P=T++;
	FOR(i,l,mid)e[i].link();
	for(opt k:t)if(k.o<=e[l].o)k.link();
	work();
	for(opt k:t)L[fd(k.u)==fd(k.v)].pbk(k);
	solve(mid+1,r,L[0]),rbk(P),solve(l,mid,L[1]),rbk(P);
}
int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}
signed main(){
	scanf("%d%d%d",&n,&m,&Q),e[m+1].o=Q+1;
	FOR(i,1,n)scanf("%d",vl+i),fa.a[i]=i;
	FOR(i,1,m)scanf("%d%d",&u,&v),mp[{u,v}]=i,e[i]={0,u,v,0};
	ROF(i,Q,1){
		scanf("%d%d%d",&o,&u,&v),q[i]={o,u,v,i};
		if(o==1)e[mp[{u,v}]].o=i;
		if(o==2)vl[u]+=v;
	}
	sort(e+1,e+m+1,[](opt x,opt y){return x.o<y.o;});
	FOR(i,1,m)e[i].id=i,t.pbk(e[i]);
	solve(1,m+1,t);
	FOR(i,1,m)V[ans[i]].pbk(e[i]);
	FOR(i,1,n)fa[i]=i,upd(vl[i],vl[i],1,rt[i]);
	FOR(i,0,Q){
		for(opt k:V[i]){
			u=find(k.u),v=find(k.v);
			if(u!=v)fa[v]=u,rt[u]=mg(rt[u],rt[v]);
		}
		q[i].work();
	}
	reverse(Rs.begin(),Rs.end());
	for(ll k:Rs)printf("%lld\n",k);
	return 0;
}

总结

从个人视角出发，整体二分这种分治算法的精髓就在于，可以通过简单的手段将需要求解的答案序列分成了两部分递归求解，从递归层数的角度出发保证复杂度正确性。

整体二分思想的运用当然是极为广泛的，如保序回归问题在求解带有限制区间的部分时就运用了整体二分。上文作为入门教程，较为简易而内容不多，提及的只是冰山一角，抛砖引玉。z