HDU 1541 Stars 树状数组

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