HDU3698(线段树区间维护)

#include"cstdio"
using namespace std;
const int MAXN=100005;
struct node{
    int l,r;
    int lazy,sum;
}a[MAXN*4];
void build(int rt,int l,int r)
{
    a[rt].l=l;
    a[rt].r=r;
    a[rt].lazy=0;
    if(l==r)
    {
        a[rt].sum=1;
        return ;
    }
    int mid=(l+r)>>1;
    build(rt<<1,l,mid);
    build((rt<<1)|1,mid+1,r);
    a[rt].sum=a[rt<<1].sum+a[(rt<<1)|1].sum;
}

void pushDown(int rt)
{
    int mid=(a[rt].l+a[rt].r)>>1;
    a[rt<<1].lazy=a[(rt<<1)|1].lazy=a[rt].lazy;
    a[rt<<1].sum=a[rt].lazy*(mid-a[rt].l+1);
    a[(rt<<1)|1].sum=a[rt].lazy*(a[rt].r-mid);
    a[rt].lazy=0;
}

void update(int rt,int l,int r,int val)
{
    if(a[rt].l==l&&a[rt].r==r)
    {
        a[rt].lazy=val;
        a[rt].sum=val*(r-l+1);
        return ;
    }
    
    if(a[rt].lazy)    pushDown(rt);
    
    int mid=(a[rt].l+a[rt].r)>>1;
    
    if(r<=mid)    update(rt<<1,l,r,val);
    else if(mid<l)    update((rt<<1)|1,l,r,val);
    else
    {
        update(rt<<1,l,mid,val);
        update((rt<<1)|1,mid+1,r,val);
    }
    a[rt].sum=a[rt<<1].sum+a[(rt<<1)|1].sum;
}

int main()
{
    int t;
    scanf("%d",&t);
    for(int cas=1;cas<=t;cas++)
    {
        int n,m;
        scanf("%d%d",&n,&m);
        build(1,1,n);
        while(m--)
        {
            int x,y,v;
            scanf("%d%d%d",&x,&y,&v);
            update(1,x,y,v);
        }
        printf("Case %d: The total value of the hook is %d.\n",cas,a[1].sum);
    }    
}