有一些题目需要用到二分，但多次询问直接二分，会导致 TLE，那么就需要用到一个离线算法，将多个询问放在一起二分，这就是整体二分。
条件
能够用整体二分解决的题目需要满足以下性质：
1.题目具有可二分性（即单调性）；
2.修改对判定答案的贡献相互独立，修改之间互不影响效果。
3.修改如果对判定答案有贡献，则贡献为一个确定的，与判定标准无关的值；
4.贡献满足交换律，结合律，具有可加性；
5.题目允许使用离线算法。
方法
记 \([l,r]\) 为答案的值域，\([L,R]\) 为答案的定义域。
- 首先将所有操作按时间顺序存入数组， 开始分治；
- 在每一层分治中，利用数据结构（一般是树状数组）统计当前查询的答案和 \(mid\) 之间的关系；
- 根据查询出来的答案和 \(mid\) 间的关系（小于等于 \(mid\) 和大于 \(mid\)）将当前处理的操作序列分为 \(q1\) 和 \(q2\) 两部分，分别递归处理；
- 当 \(l=r\) 时，找到答案，记录答案并返回即可。
需要注意的是，在整体二分的过程中，若当前处理的值域为 \([l,r]\)，则此时最终答案范围不在 \([l,r]\) 的询问会在其他时候处理。
求全局第 \(k\) 小（多次询问）
可以对于每个询问进行一次二分；但是，也可以把所有的询问放在一起二分。
先考虑二分的本质：假设要猜一个 \([l,r]\) 之间的数，猜测答案是 \(m = \lfloor\frac{l + r}{2}\rfloor\)，然后去验证 \(m\) 的正确性，再调整边界。这样做每次询问的复杂度为 \(\Theta(\log n)\)，若询问次数为 \(q\)，则时间复杂度为 \(\Theta(q\log n)\)。
回过头来，对于当前的所有询问，可以去猜测所有询问的答案都是 \(mid\)，然后去依次验证每个询问的答案应该是小于等于 \(mid\) 的还是大于 \(mid\) 的，并将询问分为两个部分，对于每个部分继续二分。
注意：如果一个询问的答案是大于 \(mid\) 的，则在将其划至右侧前需更新它的 \(k\)，即，如果当前数列中小于等于 \(mid\) 的数有 \(t\) 个，则将询问划分后实际是在右区间询问第 \(k - t\) 小数。如果一个部分的 \(l = r\) 了，则结束这个部分的二分。利用线段树的相关知识，我们每次将整个答案可能在的区间 \([1,maxans]\) 划分成了若干个部分，这样的划分共进行了 \(\Theta(\log maxans)\) 次，一次划分会将整个操作序列操作一次。若对整个序列进行操作，并支持对应的查询的时间复杂度为 \(\Theta(T)\)，则整体二分的时间复杂度为 \(\Theta(T\log n)\)。
求区间第 \(k\) 小（多次询问）
涉及到给定区间的查询，再按之前的方法进行二分就会导致 check 函数的时间复杂度爆炸。仍然考虑询问与值域中点 \(m\) 的关系：若询问区间内小于等于 \(m\) 的数有 \(t\) 个，询问的是区间内的 \(k\) 小数，则当 \(k \leqslant t\) 时，答案应小于等于 \(m\)；否则，答案应大于 \(m\)。
此处需记录一个区间小于等于指定数的数的数量，即单点加，求区间和，可用树状数组快速处理。为提高效率，只对数列中值在值域区间 \([l,r]\) 的数进行统计，即，在进一步递归之前，不仅将询问划分，将当前处理的数按值域范围划为两半。
例题 P3834【模板】可持久化线段树 2
点击查看代码
#include<bits/stdc++.h>
using namespace std;
const int MAXN=4e5+5;
const int INF=0x7f7f7f7f;
struct Query
{
int l,r,k,id,type;
}q[MAXN],q1[MAXN],q2[MAXN];
int t[MAXN],ans[MAXN];
int n,m,cnt;
inline int lowbit(int x) {return x&-x;}
inline void add(int x,int k)
{
for(int i=x;i<=MAXN;i+=lowbit(i)) t[i]+=k;
return;
}
inline int ask(int x)
{
int res=0;
for(int i=x;i>=1;i-=lowbit(i)) res+=t[i];
return res;
}
inline void solve(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].type==2) ans[q[i].id]=l;
return;
}
int mid=(l+r)>>1,cnt1=0,cnt2=0;
for(int i=ql;i<=qr;i++)
{
if(q[i].type==1)
{
if(q[i].l<=mid)
{
add(q[i].id,1);
q1[++cnt1]=q[i];
}
else q2[++cnt2]=q[i];
}
else
{
int res=ask(q[i].r)-ask(q[i].l-1);
if(res>=q[i].k) q1[++cnt1]=q[i];
else q[i].k-=res,q2[++cnt2]=q[i];
}
}
for(int i=1;i<=cnt1;i++)
if(q1[i].type==1) add(q1[i].id,-1);
for(int i=1;i<=cnt1;i++) q[ql+i-1]=q1[i];
for(int i=1;i<=cnt2;i++) q[ql+i+cnt1-1]=q2[i];
solve(l,mid,ql,ql+cnt1-1),solve(mid+1,r,ql+cnt1,qr);
return;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
cin>>n>>m;
for(int i=1;i<=n;i++)
{
int x; cin>>x;
q[++cnt]={x,x,0,i,1};
}
for(int i=1;i<=m;i++)
{
int l,r,k; cin>>l>>r>>k;
q[++cnt]={l,r,k,i,2};
}
solve(-INF,INF,1,cnt);
for(int i=1;i<=m;i++) printf("%d\n",ans[i]);
return 0;
}