P3834 【模板】可持久化線段樹 2（主席樹）

我們詳細講講這個整體二分如何求區間第k小
我們都知道二分可以求出區間里某個想要的值，如果有很多詢問，我們對每個詢問都進行二分，復雜度就是O(QNlog(1e9))鐵超，那怎么優化呢？
我們先看第一個圖
對于7個數的區間[1,5,2,6,3,7,4]，我們有兩個詢問，[2,5]的第3小，[4,4]的第1小
我們先對區間[2,5]進行二分，會得到：
[1,7] mid=4 n=2<3,(這里3是我們要求的第3小數，2指的是區間[2,5]內<=mid的數量)
[5,7] mid=6 n=4>=3(以下同里)
[5,6] mid=5 n=3 >=3
[5,5]->（l == r）ans = 5
然后我們對區間[4,4]二分，也會得到差不多的過程：
[1,7] mid=4 n=0<1
[5,7] mid=6 n=1>=1
[5,6] mid=5 n=0<1
[6,6]–>ans=6
我們剛才說過對于每個區間二分是不行的，因為會超時，現在我們對這兩個過程進行對比，發現有大量過程是在同一個而區間進行的，都會到[1,7],[5,7],[5,6]這三個區間，所以整體二分的含義就是將所有區間當作一個整體二分。

現在看圖2：
數組[1,5，2，6，3，7，4]
我們現在要進行三次查詢，分別是：
[2,5] 3
[4,4] 1
[1,7] 3
我們現在開始模擬過程：
一開始二分區間[1,7] mid=4
[2,5] K=3 n=2<K
[4,4] K=1 n=0<K
[1,7] K=3 n=4>=K
n<mid的向右繼續尋找，n>=mid向右尋找
[1,7] K=3就向左找，此時尋找區間就變成[1,4] mid=2 ,此時n=2<K,向右找，一直到區間左右一樣
[2,5]和[4,4]向右找，向右找時K是要減去n的，相當于左邊已經有n個小于K的值，我們去右邊只需要找第K-n的值就可以了
此時區間為[5,7]mid=6
[2,5] K=1 n=2>=K
[4,4] K=1 n=1>=K
繼續上述過程
最終會形成一個類似樹的結構，看看圖就知道了，這樣復雜度就優化了
n的計算要用得到樹狀數組
復雜度為：O(QlogNlog(1e9))
logN為樹狀數組，log(1e9)為二分

代碼中的lq和rq數組就是將在每次二分中，將詢問區間分成兩部分，就如圖2中將
[2,5] K=3 n=2<K
[4,4] K=1 n=0<K
[1,7] K=3 n=4>=K
這三個操作，將前兩個分為一組，第三個分為另一組

代碼：

#pragma optimize("Ofast") #include<bits/stdc++.h> #define MAXN 400005 #define inf int(1e9) using namespace std; typedef long long ll;int N,M; struct Node{int op,x,y,k;//op=insert+1/remove-1,query2int id;Node(int op=0, int x=0, int y=0, int k=0, int id=0):op(op), x(x), y(y), k(k), id(id){} } q[MAXN],lq[MAXN],rq[MAXN];// int fw[MAXN]; inline int lbt(int x){return x&(-x); }inline void change(int x, int dv){for(;x<=N;x+=lbt(x)){fw[x] += dv;} }inline int query(int x){int ans = 0;for(;x>0;x-=lbt(x)){ans += fw[x];}return ans; } // int ANS[MAXN];void solve(int vl, int vr, int ql, int qr){//cerr<<"solve: "<<vl<<" "<<vr<<" "<<ql<<" "<<qr<<endl;if(ql > qr) return;if(vl == vr){for(int i=ql;i<=qr;i++){if(q[i].op==2) ANS[q[i].id] = vl;}return;}//insertint mid = (vl + vr)>>1;int nl = 0, nr = 0;for(int i=ql;i<=qr;i++){if(q[i].op != 2){//insert/removeif(q[i].x <= mid) change(q[i].y, q[i].op), lq[++nl] = q[i];else rq[++nr] = q[i];}else{//queryint n = query(q[i].y) - query(q[i].x-1);if(q[i].k <= n) lq[++nl] = q[i];else{q[i].k -= n;rq[++nr] = q[i];}}}//removefor(int i=ql;i<=qr;i++){if(q[i].op != 2){if(q[i].x <= mid) change(q[i].y, -q[i].op);}}for(int i=1;i<=nl;i++) q[ql+i-1] = lq[i];for(int i=1;i<=nr;i++) q[ql+nl+i-1] = rq[i];solve(vl, mid, ql, ql+nl-1);solve(mid+1, vr, ql+nl, qr); }int main(){scanf("%d%d", &N, &M);int x,l,r,k;;for(int i=1;i<=N;++i){scanf("%d", &x);q[i] = Node(1,x,i);}for(int i=1;i<=M;i++){scanf("%d%d%d", &l, &r, &k);q[N+i] = Node(2,l,r,k,i);}solve(-1e9,1e9,1,N+M);for(int i=1;i<=M;i++){printf("%d\n", ANS[i]);}return 0; }

總結

以上是生活随笔為你收集整理的P3834 【模板】可持久化线段树 2（整体二分做法）的全部內容，希望文章能夠幫你解決所遇到的問題。

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