HDU 1556 Color the ball

Color the ball

Time Limit: 9000/3000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 27513 Accepted Submission(s): 13359

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个气球总共被涂色的次数。

Sample Input

Sample Output

1 1 1
3 2 1

分析：线段树模板题，跟着题意走就好。

#include <iostream>
#include <string>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
#include <deque>
#include <map>
#define range(i,a,b) for(auto i=a;i<=b;++i)
#define LL long long
#define itrange(i,a,b) for(auto i=a;i!=b;++i)
#define rerange(i,a,b) for(auto i=a;i>=b;--i)
#define fill(arr,tmp) memset(arr,tmp,sizeof(arr))
using namespace std;
template <class T>
class segtree{
private:
    T* add,*sum;
    void pushup(int rt){
        sum[rt]=sum[rt<<1]+sum[rt<<1|1];
    }
    void pushdown(int rt,int m){
        if(add[rt]){
            add[rt<<1]+=add[rt];
            add[rt<<1|1]+=add[rt];
            sum[rt<<1]+=add[rt]*(m-(m>>1));
            sum[rt<<1|1]+=add[rt]*(m>>1);
            add[rt]=0;
        }
    }
public:
    explicit segtree(int len=int(1e5+5)){
        add=new T[len<<2];
        sum=new T[len<<2];
        fill(add,0);fill(sum,0);
    }
    void build(int l,int r,int rt=1){
        add[rt]=0;
        if(l==r){
            sum[rt]=0;
            return;
        }
        int m=(l+r)>>1;
        build(l,m,rt<<1);
        build(m+1,r,rt<<1|1);
        pushup(rt);
    }
    void update(int L,int R,T c,int l,int r,int rt=1){
        if(L<=l&&r<=R){
            add[rt]+=c;
            sum[rt]+=c*(r-l+1);
            return;
        }
        pushdown(rt,r-l+1);
        int m=(l+r)>>1;
        if(L<=m)update(L,R,c,l,m,rt<<1);
        if(m<R)update(L,R,c,m+1,r,rt<<1|1);
        pushup(rt);
    }
    T query(int L,int R,int l,int r,int rt=1){
        if(L<=l&&r<=R)return sum[rt];
        pushdown(rt,r-l+1);
        int m=(l+r)>>1;
        T ret=0;
        if(L<=m)ret+=query(L,R,l,m,rt<<1);
        if(m<R)ret+=query(L,R,m+1,r,rt<<1|1);
        return ret;
    }
};
segtree<int>tree;
int n,a,b;
void init(){

}
void solve(){
    while(cin>>n,n){
        tree.build(1,n);
        range(i,1,n){
            cin>>a>>b;
            tree.update(a,b,1,1,n);
        }
        range(i,1,n){
            int ans=tree.query(i,i,1,n);
            cout<<ans<<(i==n?'
':' ');
        }
    }
}
int main() {
    init();
    solve();
    return 0;
}

View Code