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++) {//答案全部为 lif(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;
}
