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菊苣代码长大的
1/* ***********************************************
2Author :111qqz
3Created Time :2017年10月10日 星期二 18时35分53秒
4File Name :3262.cpp
5************************************************ */
6
7#include <cstdio>
8#include <cstring>
9#include <iostream>
10#include <algorithm>
11#include <vector>
12#include <queue>
13#include <set>
14#include <map>
15#include <string>
16#include <cmath>
17#include <cstdlib>
18#include <ctime>
19#define PB push_back
20#define fst first
21#define sec second
22#define lson l,m,rt<<1
23#define rson m+1,r,rt<<1|1
24#define ms(a,x) memset(a,x,sizeof(a))
25typedef long long LL;
26#define pi pair < int ,int >
27#define MP make_pair
28
29using namespace std;
30const double eps = 1E-8;
31const int dx4[4]={1,0,0,-1};
32const int dy4[4]={0,-1,1,0};
33const int inf = 0x3f3f3f3f;
34const int N=1E5+7;
35const int M=2E5+7;
36int n,k;
37int ans[N];
38struct Point
39{
40 int x,y,z;
41 int cnt,sum;
42 bool operator < ( const Point &b)const
43 {
44 if (x!=b.x) return x<b.x;
45 if (y!=b.y) return y<b.y;
46 return z<b.z;
47 }
48 bool operator == (const Point &p)const
49 {
50 return x==p.x&&y==p.y&&z==p.z;
51 }
52}p[N];
53struct BIT
54{
55 int n,t[M];
56 void init(int _n)
57 {
58 n=_n;
59 ms(t,0);
60 }
61 int lowbit( int x){ return x&(-x);}
62 void update( int x,int delta)
63 {
64 for ( int i = x ; i <= n ; i+=lowbit(i))
65 t[i]+=delta;
66 }
67 int Sum( int x)
68 {
69 int ret = 0;
70 for ( int i = x ; i >=1 ; i-=lowbit(i)) ret+=t[i];
71 return ret;
72 }
73}bit;
74bool cmpcdq(Point a,Point b) { return a.y<b.y;}
75void cdq( int l,int r)
76{
77 if (l==r) return;
78 int mid = (l+r)>>1;
79 cdq(l,mid);
80 cdq(mid+1,r);
81 sort(p+l,p+mid+1,cmpcdq);
82 sort(p+mid+1,p+r+1,cmpcdq);
83 int j = l;
84 for ( int i = mid+1 ; i <= r ; i++)
85 {
86 for ( ; j <= mid && p[j].y<=p[i].y ; j++) bit.update(p[j].z,p[j].cnt);
87 p[i].sum+=bit.Sum(p[i].z);
88 }
89 for ( int i = l ; i < j ; i++) bit.update(p[i].z,-p[i].cnt);
90}
91int tot=0;
92int main()
93{
94 #ifndef ONLINE_JUDGE
95 freopen("./in.txt","r",stdin);
96 #endif
97 scanf("%d%d",&n,&k);
98 bit.init(k);
99 for ( int i = 1; i <= n ; i++) scanf("%d%d%d",&p[i].x,&p[i].y,&p[i].z);
100 sort(p+1,p+n+1);//先去重
101 int cnt = 0 ;
102 for ( int i = 1 ; i <= n ; i++)
103 {
104 cnt++;
105 if ( !(p[i]==p[i+1]))
106 {
107 p[++tot]=p[i];
108 p[tot].cnt = cnt;
109 cnt = 0;
110 }
111 }
112 cdq(1,tot);
113 for ( int i = 1; i <= tot ; i++) ans[p[i].sum+p[i].cnt-1]+=p[i].cnt; //因为全相等也算大于，-1是减去自己
114 for ( int i = 0 ; i < n ; i++) printf("%d\n",ans[i]);
115 #ifndef ONLINE_JUDGE
116 fclose(stdin);
117 #endif
118 return 0;
119}