http://acm.pku.edu.cn/JudgeOnline/problem?id=2352

题目给出平面上N个点,对于某点p,如果有k个点的横坐标小于等于Xp,并且纵坐标小于等于Yp,那么称这个点p的level是k,问level为0~n-1的点分别有多少个。
比较直观的树状数组的题目,首先对X坐标升序排序,如果X坐标相同,则按Y坐标升序排序,然后对于每一个点,首先在树状数组里面查询前面比它的Y坐标小的点的个数,然后再把这个点插入到树状数组中即可。复杂度是O(nlgm),n是点数,m是坐标的范围。

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <algorithm>
 4 
 5 using namespace std;
 6 
 7 const int MAX_N = 15010;
 8 const int MAX_C = 32010;
 9 
10 struct point {
11     int x, y;
12     bool operator < (const point &p) const {
13         return x < p.x || x == p.x && y < p.y;
14     }
15 }a[MAX_N];
16 
17 int c[MAX_C];
18 int cnt[MAX_N];
19 int n;
20 
21 inline int lowbit(int x) {
22     return x & (-x);
23 }
24 
25 void modify(int pos, int x) {
26     while (pos < MAX_C) {
27         c[pos] += x;
28         pos += lowbit(pos);
29     }
30 }
31 
32 int sum(int end) {
33     int sum = 0;
34     while (end) {
35         sum += c[end];
36         end -= lowbit(end);
37     }
38     return sum;
39 }
40 
41 int main() {
42     while (scanf("%d"&n) != EOF) {
43         memset(cnt, 0sizeof(cnt));
44         memset(c, 0sizeof(c));
45         for (int i = 0; i < n; ++i) {
46             scanf("%d%d"&a[i].x, &a[i].y);
47             ++a[i].x; ++a[i].y;
48         }
49         sort(a, a + n);
50         for (int i = 0; i < n; ++i) {
51             ++cnt[sum(a[i].y)];
52             modify(a[i].y, 1);
53         }
54         for (int i = 0; i < n; ++i) printf("%d\n", cnt[i]);
55     }
56     return 0;
57 }
58