三维经典

/*
    废话不多看 打一打就懂了
    排序不用说 按照a,b,c等级排序  
    第二维用归并排序 过程中把c的信息放进树状数组里 
    同时把(l,mid)部分放进树状数组  (mid+1,r)部分求解
    一次归并玩后 删除(l,mid) 在树状数组的记录（其实就是清空 不过这样比memset快 
    因为有相同的坐标 稍微处理一下就行了 
*/
#include<cstdio>
#include<cstring>
#include<algorithm>
#define mid ((l+r)>>1)
using namespace std;
const int N=1e5+50;
int s[N<<1],ans[N],n,m,res;
struct pp {int a,b,c,w,f;} a[N],b[N];
bool cmp(pp a,pp b)
{
    if(a.a!=b.a) return a.a<b.a;
    if(a.b!=b.b) return a.b<b.b;
    return a.c<b.c;
}
int lowbit(int x) {return x&-x;} 
void add(int x,int c) {while(x<=m) s[x]+=c,x+=lowbit(x);} 
int find(int x) {res=0;while(x) res+=s[x],x-=lowbit(x);return res;} 
void CDQ(int l,int r)
{
    if(l>=r) return ; CDQ(l,mid),CDQ(mid+1,r);
    int i=l,j=mid+1,p=l; while(i<=mid&&j<=r)
    {
        if(a[i].b<=a[j].b) add(a[i].c,a[i].w),b[p++]=a[i++];
        else a[j].f+=find(a[j].c),b[p++]=a[j++];
    }
    while(i<=mid) add(a[i].c,a[i].w),b[p++]=a[i++];
    while(j<=r) a[j].f+=find(a[j].c),b[p++]=a[j++];
    for(int i=l;i<=mid;i++) add(a[i].c,-a[i].w);
//    memset(s,0,sizeof(s));   memset果然T飞。。。。。 
    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].a,&a[i].b,&a[i].c),a[i].w=1,a[i].f=0;
    sort(a+1,a+n+1,cmp);
    int top=1;
    for(int i=2;i<=n;i++) // 合并相同点 
        if(a[i].a==a[top].a&&a[i].b==a[top].b&&a[i].c==a[top].c) a[top].w++;
        else a[++top]=a[i];
    CDQ(1,top);
    for(int i=1;i<=top;i++) ans[a[i].f+a[i].w-1]+=a[i].w;
    // 有等于号 所以要加上相同者的数量 
    for(int i=0;i<n;i++) printf("%d\n",ans[i]);
    return 0;
}