HDU 1556 Color the ball - c++编程基础

#include  
#include  
int a[100005];  
int main(){  
    int n,x,y,i;  
    while(scanf("%d",&n)!=EOF){  
    memset(a,0,sizeof(a));  
    if(n==0)break;  
    for(i=1;i<=n;i++){  
        scanf("%d%d",&x,&y);  
        a[x]++;a[y+1]--;  
    }  
    for(i=2;i<=n;i++)  
        a[i]+=a[i-1];  
    for(i=1;i<=n;i++){  
        if(i==1)  
            printf("%d",a[i]);  
        else  
        printf(" %d",a[i]);  
    }  
    printf("\n");  
    }  
    return 0;  
}

但是毕竟是在学树状数组、所以还是用树状数组再次AC之、

#include  
#include  
int sum[100005];  
int n;  
int lowbit(int x){  
    return x&(-x);  
}  
int getsum(int x){  
    int s=0;  
    while(x>




0){  
        s+=sum[x];  
        x-=lowbit(x);  
    }  
    return s;  
}  
void update(int x,int num){  
    while(x<=n){  
        sum[x]+=num;  
        x+=lowbit(x);  
    }  
}  
int main(){  
    int i,x,y;  
    while(scanf("%d",&n)!=EOF){  
        if(n==0)break;  
        memset(sum,0,sizeof(sum));  
        for(i=1;i<=n;i++){  
            scanf("%d%d",&x,&y);  
            update(x,1);  
            update(y+1,-1);  
        }  
        for(i=1;i<=n;i++){  
            printf("%d",getsum(i));  
            if(i