所謂整體二分，就是對整體進行二分

（逃）

前言

又是一個狂艸樹套樹的小清新分治算法
但是樹套樹不需要動腦啊
整體二分有一些比較重要的條件：

修改對判定答案的貢獻互相獨立，修改之間互不影響效果

修改如果對判定答案有貢獻，則貢獻為一確定的與判定標準無關的值

貢獻滿足交換律，結(jié)合律，具有可加性

允許離線

解析

作為一個偏思想的輕算法，流程較為易于理解
為了方便闡述，直接以動態(tài)區(qū)間第k大為例（個人感覺那些抽象的流程總結(jié)并沒有一個示例有效）

我們可以把所有的信息都看作順次進行的操作
操作分為修改和查詢
而修改又分為插入和刪除
比如，一開始給出的數(shù)列相當于n次插入
每次修改值就等價于一次刪除和一次插入

考慮一個遞歸分治函數(shù)：solve(l,r,ql,qr)
表示答案區(qū)間在 (l,r) ，處理的操作區(qū)間是 (ql,qr)
首先，如果 ql>qr，沒有需要操作的區(qū)間了，直接返回
若 l=r，說明答案已經(jīng)確定，記錄答案并返回

否則，二分一個答案為 mid

對于所有修改，若其不超過 mid，就在樹狀數(shù)組上對應位置+1并把操作歸于左區(qū)間
否則把操作歸于右區(qū)間

對于所有查詢 (l,r,) 的第 k 大，若樹狀數(shù)組 (l,r) 的和大于 k ，就歸于左區(qū)間，否則把 k 減去樹狀數(shù)組里的數(shù)，并歸到右區(qū)間

最后，把所有的樹狀數(shù)組修改撤銷，并向兩個區(qū)間遞歸即可

遞歸結(jié)構(gòu)是一棵深度為（log值域）的滿的二叉樹，再加上樹狀數(shù)組的復雜度，總復雜度 $O(nlogwlogn)$

代碼

#include<bits/stdc++.h> using namespace std; #define ll long long #define ull unsigned long long #define debug(...) fprintf(stderr,__VA_ARGS__) const int N=4e5+100; const int mod=1e9+7; inline ll read(){ll x(0),f(1);char c=getchar();while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}while(isdigit(c)){x=(x<<1)+(x<<3)+c-'0';c=getchar();}return x*f; } int n,m; int f[N]; inline void add(int p,int w){for(;p<=n;p+=p&-p) f[p]+=w;return; } inline int ask(int p){int res(0);for(;p;p-=p&-p) res+=f[p];return res; } struct ope{int x,y,id,k,op; }q[N],q1[N],q2[N]; int ans[N]; void solve(int l,int r,int ql,int qr){//printf("(%d %d) (%d %d)\n",l,r,ql,qr);if(ql>qr) return;if(l==r){for(int i=ql;i<=qr;i++){if(q[i].op==2) ans[q[i].id]=l;}return;}int mid=(l+r)>>1,n1(0),n2(0);for(int i=ql;i<=qr;i++){if(q[i].op==1){if(q[i].x<=mid) add(q[i].id,q[i].y),q1[++n1]=q[i];else q2[++n2]=q[i];}else{int w=ask(q[i].y)-ask(q[i].x-1);if(w>=q[i].k) q1[++n1]=q[i];else{q[i].k-=w;q2[++n2]=q[i];}}}for(int i=1;i<=n1;i++){if(q1[i].op==1) add(q1[i].id,-q1[i].y);}for(int i=1;i<=n1;i++) q[ql+i-1]=q1[i];for(int i=1;i<=n2;i++) q[ql+n1+i-1]=q2[i];solve(l,mid,ql,ql+n1-1);solve(mid+1,r,ql+n1,qr);return; } int tot,cnt; int a[N]; signed main() { #ifndef ONLINE_JUDGE//freopen("a.in","r",stdin);//freopen("a.out","w",stdout); #endifn=read();m=read();for(int i=1;i<=n;i++) q[++tot]=(ope){a[i]=(int)read(),1,i,0,1};for(int i=1;i<=m;i++){char c;scanf(" %c",&c);if(c=='Q'){q[++tot]=(ope){(int)read(),(int)read(),++cnt,(int)read(),2};}else{int pl=read(),val=read();q[++tot]=(ope){a[pl],-1,pl,0,1};q[++tot]=(ope){val,1,pl,0,1};a[pl]=val;}}solve(-1e9,1e9,1,tot);for(int i=1;i<=cnt;i++) printf("%d\n",ans[i]);return 0; } /* 21 abcaaaaabbcbacbabcbcb*/

總結(jié)

以上是生活随笔為你收集整理的模板：整体二分的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。