算法思想

整體二分，帶有二分二字那么就一定和二分脫不了干系。
整體二分算法常用來解決詢問區間的第$k$小值的問題，思路如下：
我們二分的對象是這道題目給定的值域，及最小值與最大值之間的區間，在題目給定的數組中，對整體的值域進行二分，我們將$mid$作為左右區間的中間值。
比如需要查詢$l$~$r$區間內的第$k$小值。
然后進行一下的判斷。
1.當$l$~$r$區間內小于中值$mid$的值的數量小于當前的查詢$k$，那就說明當前的二分值小了，因為我們需要的是第$k$大，但是現在的$mid$可以求到的第$p$大在前$k$大范圍內，所以還需繼續查，那么就得往大的查，就將區間左側放到當前的$mid$$+$$1$（$mid$的值不合法，所以無需再查）
2.但$l$~$r$區間內小于中值$mid$的值的數量大于等于當前的查詢$k$，那么枚舉到的區間就肯定包含前$k$大的數，所以當前區間可用，將區間右側放到現在的$mid$處（$mid$的值是合法的，存在正確答案）
當最終的區間左右重合時，就得到最終答案了。
而現在是一個查詢的情況，當我們遇到$q$個查詢時，我們就先把查詢存起來，然后就可以將查詢分為兩類，就是上面的兩類，左區間和右區間分別用一個數組存起來，然后分類討論就行了，至于二分，就可以用歸并排序的版子。
還有一個重要的問題：怎么查找區間內比$mid$小的值的數量？
可以考慮用樹狀數組存，在原數組上對樹狀數組進行初始化就可以了。
記得每次遞歸清空樹狀數組，并且原數組的值隨著上面的兩個條件分配到左右兩個區間去！
然后就可以找到一道板子題：P3834 【模板】可持久化線段樹 2
就是詢問的板子，就不用對題目多做分析了。代碼：

#include<bits/stdc++.h>
#define int long long
#define xx x&-x
using namespace std;
const int N=1e6+5;
int n,m;
struct node{int l,r,k,id,op;
}a[N],ql[N],qr[N];
int answer[N];
int bit[N];
int cnt;
void change(int x,int p){while(x<=cnt){bit[x]+=p;x+=xx;}
}
int query(int x){int res=0;while(x){res+=bit[x];x-=xx;}return res;
}
void f(int l,int r,int N,int M){if(N>=M)return;if(l==r){for(int i=N;i<=M;i++){if(a[i].op==2)answer[a[i].id]=r;}return;}int mid=l+r>>1;int t1=0,t2=0;for(int i=N;i<=M;i++){if(a[i].op==1){if(mid>=a[i].l){ql[++t1]=a[i];change(a[i].id,1);}else{qr[++t2]=a[i];}}else{int x=query(a[i].r)-query(a[i].l-1);if(x>=a[i].k){ql[++t1]=a[i];}else{a[i].k-=x;qr[++t2]=a[i];}}}for(int i=1;i<=t1;i++){a[i+N-1]=ql[i];if(ql[i].op==1)change(ql[i].id,-1);}for(int i=1;i<=t2;i++){a[i+N+t1-1]=qr[i];}f(l,mid,N,N+t1-1);f(mid+1,r,N+t1,M);
}
signed main(){ios::sync_with_stdio(0);cin>>n>>m;for(int i=1;i<=n;i++){cin>>a[i].l;a[i].id=i;a[i].op=1;}cnt=n;for(int i=1;i<=m;i++){cnt++;cin>>a[cnt].l>>a[cnt].r>>a[cnt].k;a[cnt].id=i;a[cnt].op=2;}f(-1e9,1e9,1,cnt);for(int i=1;i<=m;i++)cout<<answer[i]<<'\n';
}

然后還有另一道題目：P1527 [國家集訓隊] 矩陣乘法
因為樹狀數組的使用類似前綴和，所以這道題就相當于改成二位前綴和。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+5;
const int M=1005;
int n,m,k;
int T;
struct node{int lx,ly,rx,ry,k,idi,idj,op,id;
}a[N],ql[N],qr[N];
int answer[N];
int bit[M][M];
int cnt;
//快讀快寫好習慣
int read(){int x=0,p=1;char c=getchar();while(c<'0'||c>'9'){if(c=='-')p=-1;c=getchar();}while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();return x*p;
}
void print(int x){if(x<0){putchar('-');x=-x;}if(x<10){putchar(x+'0');return;}print(x/10);putchar(x%10+'0');
}
void change(int x,int y,int p){for(int i=x;i<=n;i+=i&-i)for(int j=y;j<=n;j+=j&-j)bit[i][j]+=p;
}
int query(int x,int y){int res=0;for(int i=x;i;i-=i&-i)for(int j=y;j;j-=j&-j)res+=bit[i][j];return res;
}
void f(int l,int r,int N,int M){if(N>=M)return;if(l==r){for(int i=N;i<=M;i++)if(a[i].op==2)answer[a[i].id]=r;return;}int mid=l+r>>1;int t1=0,t2=0;for(int i=N;i<=M;i++){if(a[i].op==1){if(mid>=a[i].lx){ql[++t1]=a[i];change(a[i].idi,a[i].idj,1);}else{qr[++t2]=a[i];}}else{int x=query(a[i].rx,a[i].ry)+query(a[i].lx-1,a[i].ly-1)-query(a[i].lx-1,a[i].ry)-query(a[i].rx,a[i].ly-1);if(x>=a[i].k){ql[++t1]=a[i];}else{a[i].k-=x;qr[++t2]=a[i];}}}for(int i=1;i<=t1;i++){a[i+N-1]=ql[i];if(ql[i].op==1)change(ql[i].idi,ql[i].idj,-1);}for(int i=1;i<=t2;i++){a[i+N+t1-1]=qr[i];}f(l,mid,N,N+t1-1);f(mid+1,r,N+t1,M);
}
signed main(){ios::sync_with_stdio(0);n=read(),m=read();int tot=0;for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){a[++tot]=node{read(),0,0,0,0,i,j,1,0};}}cnt=tot;for(int i=1;i<=m;i++){cnt++;a[cnt].lx=read(),a[cnt].ly=read(),a[cnt].rx=read(),a[cnt].ry=read(),a[cnt].k=read();a[cnt].op=2;a[cnt].id=i;}f(0,1e9,1,cnt);for(int i=1;i<=m;i++)print(answer[i]),putchar('\n');
}