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?'\n':' ');

        }

    }

    return 0;

}