Eva

Time Limit: 20 Sec  Memory Limit: 256 MB
Description

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

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

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

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

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

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

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

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

3
1
3
0
1
0
1
0
0
1

/**************************************************************

    Problem: 3262

    User: ictsing

    Language: C++

    Result: Accepted

    Time:3492 ms

    Memory:6376 kb

****************************************************************/

 

//BZOJ 3262 陌上花开

/*

CDQ分治

主要思想：分而治之，治之之时考虑左半边区间对右半边区间的影响

以第一维排序并去重，数组中记录相同的花有多少朵。

然后CDQ分治处理，处理时，将[l,mid]区间和[mid+1,r]区间分别按第二维关键字排序，

并用树状数组以第三维为下标，维护每一朵花的出现次数。每一次处理[l,mid]对[mid+1,r]的影响时，

只需考虑第二维的影响即可（因为[l,mid]区间的x一定小于[mid+1,r]区间的x，而第三维用树状数组维护也不需要考虑），

当第二维符合要求时，将它的影响加入树状数组中

 

写CDQ分治一定要注意排序是怎么排的

*/

#include <iostream>

#include <cstdio>

#include <algorithm>

using namespace std;

const int mt = 100000+5;

const int mm = 200000+5;

struct flower{

    int x,y,z,ans,cnt;

}c[mt],d[mt];

int bit[mm];

int n,k;

int num[mt];

inline int read()

{

    int num=0,flag=1;

    char ch;

    do{

        ch=getchar();

        if(ch=='-') flag=-1;

    }while(ch<'0'||ch>'9');

    do{

        num=num*10+ch-'0';

        ch=getchar();

    }while(ch>='0'&&ch<='9');

    return num*flag;

}

bool cmpx(flower a,flower b)

{

    if(a.x<b.x) return 1;

    if(a.x>b.x) return 0;

    if(a.y<b.y) return 1;

    if(a.y>b.y) return 0;

    if(a.z<b.z) return 1;

    return 0;

}

bool cmpy(flower a,flower b)

{

    if(a.y<b.y) return 1;

    if(a.y>b.y) return 0;

    if(a.z<b.z) return 1;

    if(a.z>b.z) return 0;

    if(a.x<b.x) return 1;

    return 0;

}

void update(int x,int y)

{

    for(int i=x;i<=k;i+=(i&-i))

        bit[i]+=y;

}

int sum(int x)

{

    int res=0;

    for(int i=x;i;i-=(i&-i))

        res+=bit[i];

    return res;

}

int tot;

void CDQ(int l,int r)

{

    if(l==r)

    {

        d[l].ans+=d[l].cnt-1;

        return ;

    }

    int m=(l+r)>>1;

    CDQ(l,m); CDQ(m+1,r); 

    sort(d+l,d+m+1,cmpy);//这个要按照基本法，不能把它视作分治了，不然会死循环

    sort(d+m+1,d+r+1,cmpy);

    int j=l;

    for(int i=m+1;i<=r;i++)

    {

        while(j<=m&&d[j].y<=d[i].y)

            update(d[j].z,d[j].cnt),j++;

        d[i].ans+=sum(d[i].z);

    } 

    for(int i=l;i<j;i++) update(d[i].z,-d[i].cnt);

}

int main()

{

    n=read(),k=read();

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

        c[i].x=read(),c[i].y=read(),c[i].z=read(),c[i].ans=1;

    sort(c+1,c+n+1,cmpx);

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

        if(i!=1&&c[i].x==c[i-1].x&&c[i].y==c[i-1].y&&c[i].z==c[i-1].z) 

            d[tot].cnt++;

        else d[++tot]=c[i],d[tot].cnt=1;

    //for(int i=1;i<=tot;i++)

        //cout<<d[i].x<<" "<<d[i].y<<" "<<d[i].z<<" "<<d[i].cnt<<" "<<d[i].ans<<endl;

    CDQ(1,tot);

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

        num[d[i].ans]+=d[i].cnt;

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

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

    return 0;

}