bzoj 3262: 陌上花开（cdq分治）

3262: 陌上花开

Time Limit: 20 Sec   Memory Limit: 256 MB Submit: 2433   Solved: 1087 [ Submit][ Status][ Discuss]

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

模板题，cdq分治可以看http://blog.csdn.net/jaihk662/article/details/77720577

不过有两个地方不一样

①若干朵完全一样的花当成一朵再分治，因为属性一样算做互相超过

③若是x排序，y树状数组，z用cdq分治，一定要先将z离散化，因为它不是1-n的全排列

#include<stdio.h> #include<algorithm> using namespace std; int k, tre[200005]; typedef struct Res { int x, y, z, ans, sum; bool operator < (const Res &b) const { if(x<b.x || x==b.x && y<b.y || x==b.x && y==b.y && z<b.z) return 1; return 0; } }Res; Res s[200005], L[100005], R[100005]; int ans[200005]; bool comp(Res a, Res b) { if(a.z<b.z || a.z==b.z && a.y<b.y || a.z==b.z && a.y==b.y && a.x<b.x) return 1; return 0; } void Update(int x, int val) { while(x<=k) { tre[x] += val; x += x&-x; } } int Query(int x) { int ans = 0; while(x) { ans += tre[x]; x -= x&-x; } return ans; } void Cdq(int l, int r) { int i, p, q, m; if(l==r) return; m = (l+r)/2; for(i=l;i<=r;i++) { if(s[i].z<=m) Update(s[i].y, s[i].sum); else s[i].ans += Query(s[i].y); } for(i=l;i<=r;i++) { if(s[i].z<=m) Update(s[i].y, -s[i].sum); } p = q = 0; for(i=l;i<=r;i++) { if(s[i].z<=m) L[++p] = s[i]; else R[++q] = s[i]; } for(i=l;i<=m;i++) s[i] = L[i-(l-1)]; for(i=m+1;i<=r;i++) s[i] = R[i-m]; Cdq(l, m); Cdq(m+1, r); } int main(void) { int i, n, cnt; scanf("%d%d", &n, &k); for(i=1;i<=n;i++) { scanf("%d%d%d", &s[i].x, &s[i].y, &s[i].z); s[i].sum = 1; } sort(s+1, s+n+1); cnt = 0; 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) { s[cnt].sum++; continue; } s[++cnt] = s[i]; } sort(s+1, s+cnt+1, comp); for(i=1;i<=cnt;i++) s[i].z = i; sort(s+1, s+cnt+1); Cdq(1, cnt); for(i=1;i<=cnt;i++) { s[i].ans += s[i].sum-1; ans[s[i].ans] += s[i].sum; } for(i=0;i<=n-1;i++) printf("%d\n", ans[i]); return 0; }