cdq分治·三维偏序问题

转载自FlashHu大佬的博客CDQ分治总结（CDQ，树状数组，归并排序），在讲述部分有部分删改，用了自己的代码

CDQ分治的思想

CDQ分治是基于时间的离线分治算法。这一类分治有一个重要的思想——用一个子问题来计算对另一个子问题的贡献。

有了这种思想，就可以在一定的复杂度范围内地解决偏序问题。从一位偏序（就是按下表排列）的$\Theta(N)$开始，每增加一维增加$\Theta(\log N)$倍，可以通过不断叠加cdq分治来增加维度，但当达到4维以上时效率就和暴力差不多了。

例题1

P3810 【模板】三维偏序（陌上花开）

即给出若干元素，每个元素有三个属性值$a,b,c$，询问对于每个元素$i$，满足$a_j\leq a_i,b_j\leq b_i,c_j\leq c_i$的$j$的个数

不用着急，先从简单的问题开始

试想一下二位偏序也就是$a_j\leq a_i,b_j\leq b_i$怎么做

先按$a$为第一关键字，$b$为第二关键字排序，那么我们就保证了第一维$a$的有序。

于是，对于每一个$i$，只可能$1$到$i-1$的元素会对它有贡献，那么直接查$1$到$i-1$的元素中满足$b_j\leq b_i$的元素个数。

具体实现？动态维护$b$的树状数组，从前到后扫一遍好啦，$O(n\log n)$。

那么三维偏序呢？我们只有在保证前两位都满足的情况下才能计算答案了。

仍然按$a$为第一关键字，$b$为第二关键字，$c$为第三关键字排序，第一维保证左边小于等于右边了。

为了保证第二维也是左边小于等于右边，我们还需要排序。

想到归并排序是一个分治的过程，我们可不可以在归并的过程中，统计出在子问题中产生的对答案贡献呢？

现在我们有一个序列，我们把它递归分成两个子问题，子问题进行完归并排序，已经保证$b$有序。此时，两个子问题间有一个分界线，原来第一维左边小于等于右边，所以现在分界线左边的任意一个的$a$当然还是都小于右边的任意一个。那不等于说，只有分界线左边的能对右边的产生贡献？

于是，问题降到了二维。我们就可以排序了，归并排序（左边的指针为$j$，右边的为$i$）并维护$c$的树状数组，如果当前$b_j\leq b_i$，说明$j$可以对后面加入的满足$c_j\leq c_i$的$i$产生贡献了，把$c_j$加入树状数组；否则，因为后面加入的$j$都不会对$i$产生贡献了，所以就要统计之前被给的所有贡献了，查询树状数组$c_i$的前缀和。

这是在分治中统计的子问题的答案，跟总答案有怎样的关系呢？容易发现，每个子问题统计的只有跨越分界线的贡献，反过来看，每一个能产生贡献的$i,j$，有且仅有一个子问题，两者既同时被包含，又在分界线的异侧。那么所有子问题的贡献加起来就是总答案。

算法的大致思路就是这样啦。至于复杂度，$T(n)=O(n\log k)+T(\frac 2 n)=O(n\log n\log k)$。

当然还有不少细节问题。

最大的问题就在于，可能有完全相同的元素。这样的话，本来它们相互之间都有贡献，可是cdq的过程中只有左边的能贡献右边的。这可怎么办呢？

我们把序列去重，这样现在就没有相同的了。给现在的每个元素一个权值$v$等于出现的次数。中间的具体实现过程也稍有变化，在树状数组中插入的值是$v$而不是$1$了，最后统计答案时，也要算上相同元素内部的贡献，ans+=v-1。

写法上，为了防止sort和归并排序中空间移动太频繁，没有对每个元素封struct，这样的话就要改一下cmp函数

#include<bits/stdc++.h>

using namespace std;

typedef long long LL;

const int INF=1e9+,MAXN=1e5+,MAXK=2e5+;

struct node{

    int x,y,z,ans,w;

}A[MAXN],tmp[MAXN];

inline bool cmpx(node x,node y){

    return x.x<y.x||(x.x==y.x&&(x.y<y.y||(x.y==y.y&&x.z<y.z)));

}

