题目链接：https://vjudge.net/problem/HYSBZ-3262
3262: 陌上花开
Time Limit: 20 Sec Memory Limit: 256 MBSubmit: 3188 Solved: 1472
[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
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
1
3
0
1
0
1
0
0
1
HINT
Source
题解：
单纯的三维偏序问题，上CDQ分治。
代码如下：
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <algorithm> 5 #include <vector> 6 #include <cmath> 7 #include <queue> 8 #include <stack> 9 #include <map> 10 #include <string> 11 #include <set> 12 using namespace std; 13 typedef long long LL; 14 const int INF = 2e9; 15 const LL LNF = 9e18; 16 const int MOD = 1e9+7; 17 const int MAXN = 2e5+100; 18 19 struct node 20 { 21 int x, y, z, s, id; 22 bool operator<(const node& b)const{ 23 if(x==b.x){ 24 if(y==b.y) return z<b.z; 25 return y<b.y; 26 } 27 return x<b.x; 28 } 29 }; 30 node a[MAXN], b[MAXN]; 31 32 int n, k, c[MAXN]; 33 int lowbit(int x) {return x&(-x);} 34 void add(int x, int val) {for(int i=x;i<=k;i+=lowbit(i)) c[i]+=val;} 35 int sum(int x) {int ret=0; for(int i=x;i>0;i-=lowbit(i))ret+=c[i]; return ret;} 36 37 // 第一维排序，第二维CDQ，第三维树状数组 38 void CDQ(int l, int r) 39 { 40 if(l==r) return; 41 42 int mid = (l+r)/2; 43 CDQ(l, mid); CDQ(mid+1, r); 44 int p1 = l, p2 = mid+1; 45 for(int i = l; i<=r; i++) //按y排序，归并排序 46 { 47 //必须是：a[p1].y<=a[p2].y，不能少了==这个判断，因为当a[p1].y==a[p2].y时，必定p1排在前面，因为p1的z比p2小 48 if(p2>r||(p1<=mid&&a[p1].y<=a[p2].y)) b[i] = a[p1++]; 49 else b[i] = a[p2++]; 50 } 51 //此时y按从小到大排序，当y相等时，x小的排前面。 52 for(int i = l; i<=r; i++) 53 { 54 a[i] = b[i]; //b为a归并排序时的临时存储，应把值放回到a里 55 if(a[i].id<=mid) add(a[i].z, 1); //当x小于等于mid，则把它的z加入到树状数组中，被别人统计 56 else a[i].s += sum(a[i].z); //当x大于mid时，拿自己的z到线段树中统计 57 } 58 for(int i = l; i<=r; i++) //撤回在线段树中的操作 59 if(a[i].id<=mid) add(a[i].z, -1); 60 } 61 62 int ans[MAXN]; 63 int main() 64 { 65 while(scanf("%d%d", &n,&k)!=EOF) 66 { 67 for(int i = 1; i<=n; i++) 68 { 69 scanf("%d%d%d", &a[i].x,&a[i].y,&a[i].z); 70 a[i].s = 0; 71 } 72 sort(a+1,a+1+n); 73 memset(c, 0, sizeof(c)); 74 for(int i = 1; i<=n; i++) 75 a[i].id = i; 76 CDQ(1,n); 77 78 memset(ans, 0, sizeof(ans)); 79 for(int i = n-1; i>=1; i--) //一样的点，选值最大的 80 if(a[i].x==a[i+1].x&&a[i].y==a[i+1].y&&a[i].z==a[i+1].z) 81 a[i].s = a[i+1].s; 82 83 for(int i = 1; i<=n; i++) 84 ans[a[i].s]++; 85 for(int i = 0; i<n; i++) 86 printf("%d ", ans[i]); 87 } 88 }