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

Bob_Wang · 2019-07-11 15:06:51 · 题解

陌上花开——浅谈CDQ分治

事先声明，我是在洛谷题解里看懂的，所以我的这篇所谓的“题解”，实际上可以看做对@echo大佬题解的补充。

什么是CDQ分治

CDQ分治，就是一种分治思想。可能度娘比我解释地更清楚。主要用来求偏序。

大体思路

如图所示：

1. 将一个区间[l,r]一直向下二分为[l,mid]和[mid+1,r]；
2. 返回时分别处理区间[l,mid]和[mid+1,r]，双指针实现，处理时以当前值为下标，当前元素的个数为权值加入树状数组；

3. 合并区间[l,mid]和[mid+1,r]； 具体处理方式我会在代码里讲。

   是不是很眼熟？？？ 其实就跟归并排序差不多。

   为什么要用树状数组？ 因为好求前缀和啊。

   这里以三维偏序为例，浅谈CDQ分治。

   例题

   陌上花开(很好听的样子)

有n个元素，第i个元素有a_i，b_i，c_i三种属性，设f(i)表示满足a_j<=a_i,b_j<=b_i且c_j<=c_i的j的数量。

对于d∈[0,n),求f(i)=d的数量.

输入格式：

第一行两个整数n，k,分别表示元素数量和最大属性值。

之后n行，每行三个整数a_i,b_i，c_i，分别表示三个属性值。

输出格式：

输出n行，第d+1行表示 f(i) = d的i 的数量。(注意是输出答案为d的i的数量)

解法

不难看出，对于任意的元素i，有三个维度。

要找出使三个维度都满足条件的点，需要用到三维偏序。而我对于三维偏序的理解是：一维一维地处理。

• 读入 当然是结构体啦！

struct node
{
    int a,b,c,cnt,ans;
}s1[maxn],s2[maxn];

其中a表示第一维，b表示第二维，c表示第三维，cnt表示相同元素个数（为什么要统计相同元素个数请看题意），ans表示对于表示当前节点的答案。

• 输入 直接上代码：

scanf("%d%d",&n,&k);
mx=k;//树状数组的区间
for(int i=1;i<=n;++i)
{
    int a,b,c;
    scanf("%d%d%d",&a,&b,&c);
    s1[i].a=a;
    s1[i].b=b;
    s1[i].c=c;
}//初始化输入

在这里说明一下，k是整个数组中权值的最大值，而树状数组的下标 i 表示的是权值为 i 的元素的个数。所以 k 可以理解为树状数组下标的最大值。

• 第一维处理（以第一维为关键字排序）

bool cmp1(node x,node y)
{
    if(x.a==y.a)
    {
        if(x.b==y.b)return x.c<y.c;
        else return x.b<y.b;
    }
    else return x.a<y.a;
}//第一维排序

主函数内：

sort(s1+1,s1+1+n,cmp1);//第一维为关键字排序

• 转入CDQ数组 很简单，只需合并相同项就可以了。 其中top可以理解为相同项的个数。（注意更新元素个数）

for(int i=1;i<=n;++i)
{
    top++;
    if(s1[i].a!=s1[i+1].a||s1[i].b!=s1[i+1].b||s1[i].c!=s1[i+1].c)
    {
        m++;//更新元素个数
        s2[m].a=s1[i].a;
        s2[m].b=s1[i].b;
        s2[m].c=s1[i].c;
        s2[m].cnt=top;
        top=0;
    }
}//第一维已有序,合并相同节点

• 接下来就是重点CDQ分治的部分了！！！

1.向下二分（类似归并排序）

if(l==r)return;
int mid=(l+r)>>1;
cdq(l,mid);
cdq(mid+1,r);//类似于归并排序

2.向上合并 第二维处理：分别把[l,mid+1]和[mid+1,r]以第二维为关键字排序。

bool cmp2(node x,node y)
{
    if(x.b==y.b)
    return x.c<y.c;
    else return x.b<y.b;
}//第二维排序

CDQ函数内：

sort(s2+l,s2+mid+1,cmp2);
sort(s2+mid+1,s2+r+1,cmp2);//第二维为关键字排序

分区间排序的好处：保证[l,mid]的第一维大于[mid+1,r]的第一维，并且保证[l,mid]内和[mid+1,r]内的第二维单调不下降。

