セグメントツリー(区間更新)hdu-1698-Just a Hook

タイトルリンク:
http://acm.hdu.edu.cn/showproblem.php?pid=1698
 
タイトル:
n個の棒があって、それぞれの棒はすべて1つの値があって、q個は更新して、毎回更新する時3つのパラメータx,y,zは表して、x-y区間内の棒の値をzに変えて、最後のすべての棒の値の総和はいくらです.
 
問題解決の考え方:
nサイズの線分ツリーを作成し、sum[rt]でノード区間の値の総和を表し、value[rt]で区間が現在置かれている状態を表し、非ゼロであれば区間内のすべての棒がこの値であり、伝わっていないことを示し、ゼロであれば、区間内の状態が変わったことを示します.更新が完了するたびに当該区間のsum値を求め(アップデート)、最後にsum[1]を出力すればよい.
キー:更新遅延は、更新のたびにリーフノードに更新されるのではなく、記録状態などは次回更新時に更新されますが、毎回トップレベルのsum値を求めます.
 
詳細は、コードを参照してください.

#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<string>
#include<cstring>
#include<algorithm>
#include<vector>
#include<map>
#include<stack>
#include<list>
#include<queue>
#define eps 1e-6
#define INF (1<<30)
#define PI acos(-1.0)
using namespace std;

#define lson l,m,rt<<1
#define rson m+1,r,(rt<<1)|1
#define maxn 110000
int sum[maxn*4],value[maxn*4]; //                 

/*
freopen("data.in","r",stdin);
freopen("data.out","w",stdout);
*/

void pushup(int rt)
{
    sum[rt]=sum[rt<<1]+sum[rt<<1|1];
    return ;
}

void build(int l,int r,int rt)
{
    value[rt]=0; //     
    sum[rt]=1;//    ，     1

    if(l==r)
        return ;
    int m=(l+r)>>1;

    build(lson);
    build(rson);
    pushup(rt);
    return ;
}

void pushdown(int rt,int num) //   ,num          
{
    if(value[rt])
    {
        value[rt<<1]=value[rt<<1|1]=value[rt];
        sum[rt<<1]=(num-(num>>1))*value[rt];  //              ，              
        sum[rt<<1|1]=(num>>1)*value[rt];
        value[rt]=0;//          ，       
    }
    return ;
}

void update(int L,int R,int v,int l,int r,int rt)
{
    if(L<=l&&R>=r)  //              ，       ，  
    {
        value[rt]=v;
        sum[rt]=v*(r-l+1);
        return ;
    }
    //         ，    ，        
    pushdown(rt,r-l+1);

    int m=(l+r)>>1;

    if(L<=m)
        update(L,R,v,lson);//      
    if(R>m)
        update(L,R,v,rson);//      
    pushup(rt); //   
    return ;
}


int main()
{
    int ca,n,q;

    scanf("%d",&ca);
    for(int k=1;k<=ca;k++)
    {
        scanf("%d%d",&n,&q);
        build(1,n,1);
        while(q--)
        {
            int a,b,c;

            scanf("%d%d%d",&a,&b,&c);
            update(a,b,c,1,n,1);
        }
        printf("Case %d: The total value of the hook is %d.
",k,sum[1]);

    }
    return 0;
}