简介
前置芝士：归并排序。
\(cdq\) 分治是个离线算法，可以解决三维偏序或者优化 \(dp\)。
题目
直接上个题目：陌上花开。
维护三维偏序有个口诀：一维排序，二维归并，三位数据结构。
考虑第一维直接排序解决掉，然后还剩两维。
我们考虑第二维用归并排序解决掉。然后假设当前区间 \([l,r]\)，区间中点 \(mid\)。那么我们通过递归可以解决 \([l,mid],[mid+1,r]\) 内部的贡献，现在要考虑解决两个点在两个区间中的贡献。
我们在递归时已经按照第二维排好序了。但是有个问题，第一维的限制呢？这样不是把第一维的限制忽略掉了吗？
再想一想我们求的东西，两个端点分别在两个区间内，而这时两个区间内的第一维的相对大小仍然是满足要求的，因为这时他们还没有完成第二维的排序。
然后如果我们发现这时第二维满足了要求，我们就把第三维扔进树状数组或者权值线段树内（推荐树状数组）。否则（重点），此时的 \([l,i-1]\) 是一个极大的 \(\forall u\in[l,i-1],u\) 满足前两维的偏序关系的区间。这时我们就要统计贡献了。
然后就是，我们把没跑完的部分跑完，但是这里的循环顺序非常重要，不能更改，具体原因写在代码注释里了。
最后记得堆原数组去个重，不然会出问题。
代码：
#include<bits/stdc++.h>
#define int long long
#define N 200005
using namespace std;
int n,m,k,c[N],siz[N],f[N],res[N];
struct node{
int x,y,z,id;
bool operator<(const node &t)const{
if(x!=t.x)return x<t.x;
if(y!=t.y)return y<t.y;
return z<t.z;
}
bool operator!=(const node &t)const{
return x!=t.x||y!=t.y||z!=t.z;
}
}a[N],b[N];
int lowbit(int x){//树状数组三件套1
return x&-x;
}
void add(int x,int v){//树状数组三件套2
while(x<=k){
c[x]+=v;
x+=lowbit(x);
}
}
int qry(int x){//树状数组三件套3
int res=0;
while(x){
res+=c[x];
x-=lowbit(x);
}
return res;//求有多少数比x小
}
void cdq(int l,int r){
if(l>=r)return;
int mid=l+r>>1;
cdq(l,mid);cdq(mid+1,r);//归并排序
int i=l,j=mid+1,now=0;
while(i<=mid&&j<=r){
if(a[i].y<=a[j].y){//如果满足，证明还不是极大区间
add(a[i].z,siz[a[i].id]);//那么就把这个数存进去，注意有多个一起存
b[now++]=a[i++];//归并排序
}
else{
res[a[j].id]+=qry(a[j].z);//这时区间达到极大，可以统计
b[now++]=a[j++];
}
}
while(j<=r){//1，如果放在2后面会导致统计错误
res[a[j].id]+=qry(a[j].z);
b[now++]=a[j++];
}
for(int x=l;x<i;x++){//2，如果放到3后面会导致清空错误（多清空）
add(a[x].z,-siz[a[x].id]);
}
while(i<=mid){//3，不能放到2前面，原因见2
b[now++]=a[i++];
}//上面这3个循环的顺序不能换
for(i=l,j=0;i<=r;i++,j++){
a[i]=b[j];//归并排序
}
}
signed main(){
cin>>n>>k;
for(int i=1;i<=n;i++){
cin>>a[i].x>>a[i].y>>a[i].z;
}
sort(a+1,a+n+1);
for(int i=1;i<=n;i++){
if(a[i]!=a[i-1])b[++m]=a[i];//这里是去重
siz[m]++;//记录相同的元素个数
}
for(int i=1;i<=m;i++){
a[i]={b[i].x,b[i].y,b[i].z,i};//记录去重后的数组
}
cdq(1,m);
for(int i=1;i<=m;i++){
int id=a[i].id;
//数量为去重后统计的答案再加上其他相同的元素的数量
f[res[id]+siz[id]-1]+=siz[id];//这里减1是因为去掉自己
}
/*
这里笔者写的时候有个疑惑，为什么把id改成i是对的，原因如下：
首先，这两个写法从逻辑上来说不等价，但是结果上来说等价
因为原来的id是按照第一维排序的，上面的i是按照第二维排序的，所以两者本质不同
但是，由于id是不重复的，所以id恰好遍历1-m
所以从结果上来说两者等价
*/
for(int i=0;i<n;i++){
cout<<f[i]<<'\n';
}
return 0;
}