POJ2352 Stars

　　线段树，单点更新，区间查询，200+ms。

View Code

 1 #include <stdio.h>
 2 #include <string.h>
 3 #define lson (cur << 1)
 4 #define rson (cur << 1 | 1)
 5 #define N 32005
 6 
 7 int tree[N << 2], ans[15001];
 8 
 9 void pushup(int cur)
10 {
11     tree[cur] = tree[lson] + tree[rson];
12 }
13 
14 void insert(int cur, int l, int r, int x)
15 {
16     if(l == r)
17     {
18         tree[cur] ++;
19         return ;
20     }
21     int mid = (l + r) >> 1;
22     if(mid >= x)
23         insert(lson, l, mid, x);
24     else
25         insert(rson, mid + 1, r, x);
26     pushup(cur);
27 }
28 
29 void query(int cur, int l, int r, int s, int t, int &lv)
30 {
31     if(l >= s && r <= t)
32     {
33         lv += tree[cur];
34         return ;
35     }
36     int mid = (l + r) >> 1;
37     if(mid >= s)
38         query(lson, l, mid, s, t, lv);
39     if(mid + 1 <= t)
40         query(rson, mid + 1, r, s, t, lv);
41 }
42 
43 int main()
44 {
45     int n, i, x, y, lv;
46     scanf("%d", &n);
47     for(i = 0; i < n; i ++)
48     {
49         scanf("%d%d", &x, &y);
50         lv = 0;
51         query(1, 1, N, 1, x + 1, lv);
52         ans[lv] ++;
53         insert(1, 1, N, x + 1);
54     }
55     for(i = 0; i < n; i ++)
56     {
57         printf("%d\n", ans[i]);
58     }
59     return 0;
60 }

　　树状数组，140+ms。

View Code

 1 #include <cstdio>
 2 #include <cstring>
 3 #define N 15005
 4 #define M 32005
 5 int a[N], c[M];
 6 
 7 int lowbit(int x)
 8 {
 9     return x & (-x);
10 }
11 
12 void update(int v)
13 {
14     while(v < M)
15     {
16         c[v] ++;
17         v += lowbit(v);
18     }
19 }
20 
21 int sum(int v)
22 {
23     int ans = 0;
24     while(v)
25     {
26         ans += c[v];
27         v -= lowbit(v);
28     }
29     return ans;
30 }
31 
32 int main()
33 {
34     int n, i, x, y;
35     scanf("%d", &n);
36     for(i = 0; i < n; i ++)
37     {
38         scanf("%d%d", &x, &y);
39         ++ x;
40         a[sum(x)] ++;
41         update(x);
42     }
43     for(i = 0; i < n; i ++)
44         printf("%d\n", a[i]);
45     return 0;
46 }