hdu1698 Just a Hook（成段替换 lazy标记）

成段替换  lazy标记

题意：成段覆盖染色，求颜色值的总和。

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
#define lson l,m,rt<<1          //函数用左儿子
#define rson m+1,r,rt<<1|1      //函数用右儿子
#define havemid int m=(l+r)>>1  //取节点中点
#define left (rt<<1)            //左儿子
#define right (rt<<1|1)         //右儿子
const int maxn=100005;          //最大节点个数
int sum[maxn<<2];               //节点个数，开maxn的4倍
int col[maxn<<2];               //lazy 标记
void pushup(int rt){
    sum[rt]=sum[left]+sum[right];
}
void pushdown(int rt,int len){
    if(col[rt]){                           //被标记了
        col[left]=col[right]=col[rt];      //标记向下传
        sum[left]=(len-(len>>1))*col[rt];  //左儿子更新 
        sum[right]=(len>>1)*col[rt];       //右
        col[rt]=0;                         //置标记为0 
    }
}
void build(int l,int r,int rt){
    col[rt]=0;
    if(l==r){
        sum[rt]=1;return ;
    }
    havemid;
    build(lson);
    build(rson);
    pushup(rt);
}
void update(int L,int R,int c,int l,int r,int rt){
    if(L<=l&&r<=R){
        col[rt]=c;
        sum[rt]=c*(r-l+1);
        return ;
    }
    pushdown(rt,r-l+1);         //先看有没有标记
    havemid;
    if(L<=m)update(L,R,c,lson);
    if(R>m)update(L,R,c,rson);
    pushup(rt);                
}
int main()
{
    int T,n,Q,ca=1,a,b,c;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d",&n);
        build(1,n,1);
        scanf("%d",&Q);
        while(Q--)
        {
            scanf("%d%d%d",&a,&b,&c);
            update(a,b,c,1,n,1);
        }
        printf("Case %d: The total value of the hook is %d.\n",ca++ , sum[1]);
    }
    return 0;
}