bzoj 3262: 陌上花开

3262: 陌上花开

Time Limit: 20 Sec Memory Limit: 256 MB
Submit: 5800 Solved: 2804
[Submit][Status][Discuss]
Description
有n朵花,每朵花有三个属性:花形(s)、颜色©、气味(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

比较明显的三维偏序，于是我们可以考虑使用cdq分治解决，吊打树套树。

因为题目要求我们找等级对应的个数，所以我们需要先去重，因为相同的统计答案时会有问题，因为求个数。

我们先用cdq分治求每朵花的偏序值，然后最后统计次数。

AC代码：

#pragma GCC optimize(2)
#include<bits/stdc++.h>
//#define int long long
#define lowbit(x) (x&(-x))
using namespace std;
const int N=100010;
int n,k,a[N<<1],m=200010,res[N],idx;
struct node{
	int s,c,m,res,cnt;
	node(){
		res=0;	cnt=1;
	}
}t[N],q[N];
bool operator == (const node &s1,const node &s2){
	return (s1.s==s2.s&&s1.c==s2.c&&s1.m==s2.m);
}
bool cmps(const node &s1,const node &s2){
	return (s1.s==s2.s&&s1.c==s2.c)?(s1.m<s2.m):(s1.s==s2.s?s1.c<s2.c:s1.s<s2.s);
}
bool cmpc(const node &s1,const node &s2){
	return (s1.c==s2.c)?(s1.m<s2.m):(s1.c<s2.c);
}
inline void add(int x,int v){
	for(int i=x;i<=m;i+=lowbit(i))	a[i]+=v;
}
inline int ask(int x){
	int res=0;	for(int i=x;i;i-=lowbit(i))	res+=a[i];	return res;
}
void cdq(int l,int r){
	if(l==r)	return ;	int mid=l+r>>1;
	cdq(l,mid);	cdq(mid+1,r);
	int j=l;
	for(int i=mid+1;i<=r;i++){
		while(j<=mid&&t[j].c<=t[i].c)	add(t[j].m,t[j].cnt),j++;
		t[i].res+=ask(t[i].m);
	}
	for(int i=l;i<j;i++)	add(t[i].m,-t[i].cnt);
	sort(t+l,t+r+1,cmpc);
}
signed main(){
	scanf("%d %d",&n,&k);
	for(int i=1;i<=n;i++)
		scanf("%d %d %d",&q[i].s,&q[i].c,&q[i].m);
	sort(q+1,q+1+n,cmps);
	for(int i=1;i<=n;i++){
		if(i<n&&q[i]==q[i+1])	q[i+1].cnt+=q[i].cnt;
		else	t[++idx]=q[i];
	}
	cdq(1,idx);
	for(int i=1;i<=idx;i++)	res[t[i].res+t[i].cnt-1]+=t[i].cnt;
	for(int i=0;i<n;i++)	printf("%d\n",res[i]);
	return 0;
}