有n朵花,每朵花有三个属性:花形(s)、颜色(c)、气味(m),用三个整数表示。
现在要对每朵花评级,一朵花的级别是它拥有的美丽能超过的花的数量。
定义一朵花A比另一朵花B要美丽,当且仅Sa>=Sb,Ca>=Cb,Ma>=Mb。
显然,两朵花可能有同样的属性。需要统计出评出每个等级的花的数量。
包含N行，分别表示评级为0...N-1的每级花的数量。
三维偏序模板题。套路：第一维排序，第二维cdq，第三维树状数组。cdq的具体方法类似于归并排序，将左区间和右区间递归处理。把左右区间按第二维排序，双指针扫描，当右区间i一定时，在左边扫j，当第二维还满足条件时，在值域树状数组上找到j第三维的值，加上相同类型j的个数。当第二维j超过i时，在树状数组上查询小于等于i第三维的j的个数，更新答案。最后一定要把树状数组还原。
1 #include<iostream> 2 #include<cstdio> 3 #include<algorithm> 4 using namespace std; 5 6 int n, k, num[200005]; 7 8 struct node { 9 int a, b, c, w, ans; 10 } qwq[100005], qaq[100005]; 11 12 bool cmp1 ( node a, node b ) { 13 if ( a.a == b.a ) { 14 if ( a.b == b.b ) return a.c < b.c; 15 return a.b < b.b; 16 } 17 return a.a < b.a; 18 } 19 20 bool cmp2 ( node a, node b ) { 21 if ( a.b == b.b ) return a.c < b.c; 22 return a.b < b.b; 23 } 24 25 int lowbit ( int x ) { 26 return x & -x; 27 } 28 29 int pre[200005]; 30 31 void add ( int x, int d ) { 32 for ( int i = x; i <= k; i += lowbit ( i ) ) 33 pre[i] += d; 34 } 35 36 int query ( int x ) { 37 int ans = 0; 38 for ( int i = x; i; i -= lowbit ( i ) ) 39 ans += pre[i]; 40 return ans; 41 } 42 43 void CDQ ( int l, int r ) { 44 if ( l == r ) return ; 45 int mid = ( l + r ) >> 1; 46 CDQ ( l, mid ); CDQ ( mid + 1, r ); 47 int i = mid + 1, j = l; 48 sort ( qaq + l, qaq + mid + 1, cmp2 ); 49 sort ( qaq + mid + 1, qaq + r + 1, cmp2 ); 50 for ( ; i <= r; i ++ ) { 51 while ( qaq[j].b <= qaq[i].b && j <= mid ) { 52 add ( qaq[j].c, qaq[j].w ); j ++; 53 } 54 qaq[i].ans += query ( qaq[i].c ); 55 } 56 for ( i = l; i < j; i ++ ) add ( qaq[i].c, -qaq[i].w ); 57 } 58 59 int main ( ) { 60 //freopen ( "testdata.in", "r", stdin ); 61 //freopen ( "a.out", "w", stdout ); 62 scanf ( "%d%d", &n, &k ); 63 for ( int i = 1; i <= n; i ++ ) 64 scanf ( "%d%d%d", &qwq[i].a, &qwq[i].b, &qwq[i].c ); 65 sort ( qwq + 1, qwq + 1 + n, cmp1 ); 66 int cnt = 0, sum = 0; 67 for ( int i = 1; i <= n; i ++ ) { 68 cnt ++; 69 if ( qwq[i].a != qwq[i+1].a || qwq[i].b != qwq[i+1].b || qwq[i].c != qwq[i+1].c ) { 70 qaq[++sum] = qwq[i]; 71 qaq[sum].w = cnt; 72 cnt = 0; 73 } 74 } 75 CDQ ( 1, sum ); 76 for ( int i = 1; i <= sum; i ++ ) num[qaq[i].ans + qaq[i].w - 1] += qaq[i].w; 77 for ( int i = 0; i < n; i ++ ) printf ( "%d\n", num[i] ); 78 return 0; 79 }
原文：https://www.cnblogs.com/wans-caesar-02111007/p/9489921.html