欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

bzoj 3262 :陌上花开 (cdq分治 三维偏序)

程序员文章站 2022-05-14 18:56:27
...

题目描述:有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的每级花的数量。

裸的三维偏向问题,但是花的属性可能相同,显然相同的花答案是一样的,将它们离散化缩点聚在一起即可,最后答案加上这种花的数量。

#include<bits/stdc++.h>
using namespace std;
const int maxn = 3e5 + 10;
#define lowbit(i) (i & (-i))
struct node {
	int s,c,m,id,cnt;
}q[maxn],tmp[maxn];
int sum[maxn],n,k,top;
int ans[maxn];
int vis[maxn];
bool cmp(node a,node b) {
	if(a.s == b.s) {
		if(a.c == b.c) return a.m < b.m;
		return a.c < b.c;
	}
	return a.s < b.s;
}
int cal(node a,node b) {
	if(a.s < b.s) return -1;
	else if(a.s > b.s) return 1;
	else if(a.s == b.s) {
		if(a.c < b.c) return -2;
		else if(a.c > b.c) return 2;
		else if(a.c == b.c) {
			if(a.m < b.m) return -3;
			else if(a.m > b.m) return 3;
			else if(a.m == b.m) return 0;
		}
	}
}
int getsum(int p) {
	int ans = 0;
	for(; p; p -= lowbit(p)) ans += sum[p];
	return ans;
}
void modify(int p,int v) {
	for(; p <= k; p += lowbit(p)) sum[p] += v;
}
void cdq(int l,int r) {
	if(l == r) return;
	int mid = l + r >> 1;
	cdq(l,mid);cdq(mid + 1,r);
	top = 0;
	for(int i = l,j = mid + 1; i <= mid || j <= r;) {
		if(i <= mid && (j > r || q[i].c <= q[j].c)) {
			modify(q[i].m,q[i].cnt);
			tmp[++top] = q[i++];
		}
		else {
			ans[q[j].id] += getsum(q[j].m);
			tmp[++top] = q[j++];
		}
	}
	for(int i = l; i <= mid; i++)
		modify(q[i].m,-q[i].cnt);
	for(int i = l; i <= r; i++) 
		q[i] = tmp[i - l + 1];
}
int 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 + n + 1,cmp);
	int tot = 0;
	for(int i = 1; i <= n; i++) {
		if(tot && cal(q[i],q[tot]) == 0) {
			q[tot].cnt++;
		}
		else {
			q[++tot] = q[i];
			q[tot].id = tot;
			q[tot].cnt = 1;
		}
	}
	cdq(1,tot);
	for(int i = 1; i <= tot; i++) {
		ans[q[i].id] += q[i].cnt - 1;
	}
	for(int i = 1;i <= tot; i++) {
		vis[ans[q[i].id]] += q[i].cnt;
	}
	for(int i = 0; i < n; i++) 
		printf("%d\n",vis[i]);	
	return 0;
}
相关标签: cdq分治