经典问题：三维偏序
题：https://www.luogu.org/problem/P3810
一般处理：先按照自己定义的第一维排好序，那么在接下来的俩维判断中，我们就可以消除第一维造成的影响，接着用以前学过的分治排序法来处理第二维，以第二维作为排序对象，对于分治的[l,midd]和[midd+1,r]这俩个区间
对于区间 [m+1, r]中的某个元素x，将区间 [l, m] 的第二维小于x的元素的按第三维的权值加入树状数组，
最后区间 [l, m] 对区间 x 的贡献就是查询树状数组中小于x第三维的个数
可以边进行分治边进行归并排序，树状数组要及时清空
using namespace std;
typedef long long ll;
inline int read(){
int sum=0,x=1;
char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-')
x=0;
ch=getchar();
}
while(ch>='0'&&ch<='9')
sum=(sum<<1)+(sum<<3)+(ch^48),ch=getchar();
return x?sum:-sum;
}
inline void write(ll x){
if(x<0)
putchar('-'),x=-x;
if(x>9)
write(x/10);
putchar(x%10+'0');
}
#define pb push_back
#define lowbit(x) (x&(-x))
const int M=2e5+5;
struct node{
int x,y,z,cnt,ans;
bool operator < (const node &b)const{
if(x!=b.x)
return x<b.x;
else if(y!=b.y)
return y<b.y;
else
return z<b.z;
}
}a[M>>1],temp[M>>1];
int tree[M];
int n,k;
int ANS[M];
void add(int i,int x){
while(i<=k){
tree[i]+=x;
i+=lowbit(i);
}
}
int query(int i){
int res=0;
while(i){
res+=tree[i];
i-=lowbit(i);
}
return res;
}
void cdq(int l,int r){
if(l==r){
a[l].ans+=a[l].cnt-1;
return ;
}
int midd=(l+r)>>1;
cdq(l,midd);
cdq(midd+1,r);
int i=l,j=midd+1,op=l;
while(j<=r){
while(i<=midd&&a[i].y<=a[j].y){
add(a[i].z,a[i].cnt);
temp[op++]=a[i];
i++;
}
a[j].ans+=query(a[j].z);
temp[op++]=a[j];
j++;
}
for(j=l;j<i;j++)
add(a[j].z,-a[j].cnt);
while(i<=midd)
temp[op++]=a[i],i++;
for(i=l;i<=r;i++)
a[i]=temp[i];
}
int main(){
n=read(),k=read();
for(int i=1;i<=n;i++)
a[i].x=read(),a[i].y=read(),a[i].z=read();
sort(a+1,a+1+n);
int now=1,cnt=0;
for(int i=2;i<=n;i++){
if(a[i-1].x==a[i].x&&a[i-1].y==a[i].y&&a[i-1].z==a[i].z)
now++;
else{
a[++cnt]=a[i-1];
a[cnt].cnt=now;
a[cnt].ans=0;
now=1;
}
}
a[++cnt]=a[n];
a[cnt].cnt=now;
a[cnt].ans=0;
cdq(1,cnt);
for(int i=1;i<=cnt;i++)
ANS[a[i].ans]+=a[i].cnt;
for(int i=0;i<n;i++)
printf("%d\n",ANS[i]);
return 0;
}