# 整體二分
顧名思義 : 全部的二分搜一起做就叫做整體二分，可以用來求區間第$k$小。
區間第$k$小也可以用另一個方法做 : [持久化線段樹](/K8qTIlbaTuWijADAnTDtGw)

### 用二分搜求整個數列的第$k$小
假設質域最大到$C$，那就可以用$[1,C]$來二分搜，如果$k$比序列中小於等於$mid$的數量小，代表第$k$小的數字會小於或等於$mid$，就往左搜，否則往右搜。

int l=1,r=MAXC;
while(l<r){
    int mid=(l+r)/2;
    if(k<=pref[mid]) r=mid;
    else l=mid+1;
}
cout << l << '\n';  //answer

pref[i]為有幾個數比i小，可以先預處理 :
:::spoiler pref

for(int i=0;i<n;i++){
    cin >> a[i];
    cnt[a[i]]++;
}
for(int i=1;i<=C;i++) pref[i]=pref[i-1]+cnt[i];

:::
<br>

### 如果有很多個query呢 ?
那就全部一起做，初始$l,r$都是$1,C$，每做一次每個查詢的範圍都會除以$2$，並維護每個查詢的左右界，直到$l=r$。

bool done=true;
do{
    done=true;
    for(auto &[l,r,k]:q){
        if(l<r){
            done=false;
            int mid=(l+r)/2;
            if(k<=pre[mid]) r=mid;
            else l=mid+1;
        }
    }
}while(!done);
for(auto [l,r,k]:q) cout << l << '\n';

遞迴版本 : 把要往左子樹遞迴的綁成一堆，往右子樹遞迴的綁成一堆，分別遞迴。遞迴到底的時候代表這組$Query$的答案就是$l$或$r$。

void cur(int l,int r,vector<Q> q){
    if(q.empty()) return;
    
    if(l==r){
        for(auto i:q) ans[i.pos]=l;
        return;
    }
    int mid=(l+r)/2;
    vector<Q> qL,qR;
    for(auto i:q){
        if(i.k<=pref[mid]) qL.pb(i);
        else qR.pb(i);
    }
    cur(l,mid,qL);
    cur(mid+1,r,qR);
}

### 那如果每個$Query$都有範圍限制呢 ?
在查詢的時候就不是用$pref$了，因為預處理的時間複雜度及空間複雜度沒有很好，所以就直接在當下計算區間中有幾個數比$mid$還小，因為要計算區間合，我們就可以使用差分的概念，差分要用到前綴合，為了可以快速計算前綴合，還要使用到BIT。

### 實作
在每次遞迴的層中，先把<=$mid$的數字的位置update到BIT裡，也就是在$pos$的位置+1，這樣在求區間$[l,r]$<=$mid$的個數時就可以用$pref[r]-pre[l-1]$的方法來計算，因為被update進去的都是<=$mid$的數字，加上BIT的前綴合功能，可以很輕易地得知在前綴中有多少數字<=$mid$。

在決定要往左或往右遞迴後，另一邊的數字(假設往左遞迴的話，就是>mid的數字)就不會再被用到，可以只遞迴該邊的數字即可，節省時間。

void go(int l,int r,vector<Num> num,vector<Q> q){
	if(l==r){
		for(auto [lb,rb,k,i]:q) ans[i]=l;
		return;
	}
	
	//先把<=mid的數字更新到BIT
	int mid=(l+r)/2;
	vector<Num> ltmid,gtmid;
	for(auto i:num){ 
		if(i.val<=mid) update(i.pos,1);
		
		//往下的遞迴只會用到的其中一邊的元素，先記錄起來
		if(i.val<=mid) ltmid.pb(i);
		else gtmid.pb(i);
	}
	
	//判斷第k小在左邊還右邊
	vector<Q> go_l,go_r;
	for(auto [lb,rb,k,i]:q){
		int L_num=query(rb)-query(lb-1);  //計算區間<=mid的數字的數量和
		
		if(k<=L_num) go_l.pb({lb,rb,k,i});
		else go_r.pb({lb,rb,k-L_num,i});
	}
	
	//因為只有<=mid的數字才會被更新到BIT，所以跑ltmid即可
	for(auto i:ltmid) update(i.pos,-1);  //clear BIT
	
	go(l,mid,ltmid,go_l);
	go(mid+1,r,gtmid,go_r);
}

回圈版本 : 只能用在更新要照順序時

bool done=false;
while(true){
	vector<int> todo(n);
	for(int i=0;i<qt;i++){  //iterator all query
		if(q[i].l<q[i].r){
			done=false;
			int mid=(q[i].l+q[i].r)/2;
			todo[mid].push_back(i);
		}
	}

	if(done) break;

	int sum=0;
	for(int i=0;i<n;i++){
		update(a[i]);  //update to BIT or something
		sum=query(i);  //get prefix
		for(auto j:todo[i]){
			if(sum<=q[j].need) q[j].r=mid;
			else q[j].l=mid+1;
		}
	}
}