#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,k;
struct N{
	int x,y,z,v,cnt;
}b[100010],a[100010];
bool cmpx(N a,N 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 cmpy(N a,N b){
	return a.y<b.y;
}
int lowbit(int x){
	return x&(-x);
} 
struct BIT{
	int tr[200010];
	void add(int x,int v){
		for(int i=x;i<=k;i+=lowbit(i)){
			tr[i]+=v;
		}
	}
	int find(int x){
		int ans=0;
		for(int i=x;i;i-=lowbit(i)){
			ans+=tr[i];
		}
		return ans;
	}
}tr;
void solve(int l,int r){
	if(l==r)return ;
	int mid=(l+r)>>1;
	solve(l,mid);
	solve(mid+1,r);
	sort(a+l,a+mid+1,cmpy);
	sort(a+mid+1,a+r+1,cmpy);
	int i=l,j=mid+1;
	for(;j<=r;j++){
		for(;i<=mid&&a[i].y<=a[j].y;i++)tr.add(a[i].z,a[i].cnt);
		a[j].v+=tr.find(a[j].z);
	}
	for(int k=l;k<i;k++)tr.add(a[k].z,-a[k].cnt);
}
int ans[100010];
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin>>n>>k;
	for(int i=1;i<=n;i++){
		cin>>b[i].x>>b[i].y>>b[i].z;
	}
	sort(b+1,b+1+n,cmpx);
	int m=0;
	for(int i=1;i<=n;i++){
		if(i==1||b[i].x!=b[i-1].x||b[i].y!=b[i-1].y||b[i].z!=b[i-1].z){
			a[++m]=b[i];
			a[m].cnt=1;
			a[m].v=0;
		}
		else{
			a[m].cnt++;
		}
	}
	solve(1,m);
	for(int i=1;i<=m;i++){
		ans[a[i].v+a[i].cnt-1]+=a[i].cnt;
	}
	for(int i=0;i<n;i++){
		cout<<ans[i]<<'\n';
	}
	return 0;
}

二维线段树+动态开点 点修+区查 P3810 三维偏序（陌上花开）

C78 二维线段树+动态开点 点修+区查 P3810 三维偏序（陌上花开）

#include <bits/stdc++.h>
using namespace std;
const int N=1e5+10;
#define mid ((l+r)>>1)
struct node
{
    int a,b,c,n;
    bool operator !=(node no){ return a!=no.a || b!=no.b || c!=no.c;}
    bool operator <(node no) { return a!=no.a? a<no.a : b!=no.b? b<no.b : c<no.c;} 
}a[N];
int n,k,ans[N],aa[N],an,bb[N],bn,cc[N],cn;
int root,totx,xls[N*2],xrs[N*2];
int toty,rt[N*2],yls[N*2*100],yrs[N*2*100],d[N*2*100];
void changeY(int &p,int l,int r,int y,int c)
{
    if(!p)p=++toty;
    d[p]+=c;
    if(l==r) return ;
    if(y<=mid) changeY(yls[p],l,mid,y,c);
    else       changeY(yrs[p],mid+1,r,y,c);
}
void changeX(int &p,int l,int r,int x,int y,int c)
{
    if(!p)p=++totx;
    changeY(rt[p],1,cn,y,c);
    if(l==r) return ;
    if(x<=mid)changeX(xls[p],l,mid,x,y,c);
    else      changeX(xrs[p],mid+1,r,x,y,c);
}
int queryY(int p,int l,int r,int y1,int y2)
{
    if(!p) return 0;
    if(y1<=l && r<=y2) return d[p];
    int res=0;
    if(y1<=mid) res+=queryY(yls[p],l, mid,y1,y2);
    if(y2 >mid) res+=queryY(yrs[p],mid+1,r,y1,y2);
    return res;
}

int queryX(int p,int l,int r,int x1,int x2,int y1,int y2)
{
    if(!p) return 0;
    if(x1<=l && r<=x2) return queryY(rt[p],1,cn,y1,y2);
    int res=0;
    if(x1<=mid) res+=queryX(xls[p],l, mid,x1,x2,y1,y2);
    if(x2 >mid) res+=queryX(xrs[p],mid+1,r,x1,x2,y1,y2);
    return res;
}

int main()
{
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++) scanf("%d%d%d",&a[i].a,&a[i].b,&a[i].c);
    sort(a+1,a+n+1);
    int t=0;for(int i=1,c=1;i<=n;i++,c++) if(a[i]!=a[i+1]){a[++t]=a[i];a[t].n=c;c=0;}
     //当k很大很大的时候，需要对三个属性进行离散化
    for(int i=1;i<=t;i++) aa[i]=a[i].a,bb[i]=a[i].b,cc[i]=a[i].c;
    sort(aa+1,aa+t+1);an=unique(aa+1,aa+1+t)-aa-1;
    sort(bb+1,bb+t+1);bn=unique(bb+1,bb+1+t)-bb-1;
    sort(cc+1,cc+t+1);cn=unique(cc+1,cc+1+t)-cc-1;
    for(int i=1;i<=t;i++)
    {
        a[i].b=lower_bound(bb+1,bb+bn+1,a[i].b)-bb;
        a[i].c=lower_bound(cc+1,cc+cn+1,a[i].c)-cc;
    }
    root=totx=toty=0;memset(rt,0,sizeof(rt));
    memset(d,0,sizeof(d));memset(ans,0,sizeof(ans));
    for(int i=1;i<=t;i++)
    {
           changeX(root,1,bn,a[i].b,a[i].c,a[i].n);
        ans[queryX(root,1,bn,1,a[i].b,1,a[i].c)-1]+=a[i].n;
    }
    for(int i=0;i<n;i++)printf("%d\n",ans[i]);
    return 0;
}

【模板】CDQ 分治+树状数组 P3810 三维偏序

C97【模板】CDQ 分治+树状数组 P3810 三维偏序

#include <bits/stdc++.h>
using namespace std;
const int N=1e5+10,K=2e5+10;
struct node{
    int a,b,c,n,s;
    bool operator!=(node y){return a!=y.a||b!=y.b||c!=y.c;}
    bool operator<(node y){return a!=y.a?a<y.a:b!=y.b?b<y.b:c<y.c;}
}a[N],tmp[N];
int n,k,c[K],cnt[K];
void add(int x,int v){for(;x<=k;x+=x&-x)c[x]+=v;}
int sum(int x){int s=0;for(;x;x-=x&-x)s+=c[x];return s;}
void cdq(int L,int R){
    if(L==R)return;
    int mid=(L+R)>>1;
    cdq(L,mid);cdq(mid+1,R);
    for(int i=L,p1=L,p2=mid+1;i<=R;++i)
        if(p2>R||(p1<=mid&&a[p1].b<=a[p2].b))add(a[p1].c,a[p1].n),tmp[i]=a[p1++];
        else a[p2].s+=sum(a[p2].c),tmp[i]=a[p2++];
    for(int i=L;i<=mid;++i)add(a[i].c,-a[i].n);
    for(int i=L;i<=R;++i)a[i]=tmp[i];
}
int main(){
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;++i)scanf("%d%d%d",&a[i].a,&a[i].b,&a[i].c);
    sort(a+1,a+1+n);
    int t=0;
    for(int i=1,cnt=1;i<=n;++i,++cnt)if(a[i]!=a[i+1])a[++t]=a[i],a[t].n=cnt,cnt=0;
    cdq(1,t);
    for(int i=1;i<=t;++i)cnt[a[i].s+a[i].n-1]+=a[i].n;
    for(int i=0;i<n;++i)printf("%d\n",cnt[i]);
    return 0;
}