链接

https://www.luogu.org/problemnew/show/P3810

题解

首先按照a、b、c的优先级排序，这样第一维已经有序了
考虑第二维使用CDQ分治
在递归合并的时候，按照b的大小关系合并
左侧对右侧的影响是，首先a、b已经满足条件（在排序的时候，和合并时候），c有可能满足，所以在树状数组上更新c的值，当右侧统计答案时，在树状数组上查找小于等于c的个数即可
注意，为了方便统计，需要将完全相同的合并并计数，在树状数组更新的值就是个数

代码

#include<bits/stdc++.h>
#define N 100010
#define INF 0x3f3f3f3f
#define eps 1e-10
#define pi 3.141592653589793
#define P 1000000007
#define LL long long
#define pb push_back
#define fi first
#define se second
#define cl clear
#define si size
#define lb lower_bound
#define ub upper_bound
#define mem(x) memset(x,0,sizeof x)
#define sc(x) scanf("%d",&x)
#define scc(x,y) scanf("%d%d",&x,&y)
#define sccc(x,y,z) scanf("%d%d%d",&x,&y,&z)
using namespace std;

struct node{
    int a,b,c,w,ans;
    bool operator < (const node z) const{
        return a==z.a?(b==z.b?c<z.c:b<z.b):a<z.a;
    }
}q[N],tmp[N];
int ans[N],bar[N],d[N<<1],n,m,T;

inline void up(int x,int p){for (;x<=T;x+=x&-x) d[x]+=p;}
inline int sum(int x){int t=0;for (;x;x-=x&-x) t+=d[x]; return t;}

void CDQ(int l,int r){
    if (l==r) return;
    int t=l+r>>1,x=l,y=t+1,k=l;
    CDQ(l,t);
    CDQ(t+1,r);
    while(x<=t && y<=r){
        if (q[x].b<=q[y].b){
            up(q[x].c,q[x].w);
            tmp[k++]=q[x++];
        } else {
            q[y].ans+=sum(q[y].c);
            tmp[k++]=q[y++];
        }
    }
    while(y<=r){
        q[y].ans+=sum(q[y].c);
        tmp[k++]=q[y++];
    }
    for (int i=l;i<x;i++)  up(q[i].c,-q[i].w);
    while(x<=t) tmp[k++]=q[x++];
    for (int i=l;i<=r;i++) q[i]=tmp[i];
}

int main(int argc, char const *argv[])
{

    scc(n,T); m=1;
    for (int i=1;i<=n;i++)
        sccc(q[i].a,q[i].b,q[i].c),q[i].w=1;

    sort(q+1,q+n+1);

    for (int i=2;i<=n;i++)
        if (q[i].a==q[m].a&&q[m].b==q[i].b&&q[m].c==q[i].c) q[m].w++;
    else
        q[++m]=q[i];

    CDQ(1,m);

    for (int i=1;i<=m;i++)
        bar[q[i].ans+q[i].w-1]+=q[i].w;

    for (int i=0;i<n;i++) printf("%d\n",bar[i]);
    return 0;
}