三维偏序

-1 前言

本人写这个东西的时候十分幽默。

太难绷了于是记录下。

0 前置芝士

• 归并排序

• 树状数组

• 分治

1 相关芝士

1.1 什么是三维偏序

首先我们要了解一下一维偏序和二维偏序

一维偏序：给你一个长为 $n$ 的序列 $a$，需要求出对于每个 $a_i$ 有多少个元素比它小。

这非常简单，排序即可。

二维偏序：一个平面直角坐标系上有 $n$ 个点，第 $i$ 个点的坐标是 $(x_i,y_i)$ ，需要你对于每个点 $i$ 求出有多少个点 $j$ 满足 $x_j\leq x_i$ 且 $y_j\leq y_i$。

这个问题似乎比刚刚的要复杂一些。但是我们发现可以先固定下来一维，再对另一维度进行考虑。

于是我们可以先按照 $x$ 这一维进行排序，然后对值域建一个树状数组，每次插入 $y_i$，然后查询满足 $y_j\leq y_i$ 的个数。

另外的，求一个序列中的逆序对数量也属于二维偏序。因此解决二维偏序还可以使用类似归并排序求逆序对的方法。

接下来就是三维偏序：

在一个空间直角坐标系中有 $n$ 个点，第 $i$ 个点的坐标是 $(x_i,y_i,z_i)$ ，需要你对于每个点 $i$ 求出有多少个点 $j$ 满足 $x_i\leq x_j$ 并且 $y_i\leq y_j$ 并且 $z_i\leq z_j$。

这个问题看起来要比前两个问题都复杂得多，那么怎么解决这个问题呢？

1.2 什么是CDQ分治

解决这个问题实际上有很多种方法，比如树套树，KD-Tree。但是这些方法都比较复杂我不会，所以这里介绍一种相对更加简单的方法——CDQ分治。

回到逆序对这个问题之中，我们发现归并排序的做法事实上把整个序列的贡献分为了三部分：

• 在左边区间 $[l,mid]$ 中的对于左边区间的贡献，这部分可以继续递归分治处理。

• 在右边区间 $[mid+1,r]$ 中的对于右边区间的贡献，这部分也可以继续递归处理。

• 在左边区间 $[l,mid]$ 中的对于右边区间 $[mid+1,r]$ 中的贡献，这部分就是我们要解决的重点。

再结合树状数组的做法，我们发现可以先在最外部排序固定下来第一维 $x$，在内部归并时再按照 $y$ 排序，最后用树状数组统计 $z$，这样就可以很好的解决这个问题。这也就是CDQ分治的主要步骤。

2 具体原理和实现

注：以下均以P3810 【模板】三维偏序（陌上花开） - 洛谷为例讲述。

我们对于一个序列来看，首先，我们先按照这些点的 $x$ 升序排序，使得对于任意 $i<j$ 都有 $x_i\leq x_j$ 。

其次，由于存在取等号的情况，我们需要进行去重并且记录重复点的出现次数。令 $cnt_i$ 表示去重过会第 $i$ 个点的出现的次数。

然后开始正式的分治过程。

类似于归并排序的，我们要在分治的过程中对 $y$ 这一维排序并统计贡献。

对于两个区间 $[l,mid]$ 和 $[mid+1,r]$ ，由于经过了对于 $x$ 的排序，因此在两个区间内部无论怎样打乱都始终有 $i\in [l,mid],j\in [mid+1,r],x_i\leq x_j$ 。

然后我们按照 $y$ 来合并左右两个区间。对于 $i\in [l,mid],j\in [mid+1,r]$，有可能存在两种情况：

• $y_i\leq y_j$，也就是说前两维都满足了偏序关系，那么我们就可以把这个点加入树状数组，等待计算贡献，并且按照归并的步骤把点 $i$ 加入临时数组。

• $y_i>y_j$ ，由于左右两个区间在合并上来时已经按照 $y$ 递增排序，所以在 $[i,mid]$ 这个区间内的所有点都不可能对 $j$ 有贡献。所以我们计算前面的点对于 $j$ 的贡献，并把按照归并的步骤把点 $j$ 加入临时数组。

在全部的计算完成后，我们需要清空树状数组，然后按照归并的步骤把临时数组赋回原数组。

这样完成后我们就计算出了题目中的 $f_i$ ，然而题目最后需要我们输出对于每个 $d$ 满足 $f_i=d$ 的数量。因此我们还需要一个桶。完成后即可输出。

具体的代码实现中还有一些细节，下面是部分核心代码和注释：

int tre[N];
struct node{//一定注意此处最好把cnt,tns和三维封装在一个结构体中，否则处理十分麻烦
    int a,b,c,cnt,tns;//a,b,c分别表示三维，cnt表示点i出现次数，tns表示不包括自身数量的f_i
    bool operator == (const node &x) const{
        return (a==x.a)&&(b==x.b)&&(c==x.c);
    } 
}pt[N],tmp[N];
int m,n,d,ans[N];
void ist(int pos,int x){for(int i=pos;i<=d;tre[i]+=x,i+=lowbit(i));}//注意顺序
int query(int r){
    int ret=0;
    for(int i=r;i>=1;ret+=tre[i],i-=lowbit(i));
    return ret;
}
bool cmp(node x,node y){//注意此处的逻辑关系
    if(x.a!=y.a)return x.a<y.a;
    elif(x.b!=y.b)return x.b<y.b;
    else return x.c<y.c;
}

void solve(int l,int r){
    int mid=(l+r)>>1;
    if(l==r)return;
    solve(l,mid);solve(mid+1,r);//向下分治
    int p1=l,p2=mid+1,k=0;
    while(p1<=mid&&p2<=r){
        if(pt[p1].b<=pt[p2].b){
            ist(pt[p1].c,pt[p1].cnt);
            tmp[k++]=pt[p1++];
        }else{
            pt[p2].tns+=query(pt[p2].c);
            tmp[k++]=pt[p2++];
        }
    }
    while(p1<=mid){
        ist(pt[p1].c,pt[p1].cnt);
        tmp[k++]=pt[p1++];
    }
    while(p2<=r){
        pt[p2].tns+=query(pt[p2].c);
        tmp[k++]=pt[p2++];
    }
    for(int i=l;i<=mid;++i){ist(pt[i].c,-pt[i].cnt);}
    for(int i=0;i<k;++i){pt[l+i]=tmp[i];}
} 

signed main(){
    n=read(),d=read();
    for(int i=1;i<=n;++i){
        int u=read(),v=read(),w=read();
        pt[i]={u,v,w,1,0};
    }
    sort(pt+1,pt+n+1,cmp);
    m=1;
    for(int i=2;i<=n;++i){
        if(pt[i]==pt[m])pt[m].cnt++;
        else pt[++m]=pt[i];
    }//去重并统计
    solve(1,m);
    for(int i=1;i<=m;++i){
        ans[pt[i].tns+pt[i].cnt-1]+=pt[i].cnt;
    }
    for(int i=0;i<n;++i)printf("%lld\n",ans[i]);
    return 0;
}

3 时间复杂度分析

对于分治，一共 $\text{log}(n)$ 层，每层有 $O(n)$ 的复杂度，每次树状数组的修改和查询有 $O(\text{log}n)$ 的复杂度。因此总的时间复杂度为 $O(n\text{log}^2n )$。

4 后话

待补……吗？