「整体二分」学习笔记

Ace_FutureDream · 2025-01-17 20:27:53 · 算法·理论

写给自己看的，我也不知道为什么其他算法的没写，所以先从整体二分开始写。

算法：

整体二分的思想就是对于一些整体的询问统一二分以达到降低复杂度的目的，所以必须离线，并且可以接受带修的情况，时空复杂度也比较优秀。

例题：

A.【模板】静态区间第 k 小

考虑对于每个询问怎么二分，那么显然可以二分答案，判断比 mid 小的数有多少个，然后你发现复杂度是 O(nq\log V) 的，考虑对于所有询问一起进行二分答案。

那么我们把二分的过程写成递归的函数形式，solve(ql,qr,vl,vr)。ql,qr 表示当前的询问下标区间（注意: 下标 \ne 原询问编号，二分中途会变化），vl,vr 则表示答案范围，即下标为 ql\sim qr 的询问答案范围在 vl\sim vr 之间，接着我们还需要两个辅助数组 qx,qy 来辅助一下。

那么当 vl=vr 时，ql\sim qr 的询问答案便都是 vl。

然后考虑怎么解决求查询区间 \le 一个数的个数，那么我们将 \le 这个数的下标设为 1，其他设为 0，在二分的时候动态处理即可。

设 mid 为我们二分的值域。然后我们将操作分为修改和询问两个类型：

对于修改操作

• 若修改的数 \le mid，那么将它加入树状数组，并且它会对值域更小的数产生影响，所以加入到 qx 中。

• 若修改的数 >mid，那么它会对值域更大的数产生影响，所以加入到 qy 中。

对于查询操作

• 若在查询区间内 \le mid 的个数 < k ，则说明 mid 太小了，应该变大，那么此时 k 也需要变化，因为接下来的询问是 [mid+1,r] 范围内 \le mid' 的个数，而 mid'>mid，但是我们没有将这个区间内的答案算上，所以应该将询问的 k 减去 \le mid 的个数，然后将这个询问加入 qy 中。

• 若查询区间内 \le mid 的个数 \ge k 说明 mid 太大了，应该变小，然后将这个询问加入 qx 中。

然后你可以将 qx 和 qy 复制回 q 中，再二分下去，就做完了。

核心代码：

void solve(int ql,int qr,int l,int r){
    if(l>r||ql>qr)return;
    if(l==r){
        for(int i=ql;i<=qr;i++)
            if(q[i].op==1)//是查询操作 
                ans[q[i].id]=l;//记录答案 
        return;
    }
    int mid=(l+r)>>1;//一定不要用/2，一定要用右移，养成好习惯 
    int tot1=0,tot2=0;
    for(int i=ql;i<=qr;i++){
        if(q[i].op==1){continue;}
        if(q[i].k<=mid)add(q[i].id,1),qx[++tot1]=q[i];//q[i].k就是加这个数字 
        else qy[++tot2]=q[i];
    }//先处理修改操作 
    for(int i=ql;i<=qr;i++){
        if(q[i].op==1){
            int x=query(q[i].r)-query(q[i].l-1);
            if(x>=q[i].k)qx[++tot1]=q[i];
            else qy[++tot2]={q[i].l,q[i].r,q[i].k-x,q[i].id,q[i].op};
        }
    }//后处理查询操作 
    for(int i=ql;i<=qr;i++){
        if(q[i].op==1)continue;
        if(q[i].k<=mid)
            add(q[i].id,-1);//回溯 
    }
    for(int i=1;i<=tot1;i++)q[ql+i-1]=qx[i];
    for(int i=1;i<=tot2;i++)q[ql+tot1+i-1]=qy[i];
    solve(ql,ql+tot1-1,l,mid);
    solve(ql+tot1,qr,mid+1,r);
}

B.【模板】动态区间第 k 小

动态怎么做？一开始我想参照 cdq 分治，但貌似每次二分都要按照时间排一次序，比较麻烦，那怎么办呢?

注意到你将 q 分为 qx 和 qy 时，qx 和 qy 内部相对加入时间都是不变的，也就是说你只要在一开始在 q 中加入操作就按照时间顺序加入的话，那么你每次二分时你的操作序列也都是按照时间顺序的，所以就不用排序了。

然后在分配 qx 和 qy 的过程中就按照时间顺序一个一个搞，就能让每个查询都查询到正确的答案了。

考虑怎么修该，注意到修改 = 删除 + 添加，然后弄一个权值，删除的时候是 -1，添加的时候则是 1，然后就做完了。

核心代码：

void solve(int ql,int qr,int l,int r){
    if(l>r||ql>qr)return;
    if(l==r){
        for(int i=ql;i<=qr;i++)if(q[i].op==1)
            ans[q[i].id]=l;
        return;
    }
    int mid=(l+r)>>1;
    int tot1=0,tot2=0;
    for(int i=ql;i<=qr;i++){
        if(q[i].op==1){
            int x=query(q[i].r)-query(q[i].l-1);
            if(x>=q[i].k)qx[++tot1]=q[i];
            else qy[++tot2]={q[i].l,q[i].r,q[i].k-x,q[i].id,q[i].op};
        }else{
            if(q[i].k<=mid)add(q[i].id,q[i].l),qx[++tot1]=q[i];//这里的q[i].l就是权值
            else qy[++tot2]=q[i];   
        }
    }
    for(int i=ql;i<=qr;i++){
        if(q[i].op==1)continue;
        if(q[i].k<=mid)
            add(q[i].id,-q[i].l);
    }
    for(int i=1;i<=tot1;i++)q[ql+i-1]=qx[i];
    for(int i=1;i<=tot2;i++)q[ql+tot1+i-1]=qy[i];
    solve(ql,ql+tot1-1,l,mid);
    solve(ql+tot1,qr,mid+1,r);
}

C. [ZJOI2013] K大数查询

这个只是将求 k 小值改成了求 k 大值，单点加变成了区间加，把树状数组变成线段树就行。