hdu Stars（树状数组）

 1 #include <iostream>
 2 #include <string>
 3 #include <cstring>
 4 #include <queue>
 5 #include <vector>
 6 #include <cstdio>
 7 #define lowbit(x) ((x)&(-(x)))
 8 using namespace std;
 9 const int maxn=15007;
10 const int maxx=32002;
11 int bit[maxx],level[maxn];
12 int n;
13 void add(int pos,int delt)
14 {
15     for(int i=pos;i<=maxx;i+=lowbit(i))
16         bit[i]+=delt;
17 }
18 
19 int sum(int pos)
20 {
21     int re=0;
22     for(int i=pos;i>0;i-=lowbit(i))
23     {
24         re+=bit[i];
25     }
26     return re;
27 }
28 
29 int main()
30 {
31     while(scanf("%d",&n)==1)
32     {
33         memset(bit,0,sizeof(bit));
34         memset(level,0,sizeof(level));
35         for(int i=1;i<=n;i++)
36         {
37             int x,y;
38             scanf("%d%d",&x,&y);
39             level[sum(x+1)]++;
40             add(x+1,1);
41         }
42         for(int i=0;i<n;i++)
43             printf("%d\n",level[i]);
44     }
45     return 0;
46 }