整体二分较详讲解

看了前面所说的求第 K K K 大/小问题,在这里就不多赘述了.

先浅浅的谈一谈二分答案（如果会二分答案请直接调到整体二分部分）

二分答案

二分答案就是在答案满足单调性的时候优化 O ( N ) O(N) O(N) 的枚举答案暴力变为指数级的 O ( log ⁡ n ) O(\log_n) O(logn​)（有可能不止 O ( N ) O(N) O(N) 因为还有判断操作所以大部分暴力复杂度均为 O ( M N ) O(MN) O(MN) 甚至更高）适用于题目中让求最大\最小值问题且答案不唯一且有单调性

以枚举最小值为例
伪代码

int l=1 , r=答案最大的边界 ；// R 不判断是否合规
while(l<=r){
   
	int mid=(l+r)>>1 ;   //等同于(l+r)/2 ;
  if(mid满足答案要求) r = mid ; // 也可以为 r=mid-1 但是要单独用一个变量来存储 mid 当然也可以直接输出 r-1
  else l = mid+1 ; // 这里是不能写作 l=mid 否则会进入死循环
}
cout << r ;

先来一道例题试试水

例0

P1902 刺杀大使

这是一个很经典的利用答案的单调性枚举答案最小值的一道题目，判断答案就用dfs不会炸。

代码（可能有亿点丑）

#include<bits/stdc++.h>
using namespace std ;
long long n , m , a[1234][1234] , ans=0 ;
bool t[1234][1234] , ant ;
inline void dfs(long long x,long long y,long long num){
   
	if(x<1||y<1||x>n||y>m||t[x][y]||a[x][y]>num||ant) return ;
	if(x==n){
   ant=1 ; return;}
	t[x][y] = 1 ;
	dfs(x+1,y,num) ;
	dfs(x-1,y,num) ;
	dfs(x,y+1,num) ;
	dfs(x,y-1,num) ;
}
bool check(int num){
   
	ant = 0 ;
	memset(t,0,sizeof(t)) ;
	dfs(1,1,num) ;
	return ant ;
}
int main(){
   
	cin >> n >> m ;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			scanf("%lld",a[i]+j) ;
	int l=1 , r=10000 ;
	while(l<=r){
   
		int mid = (l+r)>>1 ;
		if(check(mid)){
   
			r = mid-1 ;
			ans = mid ;
		}else{
   
			l = mid+1 ;
		}
	}
	cout << ans ;
	return 0 ;
}

看了整体二分前提二分答案，现在让我们来看看整体二分怎么做。（可以去参考一下线段树二分）

整体二分

整体二分,其实上是在 M M M 个询问中离线处理答案的算法,差不多算是在线使用 M M M 次二分答案的简便方法,所以整体二分的本质就是在同时二分 M M M 个答案,我们先定义一个函数 s o l v e ( l , r , L , R ) solve(l,r,L,R) solve(l,r,L,R) 其中 l l l 、 r r r 表示目前的答案在这个区间内， L L L、 R R R 表示是目前操作数组 a i a_i ai​ 满足在这个区间内的操作。

在整体二分合规的操作数组 a i a_i ai​ 中用 m i d mid mid( m i d = ⌊ l + r 2 ⌋ mid= \lfloor \frac{l+r}{2} \rfloor mid=⌊2l+r​⌋)表示答案。如果是修改操作，那么就将满足答案需求的 a i a_i ai​