整体二分
整体二分其实很类似CDQ…区别在于一个是对区间二分，一个是对值进行二分，并以值划分区间
还是结合一道具体的例题吧，请直接看模板B：Dynamic Rankings
模板A（不带修改）：P3834 可持久化线段树 1（主席树）
略过
//整体二分 #include<iostream> #include<cstdio> #include<cmath> #include<cstring> #include<algorithm> #include<ctime> #include<cstdlib> #include<queue> using namespace std; const int INF=999999999; int lowbit(int x){return x&(-x);} struct BIT{ int size,tree[500005]; void init(int mysize){ size=mysize;for(int i=0;i<500005;i++) tree[i]=0; } void change(int id,int val){ for(int i=id;i<=size;i+=lowbit(i)) tree[i]+=val; } int getsum(int id){ if(id==0) return 0; int ans=0; for(int i=id;i>=1;i-=lowbit(i)) ans+=tree[i]; return ans; } int ask(int l,int r){return getsum(r)-getsum(l-1);} }bit; struct Query{ int id,type,l,r,val;//type=1：修改；type=2：查询 }q[500005]; int n,qn; int ans[500005],an; Query tmp1[500005],tmp2[500005]; void Divide(int ql,int qr,int l,int r){ if(ql>qr) return; if(l==r){ for(int i=ql;i<=qr;i++) ans[q[i].id]=l; return; } int mid=(l+r)/2; int t1=0,t2=0; for(int i=ql;i<=qr;i++){ if(q[i].type==1){ if(q[i].val<=mid){ bit.change(q[i].l,1); tmp1[++t1]=q[i]; }else tmp2[++t2]=q[i]; }else if(q[i].type==2){ int d=bit.ask(q[i].l,q[i].r); if(d>=q[i].val) tmp1[++t1]=q[i]; else q[i].val-=d,tmp2[++t2]=q[i]; } } for(int i=1;i<=t1;i++) if(tmp1[i].type==1) bit.change(tmp1[i].l,-1); for(int i=1;i<=t1;i++) q[ql+i-1]=tmp1[i]; for(int i=1;i<=t2;i++) q[ql+t1+i-1]=tmp2[i]; Divide(ql,ql+t1-1,l,mid); Divide(ql+t1,qr,mid+1,r); } int main(){ cin>>n>>an;qn=0; for(int i=1;i<=n;i++){ int x;scanf("%d",&x); q[++qn]=(Query){0,1,i,0,x}; } for(int i=1;i<=an;i++){ int l,r,val; scanf("%d%d%d",&l,&r,&val); q[++qn]=(Query){i,2,l,r,val}; } for(int i=0;i<500005;i++) ans[i]=0; bit.init(500000); Divide(1,qn,0,INF); for(int i=1;i<=an;i++) printf("%d\n",ans[i]); return 0; }
View Code
模板B（带修改）：洛谷P2617 Dynamic Rankings
一句话题意：求带修改区间的区间第k小
动态的解法是主席树套树状数组，然而这玩意不好打呀…
于是从离线的角度思考，用整体二分解决。
首先把修改转化，它可以通过删除和加入实现（这里的删除指“无视”该数），而删除和加入本质上是一样的，只是1和-1的区别。（后面你就明白了）
那么只需考虑如何随时加入或查询。
把所有加入和询问按时间序排成一个操作序列q，假设有一个递归的函数Divide(ql,qr,l,r)，表示咱们可以肯定q中ql~qr这段操作中的加入操作所加入的数、询问操作获取的答案一定在l~r之间，而这个函数的主要目的就是把ql~qr之间的操作按(l+r)/2来划分。
由于q是按照时间序排列，所以对于一个加入操作和一个查询操作，仅当在q中加入操作在询问操作之前，且该加入操作所修改的位置在询问操作所询问的区间[q[i].l,q[i].r]之内时，该加入才可能对该询问有贡献。
那么考虑如何让加入操作影响到后面的询问操作。q已按时间排好序，顺着遍历即可；询问的区间可以用树状数组维护，维护某个区间中值在l~mid之间的数的个数。对于加入操作，如果发现加入的数小于等于mid，就直接往加入位置对应的树状数组里塞个1就行，表示这个位置上已经有一个数了且这个数小于mid，然后把这个查询扔到左边准备递归；大于mid，不加入树状数组，直接扔到右边。
后面的询问操作计算时就查询一下树状数组中q[i].l~q[i].r之和，也就是求得了在q[i].l~q[i].r之间值在l~mid之间的数的个数。如果个数比查询操作的k多，那就说明答案值在l~mid之间，把这个查询放到左边准备递归；如果比k少，就说明要答案值在mid+1~r之间，就先给查询的k减掉l~mid里的个数，然后把查询丢到右边准备递归。
最后，清零树状数组，把之前扔到左边和右边的操作整理到q中，递归左边和右边，完事。等递归到l==r时，答案已经没有周旋的余地，只能是l(r)了，那就存下ql~qr中询问操作对应的答案，最后统一输出就完了。
自己在理解上面这一大段的时候花了大力气…希望自己写清楚了把，实现就请看代码注释咯
//整体二分 #include<iostream> #include<cstdio> #include<cmath> #include<cstring> #include<algorithm> #include<ctime> #include<cstdlib> #include<queue> using namespace std; const int INF=999999999; int lowbit(int x){return x&(-x);} struct BIT{//树状数组 int size,tree[1000005]; void init(int mysize){ size=mysize;for(int i=0;i<1000005;i++) tree[i]=0; } void change(int id,int val){ for(int i=id;i<=size;i+=lowbit(i)) tree[i]+=val; } int getsum(int id){ if(id==0) return 0; int ans=0; for(int i=id;i>=1;i-=lowbit(i)) ans+=tree[i]; return ans; } int ask(int l,int r){return getsum(r)-getsum(l-1);} }bit; struct Query{//操作序列 int id,type,l,r,val,dt; //id：对于查询，记录它是第几个询问 //type=1：修改；type=2：查询 //l，r：对于修改，l记录修改的位置，r无用；对于查询，共同表示查询的区间 //val：对于修改，表示加入或删除的数；对于查询，表示“第k小”的k //dt：对于修改，表示是加入还是删除 }q[1000005]; int n,qn; int ans[1000005],an; Query tmp1[1000005],tmp2[1000005]; void Divide(int ql,int qr,int l,int r){//划分 if(ql>qr) return; if(l==r){ //答案已确定 for(int i=ql;i<=qr;i++) if(q[i].type==2) ans[q[i].id]=l;//存储答案 return; } int mid=(l+r)/2; int t1=0,t2=0; for(int i=ql;i<=qr;i++){ if(q[i].type==1){//修改 if(q[i].val<=mid){//查询值小于等于mid bit.change(q[i].l,q[i].dt);//加入树状数组 tmp1[++t1]=q[i];//丢到左边 }else tmp2[++t2]=q[i];//大于，丢到右边 }else if(q[i].type==2){//查询 int d=bit.ask(q[i].l,q[i].r);//查询q[i].l~q[i].r中值在l~mid之间的数的个数 if(d>=q[i].val) tmp1[++t1]=q[i];//如果比k多，丢到左边 else q[i].val-=d,tmp2[++t2]=q[i];//否则减少k，丢到右边 } } for(int i=1;i<=t1;i++)//清零树状数组 if(tmp1[i].type==1) bit.change(tmp1[i].l,-tmp1[i].dt); for(int i=1;i<=t1;i++) q[ql+i-1]=tmp1[i];//左边放入操作队列 for(int i=1;i<=t2;i++) q[ql+t1+i-1]=tmp2[i];//右边放入操作队列 Divide(ql,ql+t1-1,l,mid);//递归左边 Divide(ql+t1,qr,mid+1,r);//递归左边 } int arr[1000005];//记录当前数组情况，更改删数要用 int main(){ int cirno; cin>>n>>cirno;qn=0,an=0; for(int i=1;i<=n;i++){ int x;scanf("%d",&x); q[++qn]=(Query){0,1,i,0,x,1}; arr[i]=x; } for(int i=1;i<=cirno;i++){ char type[5]; scanf("%s",type); int l,r,val; if(type[0]=='C'){//修改 scanf("%d%d",&l,&val); q[++qn]=(Query){0,1,l,0,arr[l],-1};//先删掉原数 arr[l]=val; q[++qn]=(Query){0,1,l,0,val,1};//加入新数 }else if(type[0]=='Q'){//询问 scanf("%d%d%d",&l,&r,&val); q[++qn]=(Query){++an,2,l,r,val,0}; } } for(int i=0;i<1000005;i++) ans[i]=0; bit.init(1000000); Divide(1,qn,0,INF);//开始递归 for(int i=1;i<=an;i++) printf("%d\n",ans[i]); return 0; }
View Code