inline bool cmpy(node x,node y){

    return x.y<y.y||(x.y==y.y&&(x.x<y.x||(x.x==y.x&&x.z<y.z)));

}

int N,K,sum[MAXK];

inline int lowbit(int x){

    return x&-x;

}

inline void upd(int x,int c){

    while(x<=K){

        sum[x]+=c;

        x+=lowbit(x);

    }

}

inline int qry(int x){

    int ret=;

    while(x){

        ret+=sum[x];

        x-=lowbit(x);

    }

    return ret;

}

void cdq(int l,int r){

    if(l==r)

        return;

    int mid=(l+r)>>;

    cdq(l,mid);

    cdq(mid+,r);

    sort(A+l,A+mid+,cmpy);

    sort(A+mid+,A+r+,cmpy);

    int i=mid+,j=l;

    for(;i<=r;i++){

        while(A[j].y<=A[i].y&&j<=mid){

            upd(A[j].z,A[j].w);

            j++;

        }

        A[i].ans+=qry(A[i].z);

    }

    for(i=l;i<j;i++)

        upd(A[i].z,-A[i].w);

}

int n,ans[MAXK];

int main(){

    scanf("%d%d",&n,&K);

    for(int i=;i<=n;i++){

        scanf("%d%d%d",&tmp[i].x,&tmp[i].y,&tmp[i].z);

    }

    sort(tmp+,tmp+n+,cmpx);

    for(int i=,c=;i<=n;i++,c++)

        if((tmp[i].x^tmp[i+].x)|(tmp[i].y^tmp[i+].y)|(tmp[i].z^tmp[i+].z)){

            A[++N]=tmp[i];

            A[N].w=c;

            c=;

        }

    cdq(,N);

    for(int i=;i<=N;i++)

        ans[A[i].ans+A[i].w-]+=A[i].w;

    for(int i=;i<n;i++)

        printf("%d\n",ans[i]);

    return ;

}

例题二

洛谷P4169 [Violet]天使玩偶/SJY摆棋子

洛谷题目传送门

不会KDT，然而CDQ当然是有优势的。

第一眼就能发现每一个修改或查询都有三个属性，$x,y$，还有时间戳。那么怎样把它转化为一般的三维偏序问题呢？

假如所有记忆的点都在查询的点的左下角，那么就会只有$x,y$和时间戳三个维度都小于查询点的记忆点可以产生贡献，这就是三维偏序了。

贡献是什么呢？设有若干$j$对$i$产生了贡献，那么直接去绝对值，答案就是$\min\{x_i-x_j+y_i-y_j\}$，也就是$x_i+y_i-\max\{x_j+y_j\}$，这个还是可以用树状数组，只不过改成维护前缀最大值。第一维时间戳，输入已经排好序了；第二位$x$归并；第三位$y$树状数组统计答案。

然而假设并不成立。但是我们可以发现，每个能产生贡献的点只可能会在查询点的四个方向（左下，左上，右下，右上），那么对所有点还要进行$3$遍坐标翻转（新坐标等于值域减去原坐标），做$4$遍CDQ，就可以统计到每个方向的最优答案，最后再取$\min$即可。

$n,m=300000$，值域$1000000$，一看这$O((n+m)\log(n+m)\log k)$好大，还要跑$4$遍，真的不会T么？所以还是要优化一些细节。

首先，蒟蒻仍然沿用三维偏序模板的做法，没有对元素封struct以减少空间交换，这样在做完坐标翻转后也能更快还原，直接for一遍初始化。然而也会带来数组的频繁调用，蒟蒻也在怀疑这种优化的可行性，还望Dalao指教。

接着，我们发现左边有$n$个元素都确定了是记忆点。也就是说，我们不必对$n+m$个点都跑CDQ了，只对后面$m$个点跑，前面的$n$个点直接预处理按$x$第一关键字、$y$第二关键字sort，这样复杂度就降到了$O(n\log n+m\log m\log k+n\log k)$了。然而做完坐标翻转后也别忘了处理一下。如果这一次翻转的是$y$，那么$x$不会受到影响；如果翻转的是$x$，那么也直接翻转数组就好啦！

至于fread什么的用上也好。加上这一堆优化，代码就有90行了。

