题目连接

题面：

代码：

//因为相等的也算，所以要去重且统计相等的有多少个
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<string>
#include<queue>
#define ll long long
#define llu unsigned ll
using namespace std;
const int maxn=200100;
struct node
{
    int x,y,z;
    int cnt,ans,id;
    bool operator == (const node &b)
    {
        return x==b.x&&y==b.y&&z==b.z;
    }
}a[maxn];
bool cmp1(const node &a,const 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;
}

bool cmp2(const node &a,const node &b)
{
    if(a.y!=b.y) return a.y<b.y;
    if(a.z!=b.z) return a.z<b.z;
    return a.id<b.id;
}

int sum[maxn],n,k,f[maxn];
void add(int x,int val)
{
    for(;x<=k;x+=(x&(-x)))
        sum[x]+=val;
}

int ask(int x)
{
    int ans=0;
    for(;x;x-=(x&(-x)))
        ans+=sum[x];
    return ans;
}

void cdq(int l,int r)
{
    if(l==r) return ;
    int mid=(l+r)>>1;
    cdq(l,mid);cdq(mid+1,r);
    sort(a+l,a+r+1,cmp2);
    for(int i=l;i<=r;i++)
    {
        if(a[i].id<=mid) add(a[i].z,a[i].cnt);
        else a[i].ans+=ask(a[i].z);
    }
    for(int i=l;i<=r;i++)
        if(a[i].id<=mid) add(a[i].z,-a[i].cnt);
}

int main(void)
{
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++)
        scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].z);
    sort(a+1,a+n+1,cmp1);
    int cnt=0;
    for(int i=1;i<=n;i++)
    {
        if(i>1&&a[i]==a[i-1]) a[cnt].cnt++;
        else a[++cnt]=a[i],a[cnt].cnt=1;
    }
    for(int i=1;i<=cnt;i++)
        a[i].id=i,a[i].ans=0;
    cdq(1,cnt);
    for(int i=1;i<=cnt;i++)
        f[a[i].ans+a[i].cnt-1]+=a[i].cnt;
    for(int i=0;i<n;i++)
        printf("%d\n",f[i]);
    return 0;
}