hdu 1698 Just a Hook

#include <bits/stdc++.h>
using namespace std;
const int maxn=1e5+7;
typedef long long ll;
int sum[maxn<<2],lazy[maxn<<2];

void build(int i,int l,int r)
{
    lazy[i]=1;
    if(l==r){
        sum[l]=1;
        return ;
    }
    int mid=(l+r)>>1;
    build(i<<1,l,mid);
    build(i<<1|1,mid+1,r);
    sum[i]=sum[i<<1]+sum[i<<1|1];
}

void pushdown(int i,int len)
{
    if(lazy[i]){
        lazy[i<<1]=lazy[i];
        lazy[i<<1|1]=lazy[i];
        sum[i<<1]=lazy[i]*(len-(len>>1));
        sum[i<<1|1]=lazy[i]*(len>>1);
        lazy[i]=0;
    }
}
void update(int i,int l,int r,int val,int L,int R)
{
    if(l>=L&&r<=R){
        lazy[i]=val;
        sum[i]=val*(r-l+1);
        return ;
    }
    pushdown(i,(r-l+1));
    int mid=(l+r)>>1;
    if(L<=mid) update(i<<1,l,mid,val,L,R);
    if(R>mid) update(i<<1|1,mid+1,r,val,L,R);
    sum[i]=sum[i<<1]+sum[i<<1|1];
}

int query(int i,int l,int r,int L,int R)
{
    if(l>=L&&r<=R){
        return sum[i];
    }
    pushdown(i,(r-l+1));
    int mid=(l+r)>>1;
    int ans=0;
    if(L<=mid) ans+=query(i<<1,l,mid,L,R);
    else if(R>mid) ans+=query(i<<1|1,mid+1,r,L,R);
    return ans;
}
int main()
{
    int t;
    int cas=1;
    scanf("%d",&t);
    while(t--){
        int n,m;
        scanf("%d%d",&n,&m);
        memset(sum,0,sizeof(sum));
        memset(lazy,0,sizeof(lazy));
        build(1,1,n);
        for(int i=0;i<m;i++){
            int a,b,c;
            scanf("%d%d%d",&a,&b,&c);
            update(1,1,n,c,a,b);
        }
        printf("Case %d: The total value of the hook is %d.\n",cas++,query(1,1,n,1,n));
    }
    return 0;
}
/*
1
10
2
1 5 2
5 9 3
*/