就是将逆序对转化到了三维上去
原理等我寒假再补
第一维sort解决
第二维并归排序（cdq）解决
第三维树状数组
// luogu-judger-enable-o2
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using std::sort;
const int maxn=101000;
const int Max=201000;
struct node
{
int a,b,c;
int size,ans;
bool operator <= (const node &A)
{
if(b!=A.b) return b<=A.b;
if(c!=A.c) return c<=A.c;
return c<=A.c;
}
};
node Q[maxn],tmp[maxn];
int base[Max],t[Max],len,Tim;
int TOT[Max<<1];
int n,m;
void add(int pos,int val,int T)
{
while(pos<=len)
{
if(t[pos]!=T)
{
t[pos]=T;
base[pos]=0;
}
base[pos]+=val;
pos+=(pos&(-pos));
}
return ;
}
int sum(int pos,int T)
{
int res=0;
while(pos)
{
if(t[pos]!=T)
{
t[pos]=T;
base[pos]=0;
}
res+=base[pos];
pos-=(pos&(-pos));
}
return res;
}
bool compare(const node &a,const node &b)
{
if(a.a!=b.a) return a.a<b.a;
if(a.b!=b.b) return a.b<b.b;
return a.c<b.c;
}
void cdq(int l,int r)
{
if(l==r) return ;
int mid=(l+r)>>1,o=0,T=++Tim;
cdq(l,mid);cdq(mid+1,r);
int q=l,p=mid+1;
while(q<=mid&&p<=r)
{
if(Q[q]<=Q[p])//按照第二维顺序，左区间的元素算贡献（利用bit），右区间的元素进行第三维元素的顺序对查询
{
add(Q[q].c,Q[q].size,T);//利用时间戳
tmp[o++]=Q[q++];//回收元素
}
else
{
Q[p].ans+=sum(Q[p].c,T);
tmp[o++]=Q[p++];
}
}
while(q<=mid) tmp[o++]=Q[q++];//将没有处理的元素压回tmp
while(p<=r)
{
Q[p].ans+=sum(Q[p].c,T);
tmp[o++]=Q[p++];
}
for(int i=0;i<o;i++) Q[l+i]=tmp[i];//回填
return ;
}
int main()
{
scanf("%d%d",&n,&m);
len=m;
for(int i=1;i<=n;i++)
scanf("%d%d%d",&tmp[i].a,&tmp[i].b,&tmp[i].c);
sort(tmp+1,tmp+1+n,compare);//解决第一位顺序
int T=0;
for(int i=1,pas=1;i<=n;i++)//去重，cdq无法正确处理相同原元素
{
if(tmp[i].a!=tmp[i+1].a||tmp[i].b!=tmp[i+1].b||tmp[i].c!=tmp[i+1].c)
{
Q[++T]=tmp[i];
Q[T].size=pas;Q[T].ans=0;
pas=1;
}
else pas++;
}
cdq(1,T);
for(int i=1;i<=T;i++) TOT[Q[i].ans+Q[i].size-1]+=Q[i].size;
for(int i=0;i<n;i++) printf("%d\n",TOT[i]);
}