http://acm.pku.edu.cn/JudgeOnline/problem?id=2352題目給出平面上N個(gè)點(diǎn)，對(duì)于某點(diǎn)p，如果有k個(gè)點(diǎn)的橫坐標(biāo)小于等于Xp，并且縱坐標(biāo)小于等于Yp，那么稱這個(gè)點(diǎn)p的level是k，問(wèn)level為0~n-1的點(diǎn)分別有多少個(gè)。
比較直觀的樹狀數(shù)組的題目，首先對(duì)X坐標(biāo)升序排序，如果X坐標(biāo)相同，則按Y坐標(biāo)升序排序，然后對(duì)于每一個(gè)點(diǎn)，首先在樹狀數(shù)組里面查詢前面比它的Y坐標(biāo)小的點(diǎn)的個(gè)數(shù)，然后再把這個(gè)點(diǎn)插入到樹狀數(shù)組中即可。復(fù)雜度是O(nlgm)，n是點(diǎn)數(shù)，m是坐標(biāo)的范圍。
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, 0, sizeof(cnt));
44 memset(c, 0, sizeof(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