建立双指针i,j。j指向[l,mid]数组，i指向[mid+1,r]数组。此时，对于每个s2[i]和s2[j]，已有s2[i]的第一维大于或等于s2[j]的第一维。那么for i从mid+1到r，一遇到s2[i].b>=s2[j].b并且j<=mid，将s2[j]加入到以s2[j].c为下标，s2[j].cnt为权值的树状数组中，最后统计s2[i]的答案。

int i,j=l;
for(i=mid+1;i<=r;++i)
{
    while(s2[i].b>=s2[j].b&&j<=mid)
    {
        add(s2[j].c,s2[j].cnt);//在s2[j]位置加上s2[j]的个数
        j++;
    }
    s2[i].ans+=query(s2[i].c);//保证树状数组里的数一定符合条件
}//类似归并

3.最后，不要忘记清空树状数组（不可以memset0）：

for(i=l;i<j;++i)
add(s2[i].c,-s2[i].cnt);//清空树状数组

• 统计答案 设su为答案数组（不要问我为什么要用这么奇怪的字母，因为我也编不下来了），那么对于对于下标i,su[s2[ i ].ans+s2[i].cnt-1]+=s2[i].cnt，即s2[i]的答案其实就是比s2[i]小的元素个数加上s2[i]的元素总数减1，即s2[i].ans+s2[i].cnt-1，加上s2[i]的个数。最后输出即可。

  for(int i=1;i<=m;++i)
  su[s2[i].ans+s2[i].cnt-1]+=s2[i].cnt;
  for(int i=0;i<n;++i)
  printf("%d\n",su[i]);

完整代码

#include<cstdio>
#include<algorithm>
#define maxn 200005
using namespace std;

struct node
{
    int a,b,c,cnt,ans;
}s1[maxn],s2[maxn];
int n,m,k,mx,top,su[maxn];
int c[maxn];//树状数组

bool cmp1(node x,node y)
{
    if(x.a==y.a)
    {
        if(x.b==y.b)return x.c<y.c;
        else return x.b<y.b;
    }
    else return x.a<y.a;
}//第一维排序

bool cmp2(node x,node y)
{
    if(x.b==y.b)
    return x.c<y.c;
    else return x.b<y.b;
}//第二维排序

int lowbit(int x)
{
    return x&(-x);
}

void add(int x,int y)
{
    while(x<=mx)
    {
        c[x]+=y;
        x+=lowbit(x);
    }
}//树状数组单点加

int query(int x)
{
    int sum=0;
    while(x)
    {
        sum+=c[x];
        x-=lowbit(x);
    }
    return sum;
}//求单点前缀和
//树状数组看得懂吧QAQ

void cdq(int l,int r)
{
    if(l==r)return;
    int mid=(l+r)>>1;
    cdq(l,mid);
    cdq(mid+1,r);//类似于归并排序
    sort(s2+l,s2+mid+1,cmp2);
    sort(s2+mid+1,s2+r+1,cmp2);//第二维为关键字排序
    int i,j=l;
    for(i=mid+1;i<=r;++i)
    {
        while(s2[i].b>=s2[j].b&&j<=mid)
        {
            add(s2[j].c,s2[j].cnt);//在s2[j]位置加上s2[j]的个数
            j++;
        }
        s2[i].ans+=query(s2[i].c);//保证树状数组里的数一定符合条件
    }//类似归并
    for(i=l;i<j;++i)
    add(s2[i].c,-s2[i].cnt);//清空树状数组
}//cdq分治

int main()
{
    scanf("%d%d",&n,&k);
    mx=k;//树状数组的区间
    for(int i=1;i<=n;++i)
    {
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        s1[i].a=a;
        s1[i].b=b;
        s1[i].c=c;
    }//初始化输入
    sort(s1+1,s1+1+n,cmp1);//第一维为关键字排序
    for(int i=1;i<=n;++i)
    {
        top++;
        if(s1[i].a!=s1[i+1].a||s1[i].b!=s1[i+1].b||s1[i].c!=s1[i+1].c)
        {
            m++;
            s2[m].a=s1[i].a;
            s2[m].b=s1[i].b;
            s2[m].c=s1[i].c;
            s2[m].cnt=top;
            top=0;
        }
    }//第一维已有序,合并相同节点
    cdq(1,m);//cdq分治
    for(int i=1;i<=m;++i)
    su[s2[i].ans+s2[i].cnt-1]+=s2[i].cnt;
    for(int i=0;i<n;++i)
    printf("%d\n",su[i]);
    return 0;
}

终于写完了，好辛苦啊！！！
然而我还是个蒟蒻。
再次感谢@echo大佬！！！