changed 2 years ago  
Published Linked with GitHub

整體二分

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

用二分搜求整個數列的第\(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小，可以先預處理 :

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];

如果有很多個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;
		}
	}
}
Select a repo