洛谷P3810-陌上开花(三维偏序, CDQ, 树状数组)

链接:

https://www.luogu.org/problem/P3810#submit

题意:

一个元素三个属性, x, y, z, 给定求f(b) = {ax <= bx, ay <= by, az <= bz}, a的数量, 求0-(n-1)个数有多少个点满足

思路:

三维偏序, CDQ分治, 听说过, 一直想学, 先写板子题, 二维偏序就属性减到连个,搞一下.

CDQ的思想就是先对第一维排序, 左边的可以给有变贡献, 在分治下去, 同时对第二维排序, 将可用的点的第三维用数据结构维护一下, 挨个统计.

代码:

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 2e5+10;

struct Node

{

    int x, y, z;

    int cnt;

    int ans;

}a[MAXN], b[MAXN];

int C[MAXN], Res[MAXN];

int n, k, cnt;

bool CmpX(Node a, Node b)

{

    if (a.x != b.x)

        return a.x < b.x;

    else if (a.y != b.y)

        return a.y < b.y;

    else

        return a.z < b.z;

}

bool CmpY(Node a, Node b)

{

    if (a.y != b.y)

        return a.y < b.y;

    else

        return a.z < b.z;

}

int Lowbit(int x)

{

    return x&(-x);

}

void Update(int pos, int val)

{

    while (pos <= k)

    {

        C[pos] += val;

        pos += Lowbit(pos);

    }

}

int Query(int pos)

{

    int ans = 0;

    while (pos > 0)

    {

        ans += C[pos];

        pos -= Lowbit(pos);

    }

    return ans;

}

void CDQ(int l, int r)

{

    if (l == r)//边界条件

        return ;

    int mid = (l+r)/2;

    CDQ(l, mid);

    CDQ(mid+1, r);

    sort(a+l, a+mid+1, CmpY);

    sort(a+mid+1, a+r+1, CmpY);

    int i = l, j = mid+1;

    while (j <= r)

    {

        while (i <= mid && a[j].y >= a[i].y)

            Update(a[i].z, a[i].cnt), i++;

        a[j].ans += Query(a[j].z);

        j++;

    }

    for (int z = l;z < i;z++)

        Update(a[z].z, -a[z].cnt);

}

int main()

{

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

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

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

    sort(b+1, b+1+n, CmpX);

    a[1] = b[1];

    a[1].cnt = 1;

    cnt = 1;

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

    {

        if (b[i].x != a[cnt].x || b[i].y != a[cnt].y || b[i].z != a[cnt].z)

            a[++cnt] = b[i], a[cnt].cnt = 1;

        else

            a[cnt].cnt++;

    }

    CDQ(1, cnt);

    for (int i = 1;i <= cnt;i++)

        Res[a[i].ans+a[i].cnt-1] += a[i].cnt;

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

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

    return 0;

}