整体二分：

对于一般二分，我们会logn外层二分一个答案，然后内层O(n)或者O(nlogn)检验。

然鹅一些有二分性质的题，询问比较多，每次逐一二分会T飞。

但是二分的范围相对固定，二分的对象也固定，而且还可以离线的话，就可以用整体二分实现。

基本思路是，二分一个mid，考虑<=mid哪些询问能够满足，根据满足与否，把询问左右下放，然后分治处理。

 

这是一般的二分的升级版。可以把所有的修改询问放在一起，用一个整体的二分来实现。一次性处理所有的修改，询问。

支持区间询问，区间修改，但是必须离线操作。

细节，边界情况考虑要到位，代码不长，但是初学的时候不是很好写。

关键是把二分理解好。

 

首先考虑不修改：

二分答案是二分答案的范围然后不断缩小，整体二分也一样。

div(A,l,r)表示，A集合所代表的询问的答案在l~r里。

每次找到一个mid，计算每个询问在mid+1~r或者l~mid中是否可以。

然后把这个询问放进下一层可以的位置的集合里面递归下去。

当l==r时，A集合中的询问的答案就都是l了。

复杂度和分治类似。logC层，每层一般O(n)或者O(nlogn)

 

例题：

区间第k小。（主席树经典例题）

我们用整体二分做。

把所有的数从小到大排一个序，放进另一个数组b里。

在每个div(A,l,r)中，

找到mid=l+r>>1，从排好序的数组b中，二分找到数值为l的位置，数值为mid的位置，

把大小为l~mid的数加入一个位置为下标树状数组里，（有就加1）然后循环当前层的A询问集合，对于qi询问

用树状数组找[li,ri]的大小sum，也就是[li,ri]中，数值在[l,mid]的数有多少个。

如果大于等于ki，说明qi的答案一定在[l,mid]中，放进左儿子集合。

否则，qi的答案一定在[mid+1,r]，令ki-=sum，放进右儿子集合。

递归之前，把树状数组上改变的位置再-1

分别递归左右儿子。

l==r的时候统计答案。

但是，复杂度O(nlogn^2)比主席树慢，而且还必须离线（辣鸡）。

 

51nod 1175：（不过这个题是区间第k大）

（把mid+1~r放进去即可）

#include
     
      using namespace std;const int N=50000+10;const int inf=1e9+2;int f[N];struct node{    int l,r;    int ans;    int kth;}q[N];int n,m;void add(int x,int c){
   for(;x<=n;x+=x&(-x))f[x]+=c;}int query(int x){
   int ret=0;for(;x;x-=x&(-x))ret+=f[x];return ret;}int delpool,cur;int dp[100];vector
      
       s[100];int a[N];int    nc(){    int r=delpool?dp[delpool--]:++cur;    s[r].clear();return r;}void dele(int x){    dp[++delpool]=x;}struct po{    int val,id;    bool friend operator <(po a,po b){        if(a.val==b.val) return a.id
       
        >1;        if(p[M].val>=mid+1) lst=M,R=M-1;        else L=M+1;    }    L=1,R=n;    while(L<=R){        int M=(L+R)>>1;        if(p[M].val<=r) rnd=M,L=M+1;        else R=M-1;    }        if(lst!=-1&&rnd!=-1){        for(int i=lst;i<=rnd;i++){            add(p[i].id,1);        }    }        int le=nc(),ri=nc();    bool fle=false,fri=false;    for(int i=0;i
        
         =q[o].kth){            fri=true;            s[ri].push_back(o);        }        else{            fle=true;            q[o].kth-=sum;            s[le].push_back(o);        }    }    if(lst!=-1&&rnd!=-1){        for(int i=lst;i<=rnd;i++){            add(p[i].id,-1);        }    }        if(fle)slo(le,l,mid);    dele(le);    if(fri)slo(ri,mid+1,r);    dele(ri);}int mi=inf,mx=0;int main(){    scanf("%d",&n);    for(int i=1;i<=n;i++){        scanf("%d",&a[i]);        mi=min(mi,a[i]);        mx=max(mx,a[i]);        p[i].val=a[i];        p[i].id=i;    }    sort(p+1,p+n+1);    scanf("%d",&m);        int st=nc();    for(int i=1;i<=m;i++){        scanf("%d%d%d",&q[i].l,&q[i].r,&q[i].kth);        q[i].l++;q[i].r++;        s[st].push_back(i);    }    slo(st,mi,mx);        for(int i=1;i<=m;i++){        printf("%d\n",q[i].ans);    }    return 0;}
        
       
      
     

 注意：

1.第k大，把mid+1~r放进去。

2.直接l~mid，mid+1~r递归，是一定能找到答案的。

3.注意vector垃圾回收（下面讲解）

4.当sum<kth的时候，q[o].kth-=sum别忘了

 

至于A集合怎么存储？

1.vector存储。但是每层另开两个vector一定MLE。发现，递归类似于dfs，一定先深度优先遍历，再回溯。

回溯之后，之前走过的地方的vector已经没有用了，但是还存在，占着空间。

其实，当基础的答案区间是-1e18~1e18的时候，最多深度是二分65次，每次最多产生两个儿子，但是一直沿一个儿子走下去，

所以，最坏情况下，最大的有用vector数量不过130个。

开一个全局的vector<int>p[130]其实足够了。

 

所以必须考虑一下垃圾回收。

vector
     
      p[130];int delepool[130];int dp;int tc;void dele(int s){    delepool[++dp]=s;}int nc(){    int r=dp?delepool[dp--]:++tc;    p[r].clear();    return r;}
     

这样，div(A,l,r)，A就是当前存储的vector的编号了。

这样，每次找一下left儿子编号le=nc(),右儿子ri=nc()

