专题：CDQ 分治

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=200005;
int n,k,m;
struct node
{
    int x,y,z,id,w;
    bool operator < (const node &A)const{
        if(A.x==x && A.y==y) return z < A.z;
        else if(A.x==x) return y < A.y;
        return x < A.x;
    }
}a[N],b[N],d[N];
int ans[N],c[N],cnt[N];
vector <int> v1,v2[N] ;
int lowbit(int x)
{
    return x & (-x);
}
void add(int x,int v)
{
    for(int i=x;i<N;i+=lowbit(i)) c[i]+=v;
}
int query(int x)
{
    int ans=0;
    for(int i=x;i;i-=lowbit(i)) ans+=c[i];
    return ans;
}
void cdq(int l,int r)
{
    if(l==r) return ;
    int mid=(l+r)>>1;
    cdq(l,mid),cdq(mid+1,r);
    int t1=l,t2=mid+1;
    for(int i=l;i<=r;i++)
    {
        if((t1<=mid && a[t1].y<=a[t2].y) || t2>r)
        {
            add(a[t1].z,a[t1].w);
            b[i]=a[t1++];
        }
        else
        {
            cnt[a[t2].id]+=query(a[t2].z);
            b[i]=a[t2++];
        }
    }
    for(int i=l;i<=mid;i++) add(a[i].z,-a[i].w);
    for(int i=l;i<=r;i++) a[i]=b[i];
}
int main()
{
    cin>>n>>k;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i].x>>a[i].y>>a[i].z;
        a[i].id=i;
    }
    sort(a+1,a+n+1);
    int num=1;
    for(int i=2;i<=n+1;i++)
    {
        if(a[i].x!=a[i-1].x || a[i].y!=a[i-1].y || a[i].z != a[i-1].z)
        {
            d[++m]=a[i-1];
            d[m].w=num;
            num=1;
            v2[a[i-1].id]=v1;
            v1.clear();
        }
        else
        {
            num++;
            v1.push_back(a[i-1].id) ;
        }
    }
    for(int i=1;i<=m;i++) a[i]=d[i];
    cdq(1,m);
    for(int i=1;i<=m;i++)
    {
        int sz=v2[a[i].id].size();
        for(auto v:v2[a[i].id]) cnt[v]+=cnt[a[i].id]+sz;
        cnt[a[i].id]+=sz;
    }
    for(int i=1;i<=n;i++) ans[cnt[i]]++;
    for(int i=0;i<n;i++) cout<<ans[i]<<'\n';
    return 0;
}