Description

有n朵花,每朵花有三个属性:花形(s)、颜色(c)、气味(m),用三个整数表示。

现在要对每朵花评级,一朵花的级别是它拥有的美丽能超过的花的数量。

定义一朵花A比另一朵花B要美丽,当且仅Sa>=Sb,Ca>=Cb,Ma>=Mb。

显然,两朵花可能有同样的属性。需要统计出评出每个等级的花的数量。

Input

第一行为N,K (1 <= N <= 100,000, 1 <= K <= 200,000 ), 分别表示花的数量和最大属性值。

以下N行，每行三个整数si, ci, mi (1 <= si, ci, mi <= K)，表示第i朵花的属性

Output

包含N行，分别表示评级为0...N-1的每级花的数量。

Sample Input

10 3

3 3 3

2 3 3

2 3 1

3 1 1

3 1 2

1 3 1

1 1 2

1 2 2

1 3 2

1 2 1

Sample Output

3

1

3

0

1

0

1

0

0

1

Solution

三维偏序

对于三维偏序，我的套路是CDQ加BIT

这道题其实很裸，但是它的同样的点的处理很烦

需要去重，并且记录下每个不相同的点出现的次数，把这个东西变成权值在CDQ中加入BIT

调死了，最后都是照着别人的代码调出来的

#include<bits/stdc++.h>

#define ll long long

#define db double

#define ld long double

#define Mid ((l+r)>>1)

const int MAXN=200000+10,MAXM=300000+10,base=233,Mod=1e9+7;

int n,m,ans[MAXN];

struct node{

	int x,y,z,ans,w;

	inline bool operator == (const node &A) const {

		return x==A.x&&y==A.y&&z==A.z;

	};

};

node point[MAXN],tmp[MAXN];

struct BIT{

	int C[MAXM];

	inline void init()

	{

		memset(C,0,sizeof(C));

	}

	inline int lowbit(int x)

	{

		return x&(-x);

	}

	inline void add(int x,int k)

	{

		while(x<=m)

		{

			C[x]+=k;

			x+=lowbit(x);

		}

	}

	inline int sum(int x)

	{

		int res=0;

		while(x)

		{

			res+=C[x];

			x-=lowbit(x);

		}

		return res;

	}

};

BIT T;

template<typename T> inline void read(T &x)

{

	T data=0,w=1;

	char ch=0;

	while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();

	if(ch=='-')w=-1,ch=getchar();

	while(ch>='0'&&ch<='9')data=((T)data<<3)+((T)data<<1)+(ch^'0'),ch=getchar();

	x=data*w;

}

template<typename T> inline void write(T x,char c='\0')

{

	if(x<0)putchar('-'),x=-x;

	if(x>9)write(x/10);

	putchar(x%10+'0');

	if(c!='\0')putchar(c);

}

template<typename T> inline void chkmin(T &x,T y){x=(y<x?y:x);}

template<typename T> inline void chkmax(T &x,T y){x=(y>x?y:x);}

template<typename T> inline T min(T x,T y){return x<y?x:y;}

template<typename T> inline T max(T x,T y){return x>y?x:y;}

inline bool cmp1(node a,node b)

{

	return a.x<b.x||(a.x==b.x&&a.y<b.y)||(a.x==b.x&&a.y==b.y&&a.z<b.z);

}

inline bool cmp2(node a,node b)

{

	return a.y<b.y||(a.y==b.y&&a.z<b.z);

}

inline void CDQ(int l,int r)

{

	if(l==r)return ;

	CDQ(l,Mid);CDQ(Mid+1,r);

	std::sort(point+l,point+Mid+1,cmp2);

	std::sort(point+Mid+1,point+r+1,cmp2);

	int j=l;

	for(register int i=Mid+1;i<=r;++i)

	{

		while(point[j].y<=point[i].y&&j<=Mid)T.add(point[j].z,point[j].w),++j;

		point[i].ans+=T.sum(point[i].z);

	}

	for(register int i=l;i<j;++i)T.add(point[i].z,-point[i].w);

}

int main()

{

	read(n);read(m);

	for(register int i=1;i<=n;++i)read(tmp[i].x),read(tmp[i].y),read(tmp[i].z);

	std::sort(tmp+1,tmp+n+1,cmp1);

	int pn=0;

	for(register int i=1,now=1;i<=n;++i,++now)

		if(!(tmp[i]==tmp[i+1]))point[++pn]=tmp[i],point[pn].w=now,now=0;

	T.init();

	CDQ(1,pn);

	for(register int i=1;i<=pn;++i)ans[point[i].ans+point[i].w-1]+=point[i].w;

	for(register int i=0;i<n;++i)write(ans[i],'\n');

	return 0;

}