然后，递归完回溯，dele(le),dele(ri)即可。

亲测可以实现，完全正确。

（upda：2018.12.18 :但是常数和空间会比较大，而且易错，不推荐，这是博主以前自己yy的做法）

 

（注意：l==r判断回溯的时候就不要dele(id)了，因为，回溯之后，id作为左二子或者右儿子会再一次被dele。就错了。）

 

2.引入两个临时的tmp[]结构体变量，tmp1,tmp2分别表示左儿子，右儿子询问集合。

判断然后加入进去，注意，是把整个qi结构体复制进去。加入完了之后，设cnt1表示tmp1大小，cnt2表示tmp2大小，

把tmp1中的qi依次加入A中，tmp2中的qi再在后面依次加入A中。

总之，div(ql,qr,l,r)集合变成了一段连续的区间，

分配完了之后，左二子变成了一段区间ql~ql+cnt1-1 右儿子就是ql+cnt1~qr

这样，用区间的两个端点就可以代表整个询问集合了。

//By YJC i207Mvoid sol(int ql, int qr, int l, int r) {    //..........    int p = ql;    for (ri i = 1; i <= cnt1; ++i) {        q[p] = tmp1[i];        ++p;    }    for (ri i = 1; i <= cnt2; ++i) {        q[p] = tmp2[i];        ++p;    }    sol(ql, ql + cnt1 - 1, l, mid); sol(ql + cnt1, qr, mid + 1, r);}

注意，我们询问本身必须用结构体q[]存储，因为它们的位置可能随时变化，必须一起动。

 

二分mid，二维树状数组处理0/1矩形和。然后递归即可。

同样k-=now,

 

 

有修改操作怎么办？

可以发现，对于一个询问，并不是所有的修改操作都对询问答案产生影响。

所以，开始，我们把A集合中，按原来顺序加入所有的修改操作和询问操作，

假设以mid+1~r为标准计算询问的归类：

二分mid，循环A集合。

1.如果是修改操作，对于修改的值小于等于mid的修改，放进左集合，表示会对答案在mid左边的询问产生影响。

对于修改的值大于mid的修改，在一个数据结构上修改，然后放进右集合，表示会对答案在mid右边的询问产生影响。

2.如果是查询操作，直接通过数据结构查询，在它前面的修改操作能影响的已经都加入数据结构里了，所以可以确定qi询问所属儿子集合。

（有点类似cdq分治）

 

不懂的话，看例题：

[ZJOI2013]K大数查询

题目描述

有N个位置，M个操作。操作有两种，每次操作如果是1 a b c的形式表示在第a个位置到第b个位置，每个位置加入一个数c如果是2 a b c形式，表示询问从第a个位置到第b个位置，第C大的数是多少。

N,M<=50000

a<=b<=N

1操作中abs(c)<=N

2操作中c<=long long

（保证输入合法）

Solution：

没错，这个可以用树套树解决。

但是，整体二分更好写。

相当于每个位置有一个桶，往里面不断加入数据。

按照上面所说的，把所有的询问、修改按顺序加入A里。

二分mid，

修改操作，对于加入的c<=mid，放进左集合不管。

否则，用一个线段树，以位置为下标，区间修改加1，加入c们。放进右集合。

对于一个询问，

线段树找[l,r]的sum，如果sum>=k,说明qi的答案一定在[mid+1,r]里面，放进右集合。

否则，k-=sum，放进左集合。

 

代码：（不知道为什么要的define int long long，害得调到凌晨）

Code：（我用的vector存储，因为值域在-n到n之间，所以开35即可。）

#include
     
      #define int long longusing namespace std;typedef long long ll;const int N=50000+10;int n,m;struct node{    int l,r;ll c;int id;int op;ll ans;}q[N];struct tr{    int sum,ad;}t[N*4];int dp;int tc;vector
      
       p[35];int delepool[35];void dele(int s){    delepool[++dp]=s;}int nc(){    int r=dp?delepool[dp--]:++tc;    p[r].clear();    return r;}int ans[N];int tot;void pushdown(int x,int l,int r){    int mid=l+r>>1;    t[x<<1].sum+=t[x].ad*(mid-l+1);    t[x<<1|1].sum+=t[x].ad*(r-mid);    t[x<<1].ad+=t[x].ad;    t[x<<1|1].ad+=t[x].ad;    t[x].ad=0;}void add(int x,int l,int r,int L,int R,int c){    if(L<=l&&r<=R){        t[x].sum+=c*(r-l+1);        t[x].ad+=c;        return;    }    pushdown(x,l,r);    int mid=l+r>>1;    if(L<=mid) add(x<<1,l,mid,L,R,c);    if(mid
       
        >1;    int ret=0;    if(L<=mid) ret+=query(x<<1,l,mid,L,R);    if(mid
        
         =q[p[id][i]].c){                fr=true;                p[ri].push_back(p[id][i]);            }            else            {                fl=true;                q[p[id][i]].c-=sum;                p[le].push_back(p[id][i]);            }        }    }    for(int i=0;i
         
          mid) {                add(1,1,n,q[p[id][i]].l,q[p[id][i]].r,-1);            }        }    }    if(p[le].size()&&fl)div(le,l,mid);    dele(le);    if(p[ri].size()&&fr)div(ri,mid+1,r);    dele(ri);}signed main(){    scanf("%d%d",&n,&m);    int st=nc();    for(int i=1;i<=m;i++){        scanf("%d%d%d%lld",&q[i].op,&q[i].l,&q[i].r,&q[i].c);        q[i].id=i;        p[st].push_back(i);    }    div(st,-n,n);    for(int i=1;i<=m;i++){        if(q[i].op==2){            printf("%lld\n",q[i].ans);        }    }    return 0;}