1 概念

在很多题目中，我们可以使用二分法来得出答案。但是如果说这一类题目有多次询问，并且多次询问分别二分会 TLE 时，我们就需要引入一个东西叫整体二分。

整体二分的主要思路就是将多个查询一起解决，因此它是一种离线算法。

整体二分的具体操作步骤如下：

首先记 \([l,r]\) 为答案的值域，\([L,R]\) 是答案的定义域。这代表着我们在求答案时考虑下标在 \([L,R]\) 上的操作，这当中的询问的答案都在 \([l,r]\)。

首先我们现将所有操作按照时间轴存入数组，然后开始分治。在每一层分治中，我们利用一些东西统计当前查询的答案和 \(mid\) 的关系。

根据这个关系（小于等于 \(mid\) 和大于 \(mid\)），我们将操作序列分成两半，然后递归处理。

那么我们通过例题来具体了解整体二分的过程。

2 基础例题

2.1 静态全局第 k 小

在一个数列中查询第 \(k\) 小的数。

显然我们可以直接排序。那如果用二分呢？我们可以二分数字，然后查询这个数字的排名；这样看上去有点多此一举，我们看下一题。

在一个数列中多次查询第 \(k\) 小的数。

我们可以分开二分，但是也可以放在一起二分。

首先我们可以假设当前所有询问的答案都是 \(mid\)，然后我们一次判断真正的答案与 \(mid\) 的关系。也就是应该小于等于 \(mid\) 还是大于 \(mid\)，并分成两个部分。假如原先我们查询的值域为 \([l,r]\)，那么现在两个区间的值域就是 \([l,mid],(r,mid]\)。在值域里继续二分查找，直到 \(l=r\)。

可以理解为我们本来是一个一个二分，现在我们将他们放到一起同时做，这样可以省去当中重复运算的时间。

2.2 静态区间第 k 小

我们来看一道模板题：【模板】可持久化线段树 2。我们发现这是一道静态查询区间第 \(k\) 小问题，可以考虑整体二分。

我们在每一次二分中利用树状数组记录下当前区间内小于等于 \(mid\) 的数有哪些，用这个来帮助计算区间中小于等于指定数的数量。同时，为了提高效率，我们可以在统计时只对值域在 \([l,r]\) 之间的数进行统计，将他们单独拿出来之后在上面做二分。

时间复杂度 \(O(n\log ^2 n)\)，比主席树 \(O(n\log n)\) 较劣。但是仍然可以过掉上面的模板题。

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;
const int Maxn = 5e5 + 5;

int n, m;
int mn = 2e9, mx;
struct node {
	int opt, l, r, k, id;
}q[Maxn], q1[Maxn], q2[Maxn];

int tot = 0;
int ans[Maxn];

struct BIT {
	int c[Maxn];
	int lowbit(int x) {
		return x & (-x);
	}
	void mdf(int x, int val) {
		for(int i = x; i <= n; i += lowbit(i)) {
			c[i] += val;
		}
	}
	int query(int x) {
		int sum = 0;
		for(int i = x; i; i -= lowbit(i)) {
			sum += c[i];
		}
		return sum;
	}
}B;

void obs(int l, int r, int pl, int pr) {
    //[l,r] 是答案值域，[pl,pr] 是当前二分的查询区间
	if(pl > pr) return ;
	if(l == r) {
		for(int i = pl; i <= pr; i++) {//答案全部为 l
			if(q[i].opt == 2) {
				ans[q[i].id] = l;
			}
		}
		return ;
	}
	int mid = (l + r) >> 1, p1 = 0, p2 = 0;
	for(int i = pl; i <= pr; i++) {
		if(q[i].opt == 1) {//是修改操作
			if(q[i].k <= mid) {//与 mid 比较
				B.mdf(q[i].id, 1);//更新树状数组
				q1[++p1] = q[i];//比 mid 小的放到左半部分
			}
			else {
				q2[++p2] = q[i];//比 mid 大的放到右半部分
			}
		}
		else {
			int x = B.query(q[i].r) - B.query(q[i].l - 1);//查询当前区间内 mid 的排名
			if(q[i].k <= x) {
				q1[++p1] = q[i];//比 mid 小的放到左半部分
			} 
			else {
				q[i].k -= x;//注意右半部分在计算之前要减掉左半部分的贡献
				q2[++p2] = q[i];//比 mid 大的放到右半部分
			}
		}
	}
	for(int i = 1; i <= p1; i++) {
		if(q1[i].opt == 1) {
			B.mdf(q1[i].id, -1);
		}
	}
	for(int i = 1; i <= p1; i++) {
		q[pl + i - 1] = q1[i];
	}
	for(int i = 1; i <= p2; i++) {
		q[pl + p1 + i - 1] = q2[i];
	}
	obs(l, mid, pl, pl + p1 - 1);
	obs(mid + 1, r, pl + p1, pr);//分治求解
}

