题目描述：有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; }