我永远爱离线分治算法

CDQ分治

用于解决多维偏序问题。

三维偏序

题目

有$n$个元素,每个元素有$a_i,b_i,c_i$三个属性。

设$f(i)$表示满足$a_j\leq a_i$且$b_j\leq b_i$且$c_j\leq c_i$的$j$的数量。

对于$i\in [1,n]$,求$f(i)$。

第一维

$sort$直接排序即可。

第二维

运用归并排序的思想,二分处理当前区间的左右子区间$[l,mid]$,$[mid+1,r]$。

因为我们已经按第一维排了序,所以当前区间左子区间的第一维都一定小于等于右子区间。

按照第二维对区间进行归并排序。

第三维

不妨设归并过程中左区间指针为$p$,右区间指针为$q$。

因为左右区间的第二维在分治过程中已经分别排序,

所以当$p.b<=q.b$时,将$p.c$放入树状数组。

否则在树状数组中查询$<=q.c$的数量加在$q$的贡献中。

注意最后要还原树状数组,并更新按第二维排序后的序列。

模板
void CDQ(int l,int r){
    if(l==r) return;
    int mid=(l+r)>>1;
    CDQ(l,mid);CDQ(mid+1,r);
    int p=l,q=mid+1,tot=l;
    while(p<=mid&&q<=r){
        if(f[p].b<=f[q].b) update(f[p].c,f[c].opt),t[tot++]=f[p++]; 
        else f[q].num+=ask(f[q].c),t[tot++]=f[q++];
    }
    while(p<=mid) update(f[p].c,f[c].opt),t[tot++]=f[p++];
    while(q<=r) f[q].num+=ask(f[q].c),t[tot++]=f[q++];
    for(int i=l;i<=mid;i++) update(f[i].c,-f[i].opt);
    for(int i=l;i<=r;i++) f[i]=t[i];
} 

一些应用

求给定矩形内点的数量。

考虑一个左下为$(0,0)$,右上为$(x,y)$的矩形。

它所覆盖的点$(x’,y’)$一定满足$x’\leq x\ \ \ \ y'\leq y$。

你看这玩意它像不像二维偏序!

我们令$ans(x,y)$表示左下为$(0,0)$,右上为$(x,y)$的矩形内点的数量。

运用二维树状数组的思想:

一个左下为$(lx,ly)$,右上为$(rx,ry)$的矩形内点的数量等于:

$$ ans(rx,ry)-ans(lx-1,ry)-ans(rx,ly-1)+ans(lx-1,ly-1) $$

对于每个存在的点,我们将其直接放入序列中,$opt$(贡献) 为$1$。

对于每个询问,我们将其拆为四个点放入序列中,$opt$(贡献)为$0$。

如果遇到点的坐标有负的,全部偏移一下就好了。

整体二分

用于解决各种花哨的带有多组询问的离线二分问题。

实现

将所有的修改和查询操作离线存下来。

二分答案,将修改查询等操作分成两部分。

这两部分中一部分的答案$\leq mid$,另一部分$> mid$。

而$C\leq mid$的修改放在第一个部分,$C>mid$的修改放在另一部分。

因为$C>mid$的修改对答案$\leq mid$的部分毫无影响。

(如果二分的是值域,$C$即为修改值的大小,如果二分的编号,$C$即为修改操作的编号)。

一个例子

查询区间第$K$小数:

如果是单次询问,我们可以直接二分答案$mid$,

如果$\leq mid$的数的数量$\ge k$,二分$[l,mid]$,反之二分$[mid+1,r]$。

如果是多次询问,我们可以把询问带入一起二分,

对于$\leq mid$的数,如果在询问区间出现次数$\ge k$,我们将该询问带到$[mid+1,r]$中继续二分。

反之同理。

单点修改,区间查询/区间修改,单点查询可以用树状数组维护。

$ps$:自带大常数的人用线段树是真的遭不住$QAQ$。

模板
void solve(int l,int r,int L,int R){
    if(L>R) return; 
    if(l==r){
        for(int i=L;i<=R;i++){
            if(f[i].opt) ans[f[i].pos]=l;
        }
        return;
    }
    int mid=(l+r)>>1,tot1=0,tot2=0;
    for(int i=L;i<=R;i++){
        if(f[i].opt){//查询操作 
            int sum=ask(f[i].y)-ask(f[i].x-1);
            if(sum>=f[i].k) t1[++tot1]=f[i];
            else f[i].k-=sum,t2[++tot2]=f[i];
        }
        else{//修改操作 
            if(f[i].x<=mid) update(f[i].x,1),t1[++tot1]=f[i];
            else t2[++tot2]=f[i];
        } 
    }
    for(int i=1;i<=tot1;i++){
        if(!t1[i].opt) update(t1[i].x,-1);
        //这里的t1很容易写成f QAQ
    } 
    for(int i=1;i<=cnt1;i++) f[L+i-1]=t1[i];
    for(int i=1;i<=cnt2;i++) f[L+cmt1+i-1]=t2[i];
    solve(l,mid,L,L+cnt1-1);
    solve(mid+1,r,L+cnt1,R);
}