題目鏈接：http://poj.org/problem?id=2352 既然題目中說Y坐標是升序給出，那么只需要維護到當前結點的小于X的值，這樣很快能求出來所有的等級，然后就balabalabala……
  view code
1 #include <iostream>
2 #include <cstdio>
3 #include <cstdlib>
4 #include <cstring>
5 #include <cmath>
6 #include <algorithm>
7 using namespace std;
8 #define lson l, m, rt << 1
9 #define rson m + 1, r, rt << 1 | 1
10 const int maxn = 32010;
11 int sum[maxn << 2], ans[15010];
12 void PushUp(int rt){
13 sum[rt] = sum[rt << 1] + sum[rt << 1 | 1];
14 }
15 void build(int l, int r, int rt){
16 sum[rt] = 0;
17 if (l == r) return;
18 int m = (l + r) >> 1;
19 build(lson);
20 build(rson);
21 PushUp(rt);
22 }
23 void update(int x, int l, int r, int rt){
24 if (l == r){
25 sum[rt] += 1;
26 return;
27 }
28 int m = (l + r) >> 1;
29 if (x <= m) update(x, lson);
30 else update(x, rson);
31 PushUp(rt);
32 }
33 int query(int ll, int rr, int l, int r, int rt){
34 if (ll <= l && rr >= r) return sum[rt];
35 int m = (l + r) >> 1;
36 int ret = 0;
37 if (ll <= m) ret += query(ll, rr, lson);
38 if (rr > m) ret += query(ll, rr, rson);
39 return ret;
40 }
41 int main(){
42 int n;
43 while (~scanf("%d", &n)){
44 build(0, maxn, 1);
45 int x, y;
46 for (int i = 0; i < n; i++){
47 scanf("%d%d", &x, &y);
48 int cnt = query(0, x, 0, maxn, 1);
49 ans[cnt] += 1;
50 update(x, 0, maxn, 1);
51 }
52 for (int i = 0; i < n; i++) printf("%d\n", ans[i]);
53 }
54 return 0;
55
|