学步园

线段树区间更新 lazy操作

#include <cstring>
#include <iostream>
#include <cstdio>
using namespace std;
#define Lson l,m,rt<<1
#define Rson m+1,r,rt<<1|1
int const MAXN = 100010;
struct TREE{
    int l,r;
    int v,add;
}tree[MAXN<<2];
inline int Max(int a,int b){
    return a>b?a:b;
}
inline void PushUp(int rt){
    tree[rt].v = tree[rt<<1].v + tree[rt<<1|1].v;
}
inline void PushDown(int rt,int m){
    /*
    m = R - L + 1
    右子 区间为 L/2 + R/2 + 1  R
    所以有 R - R / 2 - L / 2 - 1 + 1= (R - L)/2 个元素
    1 / 2 = 0;
    (R - L )/2 = m / 2;
    所以左边 m - m /2 
    */
    if(tree[rt].add){
        tree[rt<<1].add = tree[rt].add;
        tree[rt<<1|1].add = tree[rt].add;
        tree[rt<<1|1].v = tree[rt].add * (m>>1);
        tree[rt<<1].v = tree[rt].add * (m - (m>>1));
        tree[rt].add = 0;
    }
}
void Build(int l,int r,int rt){
    tree[rt].v = 1;
    tree[rt].add = 0;
    if(l == r) return ;
    int m = (l + r)>>1;
    Build(Lson);
    Build(Rson);
    PushUp(rt);
}
void Update(int s,int L,int R,int l,int r,int rt){
    if(L <=l && r <= R){
        tree[rt].add = s;
        tree[rt].v = s * (r - l + 1);
        return ;
    }
    PushDown(rt,r - l + 1);
    int m = (l + r)>>1;
    if(L <= m) Update(s,L,R,Lson);
    if(R > m) Update(s,L,R,Rson);
    PushUp(rt);
}
int main(){
    int t;
    while(~scanf("%d",&t)){
        for(int k = 1;k <= t;k++){
            int n,q;
            scanf("%d",&n);
            Build(1,n,1);
            scanf("%d",&q);
            while(q--){
                int x,y,z;
                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",k,tree[1].v);
        }
    }
    return 0;
}