[文章目录]
Description
有n朵花，每朵花有三个属性：花形(s)、颜色(c)、气味(m)，又三个整数表示。现要对每朵花评级，一朵花的级别是它拥有的美丽能超过的花的数量。定义一朵花A比另一朵花B要美丽，当且仅当Sa>=Sb,Ca>=Cb,Ma>=Mb。显然，两朵花可能有同样的属性。需要统计出评出每个等级的花的数量。1 <= N <= 100,000, 1 <= K <= 200,000
还是三维偏序统计个数的问题，注意三个属性都相同时需要去重。然后惊奇的发现结构体居然需要自定义！=。omg
讲真分值的时候直接归并常数小好多啊。
直接无脑sort：4816ms 归并排序：1144ms
那就扔归并的代码了：
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int n,k,f[201000],fna[101000];
struct node
{
int s,c,m,ans,num;
friend bool operator!= (node x,node y)
{return (x.s==y.s)?((x.c==y.c)?x.m!=y.m:true):true;}
}a[101000],b[101000];
bool cmp1(node x,node y) {return (x.s==y.s)?((x.c==y.c)?x.m<y.m:x.c<y.c):x.s<y.s;}
void fix(int x,int y){while(x<=k) f[x]+=y,x+=-x&x;}
int query(int x){int re=0; while(x>0) re+=f[x],x-=-x&x; return re;}
void clear(int x){while(x<=k) f[x]=0,x+=-x&x;}
void solve(int l,int r)
{
if(l==r) {return ;}
int mid=l+r>>1,h1=l,h2=mid+1;
solve(l,mid); solve(mid+1,r);
for(int i=l;i<=r;++i)
{
if(h2>r||(h1<=mid&&a[h1].c<=a[h2].c)) fix(a[h1].m,a[h1].num),b[i]=a[h1++];
else a[h2].ans+=query(a[h2].m),b[i]=a[h2++];
}
for(int i=l;i<=mid;++i) clear(a[i].m);
for(int i=l;i<=r;++i) a[i]=b[i];
}
int main()
{
scanf("%d%d",&n,&k); int i,cc=n;
for(i=1;i<=n;++i)
scanf("%d%d%d",&a[i].s,&a[i].c,&a[i].m);
sort(a+1,a+n+1,cmp1);
int cnt=0,now=1;
a[++cnt]=a[1];
for(i=2;i<=n;++i)
{
if(a[i]!=a[i-1]) a[++cnt]=a[i],a[cnt-1].num=now,now=1;
else now++;
}
a[cnt].num=now; n=cnt;
solve(1,n);
for(i=1;i<=n;++i)
fna[a[i].ans+a[i].num-1]+=a[i].num;
for(i=0;i!=cc;++i)
printf("%d\n",fna[i]);
return 0;
}