Stars(树状数组)

 1 #include <stdio.h>
 2 const int N=32001;
 3 int n,c[N],level[N];
 4 int lowbit(int x)
 5 {
 6     return x&(-x);
 7 }
 8 int sum(int x)//求和
 9 {
10     int s = 0;
11     while(x>0)
12     {
13         s += c[x];
14         x -= lowbit(x);
15     }
16     return s;
17 }
18 void update(int pos)//更新
19 {
20     while(pos <= N)
21     {
22         c[pos]++;
23         pos += lowbit(pos);
24     }
25 }
26 int main()
27 {
28     int x,y;
29     scanf("%d",&n);
30     for (int i = 1; i <= n; i++)
31     {
32         scanf("%d %d",&x,&y);
33         level[sum(x+1)]++;//树状数组的下标从一开始，故所有横坐标右移一位，相对位置不变
34         update(x+1);
35     }
36     for (int i = 0; i < n; i++)
37         printf("%d\n",level[i]);
38     return 0;
39 }