寫在前面

區間第k小 可以說是一個很經典的數據結構題了，這道題有很多種解法比如莫隊離線、主席樹、整體二分等等。
之前用莫隊和主席樹寫過這道題，今天來學習一個以前不會的算法——整體二分。
因為最近遇到一個類似于整體二分的題目，就是Codeforces里的gym-101741的J題，感覺它的思想和整體二分很像，但又不一樣，做完那道題順便來學習一下整體二分，那就不能不做整體二分的入門題——區間第k小啦。

整體二分使用條件

• 詢問之間是獨立的，可以離線處理詢問。
• 對于單個詢問的回答，可以使用二分答案的方法，并且check的復雜度可以接受。

整體二分思想

由于每個詢問都要進行二分check，因此有很多check是這些詢問都可以使用的，沒必要check很多次。
因此我們把這些區間打包，一起進行處理。
對于區間k小這個問題。
我們二分一個答案midmid。
1. 然后檢查所有的數，如果一個數a[i]<=mida[i]<=mid的話，那么我們就在BITBIT中把ii位置加1，然后把這個數扔到左集合里。否則的話就把這個數扔到右集合里面去。左集合中的數均≤mid≤mid，這樣的話這個集合的數就不會對[mid+1,r][mid+1,r]這個位置里面的待check答案產生影響。右集合的數均>mid>mid，這樣這個集合的數就不會對[l,mid][l,mid]這個位置里面的待check答案產生影響。
2. 我們檢查所有的詢問區間，從BITBIT中統計出當前區間內<=mid<=mid<script type="math/tex" id="MathJax-Element-1831"><= mid</script>的數有cnt個，如果cnt>=kcnt>=k，那么這個詢問應該被扔到左集合里面去。否則這個詢問應該被扔到右集合一面去，并且對應的k?=cntk?=cnt。
3. 當二分到一個區間l==rl==r的時候算法結束，此時所有的剩余的詢問答案均為ll。

時間復雜度為O(n?log(n)?log(S))O(n?log(n)?log(S))
其中SS<script type="math/tex" id="MathJax-Element-1837">S</script>是數的范圍。

注意

這道題如果想在poj上通過則要把vector換成數組，不然會超時（吐槽：poj太落后了）。

POJ2104 參考代碼

#include <iostream> #include <cstdio> #include <vector> #define pr(x) cout<<#x<<":"<<x<<endl using namespace std; const int inf = 1e9+7; const int maxn = 100007; /* struct node{int type,x,y,k,ans; }; */ int e[105007][5]; //e數組的解釋見node結構體 int n,m,tot; int bitree[maxn]; inline int lowbit(int x) {return x & (-x);} void add(int pos,int x){while(pos < maxn){bitree[pos] += x;pos += lowbit(pos);} } int sum(int pos){int ans = 0;while(pos){ans += bitree[pos];pos -= lowbit(pos);}return ans; } void solve(int l,int r,vector<int> qs){//pr(l);pr(r);if(l > r || qs.size() == 0) return ;if(l == r){for(int i = 0;i < qs.size();++i)e[qs[i]][4] = l;return ;}int mid = (l+r)>>1;vector<int> qs1,qs2;for(int i = 0;i < qs.size();++i){int id = qs[i];if(e[id][0] == 0){if(e[id][2] <= mid){add(e[id][1],1);qs1.push_back(id);}elseqs2.push_back(id);}else{int cnt = sum(e[id][2]) - sum(e[id][1]-1);if(cnt >= e[id][3]){qs1.push_back(id);}else{e[id][3] -= cnt;qs2.push_back(id);}} }for(int i = 0;i < qs1.size();++i){int id = qs1[i];if(e[id][0] == 0) add(e[id][1],-1);}solve(l,mid,qs1);solve(mid+1,r,qs2); } vector<int> qs; int main(){cin>>n>>m;for(int i = 1;i <= n;++i){scanf("%d",&e[tot][2]);e[tot][1] = i;qs.push_back(tot++);}for(int i = 0;i < m;++i){e[tot][0] = 1;scanf("%d%d%d",&e[tot][1],&e[tot][2],&e[tot][3]);qs.push_back(tot++);}solve(1,inf,qs);for(int i = 0;i < m;++i){printf("%d\n",e[i+n][4]);}return 0; }

總結

以上是生活随笔為你收集整理的经典题:poj2104-区间第k小 整体二分学习的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。