学步园

题目链接:  
http://acm.hdu.edu.cn/showproblem.php?pid=1698

题目大意:   给出初试值都为1的区间[1,n]

                  有M次操作，每次操作表示将[a,b]的值全部替换成c

                  最后输出总值的大小

解题思路:  线段树的区间更新，区间查询

                 这道题是线段树从点更新到区间更新的过渡题

                 用到lazy的思想，把每次只更新到[a,b]区间，而不会继续往下更新

                 什么时候再往下更新呢？等下一次查询或者更新到[a,b]区间之间时再把上次标记的更新

                 更新时间复杂度O(logN)，查询时间复杂度O(logN)

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX 100100
#define MID(a,b) (a+b)>>1
#define L(a) a<<1
#define R(a) (a<<1|1)
typedef struct{
    int left,right;
    int sum,add;    //add是lazy的标记
}Node;
Node Tree[MAX<<2];

void Build(int t,int l,int r)      //以1根结点建立线段树[l,r]
{
    Tree[t].left=l,Tree[t].right=r;
    if(Tree[t].left==Tree[t].right)
    {
        Tree[t].add=0;      //初始化为0
        Tree[t].sum=1;
        return ;
    }
    int mid=MID(Tree[t].left,Tree[t].right);
    Build(L(t),l,mid);
    Build(R(t),mid+1,r);
}

void Insert(int t,int l,int r,int m)  //向以t为根结点，l为左子树，r为右子树的结点插入m
{
    if(Tree[t].left==l&&Tree[t].right==r)
    {
        Tree[t].add=m;       //每次到区间就更新lazy,并且退出
        Tree[t].sum=(r-l+1)*m;
        return ;
    }
    int mid=MID(Tree[t].left,Tree[t].right);
    if(Tree[t].add!=0)       //如果此结点有上次未更新的lazy，则继续往下更新
    {
        Tree[L(t)].sum=(Tree[L(t)].right-Tree[L(t)].left+1)*Tree[t].add;
        Tree[R(t)].sum=(Tree[R(t)].right-Tree[R(t)].left+1)*Tree[t].add;
        Tree[L(t)].add=Tree[t].add;   //往下更新
        Tree[R(t)].add=Tree[t].add;   //往下更新
        Tree[t].add=0;      //标记此lazy以更新
    }
    if(l>mid)
    {
        Insert(R(t),l,r,m);
    }
    else if(r<=mid)
    {
        Insert(L(t),l,r,m);
    }
    else
    {
        Insert(L(t),l,mid,m);
        Insert(R(t),mid+1,r,m);
    }
    Tree[t].sum=Tree[L(t)].sum+Tree[R(t)].sum;  //结点的值=左子树的值+右子树的值
}

int main()
{
    int i1,i,n,m,a,b,c,t;
    scanf("%d",&t);
    for(i1=1;i1<=t;i1++)
    {
        memset(Tree,0,sizeof(Tree));
        scanf("%d%d",&n,&m);
        Build(1,1,n);
        for(i=1;i<=m;i++)
        {
            scanf("%d%d%d",&a,&b,&c);
            Insert(1,a,b,c);
        }
        printf("Case %d: The total value of the hook is %d.\n",i1,Tree[1].sum);
    }
    return 0;
}

注：原创文章，转载请注明出处