hdu1698 线段树 区间更改 区间求和

题目传送 hdu1698

//#include<bits/stdc++.h>
#include<cstdio>
#include<iostream>
#include<cstring> //memset函数头文件
using namespace std;
const int maxn=1e5+5;
int lazy[maxn*4]; //注意数据范围是否需要longlong之类
int sum[maxn*4];
void build(int l,int r,int root){
    if(l==r){
        sum[root]=1;
        return ;
    }
    int mid=(l+r)>>1;
    build(l,mid,root<<1);
    build(mid+1,r,root<<1|1);
    sum[root]=sum[root<<1]+sum[root<<1|1];
}
void pushdown(int l,int r,int root){
    if(lazy[root]){
        lazy[root<<1]=lazy[root<<1|1]=lazy[root];
        int mid=(l+r)>>1;
        sum[root<<1]=(mid-l+1)*lazy[root];
        sum[root<<1|1]=(r-mid)*lazy[root];
        lazy[root]=0;
    }   
}
void updt(int L,int R,int flag,int l,int r,int root){
    if(L<=l&&R>=r){
        lazy[root]=flag;
        sum[root]=(r-l+1)*flag;
        return;
    }
    else{
        int mid=(l+r)>>1;
        pushdown(l,r,root);
        if(L<=mid)updt(L,R,flag,l,mid,root<<1);
        if(R>=mid+1)updt(L,R,flag,mid+1,r,root<<1|1);
        sum[root]=sum[root<<1]+sum[root<<1|1];
    }
}
int main(){
    int T,N,n;
    int stx,sty,data;
    scanf("%d",&T);
    for(int k=1;k<=T;k++){
        scanf("%d",&N);
        memset(lazy,0,sizeof(lazy));
        build(1,N,1);
        scanf("%d",&n);
        for(int i=1;i<=n;i++){                    
            scanf("%d%d%d",&stx,&sty,&data);
            updt(stx,sty,data,1,N,1);
        }
        //输出k,手残输出T,疯狂wa
        printf("Case %d: The total value of the hook is %d.\n",k,sum[1]);
    }
    return 0;
}