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

HINT

 

1 <= N <= 100,000, 1 <= K <= 200,000

/*  这个东西好像叫三维偏序，就是排序一维，cdq一维，树状数组一维。  自己尝试码了码，但是出现了很多问题，然后看了看网上的代码，感觉还是不怎么懂 */#include
      
       #include
       
        #include
        
         #define N 500010using namespace std;int now,n,ans[N],k;struct node{    int c,s,m,num,ans;};node a[N],b[N],q[N];struct Node{    int v,T;};Node t[N*3];bool cmp(node a,node b){    if(a.s==b.s&&a.c==b.c)return a.m
         
          >1;    int q1=l,q2=m+1;    for(int i=l;i<=r;i++)        if(q1<=m&&a[i].s<=m)            q[q1++]=a[i];        else q[q2++]=a[i];    for(int i=l;i<=r;i++)        a[i]=q[i];    cdq(l,m);    now++;    int j=l;    for(int i=m+1;i<=r;i++){        for(;j<=m;j++)            if(a[i].c>=a[j].c)modify(a[j].m,a[j].num);            else break;        a[i].ans+=query(a[i].m);    }    cdq(m+1,r);    q1=l;q2=m+1;    for(int i=l;i<=r;i++)        if((a[q1].c<=a[q2].c||q2>r)&&q1<=m)            q[i]=a[q1++];        else q[i]=a[q2++];    for(int i=l;i<=r;i++)        a[i]=q[i];}int main(){    now=0;    scanf("%d%d",&n,&k);    for(int i=1;i<=n;i++){        scanf("%d%d%d",&a[i].s,&a[i].c,&a[i].m);        a[i].num=1;    }    sort(a+1,a+n+1,cmp);    int tot=0;    for(int i=1;i<=n;i++){        int k=(a[i].s==a[i-1].s)&(a[i].c==a[i-1].c)&(a[i].m==a[i-1].m);        if(i==1||!k)a[++tot]=a[i];        else a[tot].num++;    }    for(int i=1;i<=tot;i++)a[i].s=i;    sort(a+1,a+tot+1,cmp2);    cdq(1,tot);    for(int i=1;i<=tot;i++)        ans[a[i].ans]+=a[i].num;    for(int i=0;i