然后一交上去就1A了！？平时习惯了满屏殷红的WA，蒟蒻也不得不感叹，比起不少数据结构，CDQ真是思路板又好写还好调。

#include<cstdio>

#include<cstring>

#include<algorithm>

#define RG register

#define I inline void

#define R RG int

#define gc          if(++pp==pe)fread (pp=buf,1,SZ,stdin)

#define pc(C) *pp=C;if(++pp==pe)fwrite(pp=buf,1,SZ,stdout)

const int N=3e5,D=1e6+,SZ=<<,INF=;

char buf[SZ],*pe=buf+SZ,*pp=pe-;

int x[N],y[N],p[N],q[N],f[N],ans[N],e[D+];

bool t[N];

struct NODE{

    int x,y;

    inline bool operator<(RG NODE b)const{

        return x<b.x||(x==b.x&&y<b.y);

    }

}a[N];//前n个点

inline int in(){

    gc;while(*pp<'-')gc;

    R x=*pp&;gc;

    while(*pp>'-'){x*=;x+=*pp&;gc;}

    return x;

}

I out(R x){

    if(x>)out(x/);

    pc(x%|'');

}

I min(R&x,R y){if(x>y)x=y;}

I upd(R i,R v){for(;i<=D;i+=i&-i)if(e[i]<v)e[i]=v;}

I qry(R i,R&v){for(;i   ;i-=i&-i)if(v<e[i])v=e[i];}

I clr(R i)    {for(;i<=D;i+=i&-i)e[i]=;}

void cdq(R*p,R m){//三维偏序Dalao们都会吧

    if(m==)return;

    R n=m>>,i,j,k;

    cdq(p,n);cdq(p+n,m-n);

    memcpy(q,p,m<<);

    for(k=i=,j=n;i<n&&j<m;++k)

        if(x[q[i]]<=x[q[j]]){

            if(!t[q[i]])upd(y[q[i]],x[q[i]]+y[q[i]]);

            p[k]=q[i++];

        }

        else{

            if(t[q[j]])qry(y[q[j]],f[q[j]]);

            p[k]=q[j++];

        }

    for(;j<m;++j)

        if(t[q[j]])qry(y[q[j]],f[q[j]]);

    memcpy(p+k,q+i,(n-i)<<);//注意收尾和清空

    for(--i;~i;--i)clr(y[q[i]]);

}

int main(){

    R n=in(),m=in(),i,j,k;

    for(i=;i<n;++i)

        a[i].x=in()+,a[i].y=in()+;

    std::sort(a,a+n);//n个点预排序

    for(i=;i<m;++i){

        if((t[i]=in()-))ans[i]=INF;//注意给极大值

        x[i]=in()+;y[i]=in()+;//BIT不能有0下标，所以改一下

    }

    for(k=;k<=;++k){

        for(i=;i<m;++i)p[i]=i;//很快就可以初始化序列

        cdq(p,m);

        for(i=j=;i<n&&j<m;){//外面统计还是和CDQ一样，只是不用归并了

            if(a[i].x<=x[p[j]])

                upd(a[i].y,a[i].x+a[i].y),++i;

            else{

                if(t[p[j]])qry(y[p[j]],f[p[j]]);

                ++j;

            }

        }

        for(;j<m;++j)

            if(t[p[j]])qry(y[p[j]],f[p[j]]);

        memset(e,,sizeof(e));

        for(i=;i<m;++i)

            if(t[i]&&f[i])min(ans[i],x[i]+y[i]-f[i]),f[i]=;

        if(k==)break;

        if(k&){//第一次、第三次上下翻

            for(i=;i<n;++i)a[i].y=D-a[i].y;

            for(i=;i<m;++i)y[i]=D-y[i];

        }

        else{//第二次左右翻

            for(i=;i<n;++i)a[i].x=D-a[i].x;

            for(i=;i<m;++i)x[i]=D-x[i];

            for(i=,j=n-;i<j;++i,--j)std::swap(a[i],a[j]);//注意仍要保证x不降

        }

    }

    for(pp=buf,i=;i<m;++i)

        if(t[i]){out(ans[i]);pc('\n');}

    fwrite(buf,,pp-buf,stdout);

    return ;

}

巴特西

cdq分治·三维偏序问题

CDQ分治的思想

例题1

例题二

最新文章

热门文章