整体二分
整体二分，就是对答案（权值）做CDQ分治。
有些问题会给出一些修改和一些询问，当可以通过二分后线性判定回答询问时，我们就可以将所有修改和询问放在一起二分，复杂度一般会将一个O(n)级别优化掉，这就是整体二分。
一般配合树状数组、线段树等数据结构，来替代树套树、KD-Tree等代码量和常数都较大的方法。
[BZOJ1901][Zju2112] Dynamic Rankings
动态区间第k小是整体二分最经典的应用。
1 #include<cstdio> 2 #include<algorithm> 3 #define rep(i,l,r) for (int i=(l); i<=(r); i++) 4 using namespace std; 5 6 const int N=30010; 7 char ch; 8 int n,m,x,y,z,tot,cnt,a[N],tmp[N],ans[N],c[N]; 9 struct P{ int x,y,z,op,id; }q[N],q1[N],q2[N]; 10 11 void add(int x,int k){ for (; x<=n; x+=x&-x) c[x]+=k; } 12 int que(int x){ int res=0; for (; x; x-=x&-x) res+=c[x]; return res; } 13 14 void solve(int st,int ed,int l,int r){ 15 if (st>ed) return; 16 if (l==r){ rep(i,st,ed) ans[q[i].id]=l; return; } 17 int mid=(l+r)>>1,tot1=0,tot2=0; 18 rep(i,st,ed){ 19 if (q[i].op==1){ 20 if (q[i].y<=mid) add(q[i].x,1),q1[++tot1]=q[i]; else q2[++tot2]=q[i]; 21 } 22 if (q[i].op==2){ 23 if (q[i].y<=mid) add(q[i].x,-1),q1[++tot1]=q[i]; else q2[++tot2]=q[i]; 24 } 25 if (q[i].op==3){ 26 int t=que(q[i].y)-que(q[i].x-1); 27 if (q[i].z<=t) q1[++tot1]=q[i]; else q[i].z-=t,q2[++tot2]=q[i]; 28 } 29 } 30 rep(i,1,tot1){ 31 if (q1[i].op==1) add(q1[i].x,-1); 32 if (q1[i].op==2) add(q1[i].x,1); 33 } 34 rep(i,1,tot1) q[st+i-1]=q1[i]; 35 rep(i,1,tot2) q[st+tot1+i-1]=q2[i]; 36 solve(st,st+tot1-1,l,mid); 37 solve(st+tot1,ed,mid+1,r); 38 } 39 40 int main(){ 41 freopen("bzoj1901.in","r",stdin); 42 freopen("bzoj1901.out","w",stdout); 43 scanf("%d%d",&n,&m); 44 rep(i,1,n) scanf("%d",&a[i]),q[++tot]=(P){i,a[i],0,1,0}; 45 rep(i,1,m){ 46 scanf(" %c",&ch); 47 if (ch=='Q') scanf("%d%d%d",&x,&y,&z),q[++tot]=(P){x,y,z,3,++cnt}; 48 else scanf("%d%d",&x,&y),q[++tot]=(P){x,a[x],0,2,0},a[x]=y,q[++tot]=(P){x,y,0,1,0}; 49 } 50 solve(1,tot,0,1e9); 51 rep(i,1,cnt) printf("%d ",ans[i]); 52 return 0; 53 }
显然我们可以对每个询问二分，然后O(n)判定。考虑整体二分，用now标记当前处于的是哪个位置的状态，每次暴力调整，均摊是O(nlogn)的。
1 #include<cstdio> 2 #include<vector> 3 #include<algorithm> 4 #define rep(i,l,r) for (int i=(l); i<=(r); i++) 5 typedef long long ll; 6 using namespace std; 7 8 const int N=300010,inf=1e9; 9 ll c[N]; 10 int n,m,l,r,k,Q,tot,now,co[N],d[N],a[N],a1[N],a2[N],ans[N]; 11 struct P{ int l,r,k; }q[N]; 12 vector<int>ve[N]; 13 14 void add(int x,int k){ for (; x<=m; x+=x&-x) c[x]+=k; } 15 ll que(int x){ ll res=0; for (; x; x-=x&-x) res+=c[x]; return res; } 16 17 void work(int x,int k){ 18 add(q[x].l,k*q[x].k),add(q[x].r+1,-k*q[x].k); 19 if (q[x].l>q[x].r) add(1,k*q[x].k); 20 } 21 22 void solve(int st,int ed,int l,int r){ 23 if (st>ed) return; 24 if (l==r){ rep(i,st,ed) ans[a[i]]=l; return; } 25 int mid=(l+r)>>1; 26 while (now<mid) work(++now,1); 27 while (now>mid) work(now--,-1); 28 int tot1=0,tot2=0; 29 rep(i,st,ed){ 30 int en=ve[a[i]].size()-1; ll res=0; 31 rep(j,0,en){ 32 res+=que(ve[a[i]][j]); 33 if (res>=d[a[i]]) break; 34 } 35 if (res>=d[a[i]]) a1[++tot1]=a[i]; else a2[++tot2]=a[i]; 36 } 37 rep(i,1,tot1) a[st+i-1]=a1[i]; 38 rep(i,1,tot2) a[st+tot1+i-1]=a2[i]; 39 solve(st,st+tot1-1,l,mid); 40 solve(st+tot1,ed,mid+1,r); 41 } 42 43 int main(){ 44 freopen("bzoj2527.in","r",stdin); 45 freopen("bzoj2527.out","w",stdout); 46 scanf("%d%d",&n,&m); 47 rep(i,1,m) scanf("%d",&co[i]),ve[co[i]].push_back(i); 48 rep(i,1,n) scanf("%d",&d[i]),a[i]=i; 49 scanf("%d",&Q); 50 rep(i,1,Q) scanf("%d%d%d",&l,&r,&k),q[i]=(P){l,r,k}; 51 q[Q+1]=(P){1,m,inf}; 52 solve(1,n,1,Q+1); 53 rep(i,1,n) if (ans[i]==Q+1) puts("NIE"); else printf("%d ",ans[i]); 54 return 0; 55 }