欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

三维偏序(陌上花开)---洛谷P3810&&BZOJ3262(cdq分治--归并排序+树状数组)

程序员文章站 2022-05-14 18:45:32
...

洛谷题目链接https://www.luogu.org/problem/P3810

BZOJ题目链接https://www.lydsy.com/JudgeOnline/problem.php?id=3262

Description

有n朵花,每朵花有三个属性:花形(s)、颜色(c)、气味(m),用三个整数表示。

现在要对每朵花评级,一朵花的级别是它拥有的美丽能超过的花的数量。

定义一朵花A比另一朵花B要美丽,当且仅Sa>=Sb,Ca>=Cb,Ma>=Mb。

显然,两朵花可能有同样的属性。需要统计出评出每个等级的花的数量。

Input

第一行为N,K (1 <= N <= 100,000, 1 <= K <= 200,000 ), 分别表示花的数量和最大属性值。

以下N行,每行三个整数si, ci, mi (1 <= si, ci, mi <= K),表示第i朵花的属性

Output

包含N行,分别表示评级为0...N-1的每级花的数量。

Sample Input

10 3
3 3 3
2 3 3
2 3 1
3 1 1
3 1 2
1 3 1
1 1 2
1 2 2
1 3 2
1 2 1

Sample Output

3
1
3
0
1
0
1
0
0
1


。。。蜜汁BUG,重构之后才过了QAQ

三维偏序比二维偏序多了一维,但我们还是可以按照二维偏序的思路来想。先固定住第一维,然后对于第二维用归并排序,第三维用树状数组。

我们在归并的时候考虑 [l,mid] 对 [mid+1,r] 的贡献。因为我们已经按属性 a 排过序了,所以在排序属性 b 的时候,无论属性 a 怎么被打乱,[mid+1,r] 所有元素的属性 a 一定不小于 [l,mid] 中所有元素的属性 a,那么我们就可以把[l,mid]内的属性z一个个放到树状数组里面统计了,和二维偏序是一样的做法。接下来还有一个比较重要的就是重复元素--由于这并不是真真的坐标,所以他们会重和,所以我们需要对重复的元素进行剔除和累加。

以下是AC代码:

#include <bits/stdc++.h>
using namespace std;

const int mac=1e5+10;
const int maxn=2e5+10;

int n,m;
int ans[mac],c[maxn];

struct node
{
    int x,y,z,ans,f;
}a[mac],b[mac];

bool cmp(node a,node b)
{
    if (a.x!=b.x) return a.x<b.x;
    if (a.y!=b.y) return a.y<b.y;
    return a.z<b.z;
}

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

void update(int pos,int val)
{
    while (pos<=m){
        c[pos]+=val;
        pos+=lowbit(pos);
    }
}

int query(int pos)
{
    int sum=0;
    while (pos>0){
        sum+=c[pos];
        pos-=lowbit(pos);
    }
    return sum;
}

void cdq(int l,int r)
{
    if (l==r) return;
    int mid=(l+r)>>1;
    cdq(l,mid);cdq(mid+1,r);
    int ll=l,rr=mid+1,cnt=l-1;
    while (ll<=mid && rr<=r){
        if (a[ll].y<=a[rr].y){//这个时候后半段对前半段是不会产生贡献的,所以不用统计前半段的答案
            update(a[ll].z,a[ll].f);
            b[++cnt]=a[ll++];
        }
        else {
            a[rr].ans+=query(a[rr].z);
            b[++cnt]=a[rr++];
        }
    }
    while (ll<=mid){
        update(a[ll].z,a[ll].f);//实际上这里的这个是没有用的,只不过是为了方便之后的清空
        b[++cnt]=a[ll++];
    }
    while (rr<=r){
        a[rr].ans+=query(a[rr].z);
        b[++cnt]=a[rr++];
    }
    for (int i=l; i<=mid; i++) update(a[i].z,-a[i].f);
    cnt=0;
    for (int i=l; i<=r; i++) a[i]=b[i];
}

int main()
{
    scanf ("%d%d",&n,&m);
    for (int i=1; i<=n; i++){
        scanf ("%d%d%d",&a[i].x,&a[i].y,&a[i].z);
        a[i].f=1;
    }
    sort(a+1,a+1+n,cmp);
    int cnt=1;
    for (int i=2; i<=n; i++){
        if (a[i].x==a[cnt].x && a[i].y==a[cnt].y && a[i].z==a[cnt].z)
            a[cnt].f++;//f保留的是重复元素的个数
        else a[++cnt]=a[i];
    }
    cdq(1,cnt);
    for (int i=1; i<=cnt; i++){
        ans[a[i].ans+a[i].f-1]+=a[i].f;//由于=是成立的,所以我们要加上相等的个数
    }
    for (int i=0; i<n; i++)
        printf ("%d\n",ans[i]);
    return 0;
}