【BZOJ3262】陌上花开

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

HINT

1 <= N <= 100,000, 1 <= K <= 200,000

题解：先按第一维排序；然后cdq分治，具体做法是将整个区间[l,r]分成[l,mid]和[mid+1,r]，然后递归处理左右两半，这样我们就只需要求出有多少跨过mid的关系了。这个我们一边分治一边将第二维归并排序，然后将第三维扔到树状数组里，顺便再树状数组里统计一下答案

注意本题需要判重，即如果两朵花所有属性都相等，那么它们都比对方美丽

珍爱生命，远离memset

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <iostream>

using namespace std;

const int maxn=100010;

struct node

{

	int x,y,z;

}s[maxn];

int s1[maxn],s2[maxn],ss[maxn],ans[maxn],tr[maxn<<1],p[maxn],q[maxn],sta[maxn];

int n,m,nn;

bool cmp(node a,node b)

{

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

	if(a.x==b.x)	return a.y<b.y;

	return a.x<b.x;

}

void updata(int a,int v)

{

	for(int i=a;i<=m;i+=i&-i)	tr[i]+=v;

}

int query(int a)

{

	int i,ret=0;

	for(i=a;i;i-=i&-i)	ret+=tr[i];

	return ret;

}

void dfs(int l,int r)

{

	if(l==r)

	{

		p[l]=l;

		return ;

	}

	int i,mid=l+r>>1,h1=l,h2=mid+1;

	dfs(l,mid),dfs(mid+1,r);

	for(i=l;i<=r;i++)

	{

		if(h2<=r&&(h1>mid||s1[p[h1]]>s1[p[h2]]))	ans[p[h2]]+=query(s2[p[h2]]),q[i]=p[h2++];

		else	updata(s2[p[h1]],ss[p[h1]]),q[i]=p[h1++];

	}

	for(i=l;i<=mid;i++)	updata(s2[i],-ss[i]);

	for(i=l;i<=r;i++)	p[i]=q[i];

}

int main()

{

	scanf("%d%d",&n,&m);

	int i;

	for(i=1;i<=n;i++)	scanf("%d%d%d",&s[i].x,&s[i].y,&s[i].z);

	sort(s+1,s+n+1,cmp);

	for(i=1;i<=n;i++)

	{

		if(s[i].x!=s[i-1].x||s[i].y!=s[i-1].y||s[i].z!=s[i-1].z)	s1[++nn]=s[i].y,s2[nn]=s[i].z;

		ss[nn]++;

	}

	dfs(1,nn);

	for(i=1;i<=nn;i++)	sta[ans[i]+ss[i]-1]+=ss[i];

	for(i=0;i<n;i++)	printf("%d\n",sta[i]);

	return 0;

}

巴特西

【BZOJ3262】陌上花开 cdq分治