HDU 1556 Color the ball(线段树区间更新)

Color the ball

我真的该认真的复习一下以前没懂的知识了,今天看了一下线段树,以前只会用模板,现在看懂了之后,发现还有这么多巧妙的地方,好厉害啊所以就应该尽量搞懂弄明白每个知识点

【题目类型】线段树区间更新

&题意：

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

&题解：

线段树区间更新模板题

【时间复杂度】(O(nlogn))

&代码：

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int maxn=1e5+5;
typedef long long ll;
int N;
int seg[maxn<<2];
int add[maxn<<2];

//在build 和 updata时需要向上更新
//query时不需要
inline void puup(int no)
{
    seg[no]+=seg[no<<1]+seg[no<<1|1];
}

//这题不需要建树 因为都是0
void build(int no,int b,int e)
{
    if (b==e){
        seg[no]=0;
        return ;
    }
    int m=b+e>>1;
    build(no<<1,b,m);
    build(no<<1|1,m+1,e);
    puup(no);
}

//query 和 updata时都要向下更新
void pudown(int no,int len)
{
    if (add[no]){
        //注意都是 +=
        add[no<<1]+=add[no];
        add[no<<1|1]+=add[no];
        //这seg节点里存的是与add相乘
        seg[no<<1]+=add[no]*(len-len/2);
        //左儿子存多的 右儿子存少的 可以自己弄一个奇数区间试一下
        seg[no<<1|1]+=add[no]*(len/2);
        add[no]=0;
    }
}

int query(int no,int b,int e,int l,int r)
{
    //第一种情况 在[l,r]中间
    if (l<=b&&e<=r){
        return seg[no];
    }
    int m=b+e>>1;
    pudown(no,e-b+1);
    ll re=0;
    //第二种情况 在疯狂的两个区间中
    if (l<=m)
        re+=query(no<<1,b,m,l,r);
    if (m<r)
        re+=query(no<<1|1,m+1,e,l,r);
    return re;
}

void updata(int no,int b,int e,int l,int r,int xx)
{
    //第一种情况 在[l,r]中间
    if (l<=b&&e<=r){
        add[no]+=xx;
        seg[no]+=e-b+1;
        return ;
    }
    pudown(no,e-b+1);
    int m=b+e>>1;
    //第二种情况 在疯狂的两个区间中
    if (l<=m)
        updata(no<<1,b,m,l,r,xx);
    if (m<r)
        updata(no<<1|1,m+1,e,l,r,xx);
    puup(no);
}

int main()
{
    while(cin>>N){
        if (N==0) break;
        //别忘初始化
        memset(seg,0,sizeof(seg));
        memset(add,0,sizeof(add));
//        build(1,1,N);
        for(int i=0;i<N;i++){
            int u,v;
            cin>>u>>v;
            updata(1,1,N,u,v,1);
        }
        for(int i=1;i<=N;i++){
            printf("%d%c",query(1,1,N,i,i),i==N?'
':' ');
        }
    }
    return 0;
}