HDOJ1698 Just a hook【线段树---成段更新---lazy标志】

/*
1
10
2
1 5 2
5 9 3
*/
#include <stdio.h>
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define maxn 111111
int sum[maxn<<2],lazy[maxn<<2];
void PullUp(int rt)//上拉
{
    sum[rt]=sum[rt<<1]+sum[rt<<1|1];
}
void PushDown(int rt,int len)//下推
{
    lazy[rt<<1]=lazy[rt<<1|1]=lazy[rt];
    sum[rt<<1]=lazy[rt]*(len-(len>>1));
    sum[rt<<1|1]=lazy[rt]*(len>>1);
    lazy[rt]=0;
}
void build(int l,int r,int rt)
{
    int m=(l+r)>>1;
    lazy[rt]=0;
    if(l==r){
        sum[rt]=1;
        return;
    }
    build(lson);
    build(rson);
    PullUp(rt);
}
void update(int z,int L,int R,int l,int r,int rt)
{
    int m=(l+r)>>1;
    if(l>=L&&r<=R){//当前区间是更新区间的子集，则一定要更新
        lazy[rt]=z;//标记
        sum[rt]=(r-l+1)*z;//更新当前区间
        return;
    }
    if(lazy[rt])PushDown(rt,r-l+1);//延迟标记下传一层
    if(L<=m)    update(z,L,R,lson);//左子树上有一部分
    if(R>m)        update(z,L,R,rson);//右子树上有一部分
    PullUp(rt);//上推
}
int main()
{
    int t,n,q,x,y,z,i;
    scanf("%d",&t);
    for (i=1;i<=t;i++){
        scanf("%d",&n);
        build(1,n,1);
        scanf("%d",&q);
        while (q--){
            scanf("%d%d%d",&x,&y,&z);
            update(z,x,y,1,n,1);
        }
        printf("Case %d: The total value of the hook is %d.\n",i,sum[1]);
    }
    return 0;
}