线段树 模板

http://acm.hdu.edu.cn/showproblem.php?pid=1698 

模板!

#include<cstdio>
#include<cstring>
#include<iostream>
typedef long long int ll;
using namespace std; 
ll sum[400004];
ll lazy[400004];
// 中间值统一靠左 
void pushup(int cr){
    sum[cr]=sum[cr*2]+sum[2*cr+1];
}
void pushdown(int cr,int ln,int rn){  
    if(lazy[cr]){
        lazy[cr<<1]=lazy[cr];
        lazy[cr<<1|1]=lazy[cr];        
        sum[cr<<1]=lazy[cr]*ln;
        sum[cr<<1|1]=lazy[cr]*rn;
    }
    lazy[cr]=0;
}
void update(int l,int r,ll val,int L,int R,int cr){    
    int m=(L+R)/2;     
    if(L==l && r==R){
        sum[cr]=( (r-l+1)*val );
        lazy[cr]=val;
        return ;
    }
    pushdown(cr,m-L+1,R-m);
    if(l<=m) update(l,min(r,m),val,L,m,cr*2);
    if(r>=m+1) update(max(m+1,l),r,val,m+1,R,cr*2+1);
    if(R!=L)
        pushup(cr);
}
void build(int l,int r,int cr){   
    if(l==r){
        sum[cr]=1;
        return;
    }
    int mid= (l+r)/2;
    build(l,mid,2*cr);
    build(mid+1,r,2*cr+1);
    pushup(cr);
}
ll query(int l,int r,int L,int R,int cr){

    if(l==L&&r==R){
        return sum[cr];
    }
    else{
        ll ans=0;
        int m=(L+R)/2;
        pushdown(cr,m-L+1,R-m);
        if(l<=m) {    
            ans+=query(l,min(r,m),L,m,cr*2);    
        }
        if(r>=m+1){
            ans+=query( max(l,m+1),r,m+1,R,cr*2+1 );
        } 
        return ans;
    }
}
int main(){
    int t;
    scanf("%d",&t);
    for(int j=1;j<=t;j++){
        int n,op;
        scanf("%d%d",&n,&op);
        memset(sum,0,sizeof(sum));
        memset(lazy,0,sizeof(lazy));
        build(1,n,1); 
        for(int i=0;i<op;i++){
            int l,r,val;
            scanf("%d%d%d",&l,&r,&val);
            update(l,r,val,1,n,1);            
        }
        printf("Case %d: The total value of the hook is %lld.
",j,query(1,n,1,n,1) );
    }
}