HDU 1556 color the ball

树状数组，插段问点

有一行气球，

给出n个区间，

每次对区间内的每个气球涂一次色，

问最后每个气球各涂了多少次。

 1 #include<cstdio>
 2 #include<cstring>
 3 const int MAXN=100000+5;
 4 int c[MAXN];
 5 int n;
 6 int lowbit(int x)
 7 {
 8     return x&(-x);
 9 }
10 void update(int x,int num)
11 {
12     while(x>0){
13         c[x]+=num;
14         x-=lowbit(x);
15     }
16 }
17 int sum(int x)
18 {
19     int temp=0;
20     while(x<=n){
21         temp+=c[x];
22         x+=lowbit(x);
23     }
24     return temp;
25 }
26 
27 int main()
28 {
29     while(scanf("%d",&n)){
30         if(!n)
31             break;
32         memset(c,0,sizeof(c));
33         int a,b;
34         for(int i=1;i<=n;i++){
35             scanf("%d%d",&a,&b);
36             update(b,1);
37             update(a-1,-1);
38         }
39         for(int i=1;i<n;i++){
40             printf("%d ",sum(i));
41         }
42         printf("%d
",sum(n));
43     }
44     return 0;
45 }

hdu1556