# 整體二分 顧名思義 : 全部的二分搜一起做就叫做整體二分，可以用來求區間第$k$小。 區間第$k$小也可以用另一個方法做 : [持久化線段樹](/K8qTIlbaTuWijADAnTDtGw) ### 用二分搜求整個數列的第$k$小 假設質域最大到$C$，那就可以用$[1,C]$來二分搜，如果$k$比序列中小於等於$mid$的數量小，代表第$k$小的數字會小於或等於$mid$，就往左搜，否則往右搜。 ```cpp= 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 ```cpp= 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$。 ```cpp= 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$。 ```cpp= 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的數字)就不會再被用到，可以只遞迴該邊的數字即可，節省時間。 ```cpp= 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); } ``` 回圈版本 : 只能用在更新要照順序時 ```cpp= 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; } } } ```