hdu1556Colortheball(树状数组)

1 //390MS 1020K 720 B C&＃43;&＃43;
2 //树状数组模板题&＃xff0c;还有O(n)的简单算法&＃xff0c;这里不贴。
3 #include
4 #include<string.h>
5 #define N 100005
6 int c[N],d[N];
7 int lowbit(int k)
8 {
9 return (-k)&k;
10 }
11 int getsum(int k)
12 {
13 int sum&＃61;0;
14 while(k<N){
15 sum&＃43;&＃61;c[k];
16 k&＃43;&＃61;lowbit(k);
17 }
18 return sum;
19 }
20 void update(int k,int detal)
21 {
22 while(k>0){
23 c[k]&＃43;&＃61;detal;
24 k-&＃61;lowbit(k);
25 }
26 }
27 int main(void)
28 {
29 int n,a,b;
30 while(scanf("%d",&n),n)
31 {
32 memset(c,0,sizeof(c));
33 memset(d,0,sizeof(d));
34 for(int i&＃61;0;i){
35 scanf("%d%d",&a,&b);
36 update(b,1);
37 update(a-1,-1);
38 }
39 for(int i&＃61;1;i<&＃61;n;i&＃43;&＃43;)
40 printf(i&＃61;&＃61;n?"%d\n":"%d ",getsum(i));
41 }
42 return 0;
43 }