BZOJ 3262: 陌上花开 (cdq分治模板题，三维偏序)
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
HINT
1 <= N <= 100,000, 1 <= K <= 200,000
思路：
第一发cdq分治，果然很好写。
题目很裸，好像没什么好分析的。
代码风格的话，我是看lwt菊苣代码长大的
/* ***********************************************
Author :111qqz
Created Time :2017年10月10日 星期二 18时35分53秒
File Name :3262.cpp
************************************************ */
1#include <cstdio>
2#include <cstring>
3#include <iostream>
4#include <algorithm>
5#include <vector>
6#include <queue>
7#include <set>
8#include <map>
9#include <string>
10#include <cmath>
11#include <cstdlib>
12#include <ctime>
13#define PB push_back
14#define fst first
15#define sec second
16#define lson l,m,rt<<1
17#define rson m+1,r,rt<<1|1
18#define ms(a,x) memset(a,x,sizeof(a))
19typedef long long LL;
20#define pi pair < int ,int >
21#define MP make_pair
1using namespace std;
2const double eps = 1E-8;
3const int dx4[4]={1,0,0,-1};
4const int dy4[4]={0,-1,1,0};
5const int inf = 0x3f3f3f3f;
6const int N=1E5+7;
7const int M=2E5+7;
8int n,k;
9int ans[N];
10struct Point
11{
12 int x,y,z;
13 int cnt,sum;
14 bool operator < ( const Point &b)const
15 {
16 if (x!=b.x) return x<b.x;
17 if (y!=b.y) return y<b.y;
18 return z<b.z;
19 }
20 bool operator == (const Point &p)const
21 {
22 return x==p.x&&y==p.y&&z==p.z;
23 }
24}p[N];
25struct BIT
26{
27 int n,t[M];
28 void init(int _n)
29 {
30 n=_n;
31 ms(t,0);
32 }
33 int lowbit( int x){ return x&(-x);}
34 void update( int x,int delta)
35 {
36 for ( int i = x ; i <= n ; i+=lowbit(i))
37 t[i]+=delta;
38 }
39 int Sum( int x)
40 {
41 int ret = 0;
42 for ( int i = x ; i >=1 ; i-=lowbit(i)) ret+=t[i];
43 return ret;
44 }
45}bit;
46bool cmpcdq(Point a,Point b) { return a.y<b.y;}
47void cdq( int l,int r)
48{
49 if (l==r) return;
50 int mid = (l+r)>>1;
51 cdq(l,mid);
52 cdq(mid+1,r);
53 sort(p+l,p+mid+1,cmpcdq);
54 sort(p+mid+1,p+r+1,cmpcdq);
55 int j = l;
56 for ( int i = mid+1 ; i <= r ; i++)
57 {
58 for ( ; j <= mid && p[j].y<=p[i].y ; j++) bit.update(p[j].z,p[j].cnt);
59 p[i].sum+=bit.Sum(p[i].z);
60 }
61 for ( int i = l ; i < j ; i++) bit.update(p[i].z,-p[i].cnt);
62}
63int tot=0;
64int main()
65{
66 #ifndef ONLINE_JUDGE
67 freopen("./in.txt","r",stdin);
68 #endif
69 scanf("%d%d",&n,&k);
70 bit.init(k);
71 for ( int i = 1; i <= n ; i++) scanf("%d%d%d",&p[i].x,&p[i].y,&p[i].z);
72 sort(p+1,p+n+1);//先去重
73 int cnt = 0 ;
74 for ( int i = 1 ; i <= n ; i++)
75 {
76 cnt++;
77 if ( !(p[i]==p[i+1]))
78 {
79 p[++tot]=p[i];
80 p[tot].cnt = cnt;
81 cnt = 0;
82 }
83 }
84 cdq(1,tot);
85 for ( int i = 1; i <= tot ; i++) ans[p[i].sum+p[i].cnt-1]+=p[i].cnt; //因为全相等也算大于，-1是减去自己
86 for ( int i = 0 ; i < n ; i++) printf("%d\n",ans[i]);
87 #ifndef ONLINE_JUDGE
88 fclose(stdin);
89 #endif
90 return 0;
91}