int main() {
	ios::sync_with_stdio(0);
	cin >> n >> m;
	for(int i = 1; i <= n; i++) {
		int p;
		cin >> p;
		mn = min(mn, p), mx = max(mx, p);
		q[++tot] = {1, -1, -1, p, i};
	}
	for(int i = 1; i <= m; i++) {
		int l, r, k;
		cin >> l >> r >> k;
		q[++tot] = {2, l, r, k, i};
	}
	obs(mn, mx, 1, tot);
	for(int i = 1; i <= m; i++) {
		cout << ans[i] << '\n';
	}
	return 0;
}

二维区间最小值例题：[国家集训队] 矩阵乘法。

2.3 带修区间第 k 小

例题：Dynamic Rankings。

我们发现这样一个问题：上面我们求静态区间第 k 小的时候已经将初始序列当做了插入操作，那么我们再做带修区间第 k 小的时候应该比较容易。

首先，一次修改操作可以看做是一次删除和一次插入操作组成的。而删除与查询操作本质上都是一样的，无非就是在树状数组上加一减一的区别。

代码与静态区间第 k 小的非常相似，如下：

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;
const int Maxn = 5e5 + 5;

int n, m, a[Maxn];
int mn = 2e9, mx;
struct node {
	int opt, l, r, k, id;
}q[Maxn], q1[Maxn], q2[Maxn];

int tot, cnt;

struct BIT {
	int c[Maxn];
	int lowbit(int x) {
		return x & (-x);
	}
	void mdf(int x, int val) {
		for(int i = x; i <= n; i += lowbit(i)) {
			c[i] += val;
		}
	}
	int query(int x) {
		int sum = 0;
		for(int i = x; i; i -= lowbit(i)) {
			sum += c[i];
		}
		return sum;
	}
}B;

int ans[Maxn];

void obs(int l, int r, int ql, int qr) {
	if(ql > qr) return ;
	if(l == r) {
		for(int i = ql; i <= qr; i++) {
			if(q[i].opt == 3) {
				ans[q[i].id] = l;
			}
		}
		return ;
	}
	int mid = (l + r) >> 1, p1 = 0, p2 = 0;
	for(int i = ql; i <= qr; i++) {
		if(q[i].opt == 3) {
			int x = B.query(q[i].r) - B.query(q[i].l - 1);
			if(q[i].k <= x) {
				q1[++p1] = q[i];
			}
			else {
				q[i].k -= x;
				q2[++p2] = q[i];
			}
		}
		else {
			if(q[i].k <= mid) {
				if(q[i].opt == 1) B.mdf(q[i].id, 1);
				else B.mdf(q[i].id, -1);
				q1[++p1] = q[i]; 
			}
			else {
				q2[++p2] = q[i];
			}
		}
	}
	for(int i = 1; i <= p1; i++) {
		if(q1[i].opt == 1) B.mdf(q1[i].id, -1);
		else if(q1[i].opt == 2) B.mdf(q1[i].id, 1);
	}
	for(int i = 1; i <= p1; i++) {
		q[ql + i - 1] = q1[i]; 
	}
	for(int i = 1; i <= p2; i++) {
		q[ql + p1 + i - 1] = q2[i];
	}
	obs(l, mid, ql, ql + p1 - 1);
	obs(mid + 1, r, ql + p1, qr);
}

int main() {
	ios::sync_with_stdio(0);
	cin >> n >> m;
	for(int i = 1; i <= n; i++) {
		int p;
		cin >> p;
		mn = min(mn, p), mx = max(mx, p);
		a[i] = p;
		q[++tot] = {1, -1, -1, p, i};
	}
	for(int i = 1; i <= m; i++) {
		char opt;
		int l, r, k;
		cin >> opt >> l >> r;
		if(opt == 'C') {
			mn = min(mn, r), mx = max(mx, r);
			q[++tot] = {2, -1, -1, a[l], l};
			q[++tot] = {1, -1, -1, r, l};
			a[l] = r;
		}
		else {
			cin >> k;
			q[++tot] = {3, l, r, k, ++cnt};
		} 
	}
	obs(mn, mx, 1, tot);
	for(int i = 1; i <= cnt; i++) {
		cout << ans[i] << '\n';
	}
	return 0;
}