HDU 1556 Color the ball (线段树|树状数组，区间更新)

链接：

http://acm.hdu.edu.cn/showproblem.php?pid=1556

题目：

Problem Description

N个气球排成一排，从左到右依次编号为1,2,3....N.每次给定2个整数a b(a <= b),lele便为骑上他的“小飞鸽"牌电动车从气球a开始到气球b依次给每个气球涂一次颜色。但是N次以后lele已经忘记了第I个气球已经涂过几次颜色了，你能帮他算出每个气球被涂过几次颜色吗？

Input

每个测试实例第一行为一个整数N,(N <= 100000).接下来的N行，每行包括2个整数a b(1 <= a <= b <= N)。
当N = 0，输入结束。

Output

每个测试实例输出一行，包括N个整数，第I个数代表第I个气球总共被涂色的次数。

分析与总结：

很基本的成段更新，单点查询， 这题用线段树或者树状数组都可以做。

代码：

1. 树状数组

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;

typedef long long int64;
const int MAXN  = 100005;
int64 C[MAXN];
int n;

inline int lowbit(int x){return x&(-x);}

int64 sum(int x){
    int64 ret=0;
    while(x > 0){
        ret += C[x];
        x -= lowbit(x);
    }
    return ret;
}
void add(int x,int val){
    while(x <= n) {
        C[x] += val;
        x += lowbit(x);
    }
}

int main(){
    int a,b;
    while(~scanf("%d",&n) && n){
        memset(C, 0, sizeof(C));
        for(int i=0; i<n; ++i){
            scanf("%d%d",&a,&b);
            add(a,1);
            add(b+1,-1);
        }
        for(int i=1; i<=n; ++i){
            if(i==1)printf("%lld",C[i]);
            else printf(" %lld",sum(i));
        }
        puts("");
    }
    return 0;
}

2. 线段树

#include<iostream>
#include<cstdio>
#include<cstring>
#define mem(str,x) memset(str,(x),sizeof(str))
#define mid  ((left+right)>>1)
#define len  (right-left+1)
#define lson rt<<1, left, m
#define rson rt<<1|1, m+1, right
using namespace std;
const int MAXN = 100005;
int sum[MAXN<<2],col[MAXN<<2],n;

inline void push_up(int rt){
    sum[rt] = sum[rt<<1] + sum[rt<<1|1];
}
inline void push_down(int rt, int _len){
    if(col[rt]){
        int l=rt<<1, r=rt<<1|1, m=_len>>1;
        col[l] += col[rt];
        col[r] += col[rt];
        sum[l] += (_len-m) * col[rt];
        sum[r] += m * col[rt];
        col[rt] = 0;
    }
}
void update(int rt,int left,int right,int l,int r){
    if(l<=left && right<=r){
        ++col[rt];
        sum[rt] += len;
        return;
    }
    push_down(rt,len);
    int m = mid;
    if(l <= m) update(lson,l,r);
    if(r > m) update(rson,l,r);
    push_up(rt);
}
int query(int rt,int left,int right,int l,int r){
    if(left==l && right==r) return sum[rt];
    int m = mid;
    push_down(rt,len);
    if(r <= m) return query(lson, l, r);
    else if(l > m) return query(rson,l,r);
    else return query(lson,l,m) + query(rson,m+1,r);
}

int main(){
    int a,b;
    while(~scanf("%d",&n) && n) {
        mem(sum,0); mem(col,0);
        for(int i=0; i<n; ++i){
            scanf("%d%d",&a,&b);
            update(1,1,n,a,b);
        }
        for(int i=1; i<=n; ++i){
            if(i==1) printf("%d",query(1,1,n,i,i));
            else printf(" %d",query(1,1,n,i,i));
        }
        puts("");
    }
    return 0;
}

—— 生命的意义，在于赋予它意义士。

原创http://blog.csdn.net/shuangde800，By D_Double (转载请标明)