整体二分，顾名思义就是在整体上二分。
可以使用整体二分解决的题目需要满足以下性质：
询问的答案具有可二分性。
修改对判定答案的贡献互相独立，修改之间互不影响效果。
修改如果对判定答案有贡献，则贡献为一确定的与判定标准无关的值。
贡献满足交换律，结合律，具有可加性
题目允许使用离线算法。
——许昊然《浅谈数据结构题几个非经典解法》
与其说整体二分是一种二分，不如说它是一种分治。
设函数 表示询问 的答案在区间 中。将该区间 划分为 两个子区间，利用数据结构处理 ，并将询问分成 与 两组子询问。与线段树建树相同的方式递归处理 。
给定 个整数构成的序列 ，将对于指定的闭区间 查询其区间内的第 小值。
先考虑 时怎么做。
不难想到单次询问二分第 小值，通过 来获得答案。
设值域大小为 ，时间复杂度 。
考虑满分做法。
题目允许离线，且答案单调，考虑整体二分做法。
我们设 表示 对应的原询问编号， 表示关于询问 ，在当前值域左侧已经确定的、比答案小的数字的总个数。
设 表示询问 的答案在 中。函数内部，我们将 的数染黑，利用树状数组结合 计算询问区间内黑点个数，递归处理左右区间。
::::info[时间复杂度证明]{open}
通过观察，发现 的的移动次数为 。由于函数内部套了一层树状数组，总时间复杂度应乘上一只 。又因为每层遍历了一次 ，所以总时间复杂度为 。
::::
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+7;
int n;
struct BIT{
int tr[N];
int lowbit(int x){
return x&-x;
}
void add(int x,int c){
while(x<=n){
tr[x]+=c;
x+=lowbit(x);
}
}
int query(int x){
int res=0;
while(x>0){
res+=tr[x];
x-=lowbit(x);
}
return res;
}
}bit;
int cas;
struct node{
int v,id;
bool operator<(node a)const{
return v<a.v;
}
}a[N];
struct Q{
int l,r,k;
}q[N];
int q1[N],q2[N],id[N],ans[N],cur[N];
void Solve(int l,int r,int ql,int qr){
if(ql>qr)return;
if(l==r){
for(int i=ql;i<=qr;i++)ans[id[i]]=a[l].v;
return;
}
int mid=(l+r)/2;
for(int i=l;i<=mid;i++)bit.add(a[i].id,1);
int cnt1=0,cnt2=0;
for(int i=ql;i<=qr;i++){
int sum=cur[id[i]]+bit.query(q[id[i]].r)-bit.query(q[id[i]].l-1);
if(sum>=q[id[i]].k)q1[++cnt1]=id[i];
else q2[++cnt2]=id[i],cur[id[i]]=sum;
}
for(int i=l;i<=mid;i++)bit.add(a[i].id,-1);
int qcnt=ql-1;
for(int i=1;i<=cnt1;i++)id[++qcnt]=q1[i];
for(int i=1;i<=cnt2;i++)id[++qcnt]=q2[i];
Solve(l,mid,ql,ql+cnt1-1);
Solve(mid+1,r,ql+cnt1,qr);
}
void solve(){
//start
cin.tie(0)->ios::sync_with_stdio(0);
cout.tie(0);
cin>>n>>cas;
for(int i=1;i<=n;i++){
cin>>a[i].v;
a[i].id=i;
}
sort(a+1,a+n+1);
for(int i=1;i<=cas;i++)cin>>q[i].l>>q[i].r>>q[i].k,id[i]=i;
Solve(1,n,1,cas);
for(int i=1;i<=cas;i++)cout<<ans[i]<<'\n';
}
signed main(){
solve();
return 0;
}
给你一个 的矩阵，不用算矩阵乘法，但是每次询问一个子矩形的第 小数。
考虑 的数据。
不难想到暴力二分，遍历矩阵，计算 的数的个数。
设 为值域上界，总体时间复杂度为 。
考虑 的数据。
发现与普通区间 kth 的区别在于这题的 是二维的。
同样，我们可以将 存成一维数组形式，利用二维树状数组来整体二分。
设 表示询问 的答案在 中（此处 指一维数组）。函数内部，我们将 的数染黑，利用二维树状数组结合 计算询问区间内黑点个数，递归处理左右区间。
由于二维树状数组单次修改查询是 的，所以时间复杂度为 。
#include<bits/stdc++.h>
using namespace std;
const int N=507,M=6e4+7;
int tr[N][N],id[M],n;
int lowbit(int x){
return x&-x;
}
void add(int x,int y,int c){
for(int i=x;i<=n;i+=lowbit(i)){
for(int j=y;j<=n;j+=lowbit(j)){
tr[i][j]+=c;
}
}
}
int query(int x,int y){
int res=0;
for(int i=x;i>0;i-=lowbit(i)){
for(int j=y;j>0;j-=lowbit(j)){
res+=tr[i][j];
}
}
return res;
}
struct node{
int x,y,v;
bool operator<(node a)const{
return v<a.v;
}
}mat[N*N];
struct Q{
int x_1,y_1,x_2,y_2,k;
}q[M];
int cas,cur[M],q1[M],q2[M],ans[M];
int get(int x,int y){
return (x-1)*n+y;
}
void Solve(int l,int r,int ql,int qr){
if(ql>qr)return;
if(l==r){
for(int i=ql;i<=qr;i++)ans[id[i]]=mat[l].v;
return;
}
int mid=(l+r)>>1;
int cnt1=0,cnt2=0;
for(int i=l;i<=mid;i++)add(mat[i].x,mat[i].y,1);
for(int i=ql;i<=qr;i++){
int sum=query(q[id[i]].x_2,q[id[i]].y_2)-query(q[id[i]].x_1-1,q[id[i]].y_2)-
query(q[id[i]].x_2,q[id[i]].y_1-1)+query(q[id[i]].x_1-1,q[id[i]].y_1-1);
int num=cur[id[i]]+sum;
if(num>=q[id[i]].k)q1[++cnt1]=id[i];
else q2[++cnt2]=id[i],cur[id[i]]=num;
}
for(int i=l;i<=mid;i++)add(mat[i].x,mat[i].y,-1);
int qcnt=ql;
for(int i=1;i<=cnt1;i++)id[qcnt++]=q1[i];
for(int i=1;i<=cnt2;i++)id[qcnt++]=q2[i];
Solve(l,mid,ql,ql+cnt1-1);
Solve(mid+1,r,ql+cnt1,qr);
}
void solve(){
//start
cin.tie(0)->ios::sync_with_stdio(0);
cout.tie(0);
cin>>n>>cas;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
int x;
cin>>x;
mat[get(i,j)]={i,j,x};
}
}
sort(mat+1,mat+n*n+1);
for(int i=1;i<=cas;i++){
cin>>q[i].x_1>>q[i].y_1>>q[i].x_2>>q[i].y_2>>q[i].k;
id[i]=i;
}
Solve(1,n*n,1,cas);
for(int i=1;i<=cas;i++)cout<<ans[i]<<endl;
}
int main(){
solve();
return 0;
}