hdu 1698 Just a Hook(线段树 成段更新+总区间求和)

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

题意：给定一根棒的长度，它上面有价值1,2,3种，初始价值为1，每次输入的x,y,z表示把区间[x,y]的价值全部变为z；问最后这根棒的总价值是多少。

思路：与书中对某一线段[x,y]同时加上z类似，只不过这个是把线段[x,y]变成z。

属于线段树成段更新问题。。成段更新与单点更新就不同了。成段更新没必要更新到单个点，当找到要更新的区间时直接更新这一整个区间返回即可，若上面没有返回，就要传递属性，即把该区间的价值属性传递给左右儿子，并且把该区间的价值属性设为-1，标志它已把价值传递给左右子树了。这是比较重要的一点。

当计算总区间的和时，区间的价值是很重要的一点，若它的价值是正值（1,2,3,），直接计算该区间之和返回即可，但若是-1，说明更新时它已把价值传递给左右子树，这时要递归左右子树求区间之和。

（本人的一点理解，还有待改善）

#include <stdio.h>
#include <string.h>

const int maxn = 100005;


struct line
{
    int l;
    int r;
    int col;	//标记该区间的价值属性（1,2,3）
}tree[4*maxn];

void build(int v, int l, int r)
{
    tree[v].l = l;
    tree[v].r = r;
    tree[v].col = 1;	//初始化为1
    if(l == r)
        return;

    int mid = (l+r)>>1;
    build(v*2,l,mid);
    build(v*2+1,mid+1,r);
}
//更新区间[l,r]上的价值属性为z,v是当前待检验区间
void update(int v, int l, int r, int z)
{
    if(tree[v].l >= l && tree[v].r <= r)
    //如果当前区间是要更改价值的区间的子区间，那么直接把当前区间价值属性改为z并结束
    {
        tree[v].col = z;
        return;
    }

    if(tree[v].col != -1)//若上面没走掉，把其价值传递到左右子树，并把它本身的价值设为-1，表示它的价值已经向下传递
    {
        tree[v*2].col = tree[v].col;
        tree[v*2+1].col = tree[v].col;
        tree[v].col = -1;
    }
    int mid = (tree[v].l + tree[v].r) >> 1;

    if(r <= mid)
        update(v*2,l,r,z);	//更新左子树
    else if(l > mid)
        update(v*2+1,l,r,z);//更新右子树
    else
    {
        update(v*2,l,mid,z);
        update(v*2+1,mid+1,r,z);//区间横跨了左右儿子区间，两者均更新
    }
}

//可以用下面两种方法求1~n的价值和。
/*int query(int v, int l, int r)
{
    if(tree[v].l == l && tree[v].r == r)
    {
        if(tree[v].col != -1)
            return tree[v].col*(r-l+1);
        else
        {
            int mid = (tree[v].l + tree[v].r)>>1;
            return query(v*2,l,mid) + query(v*2+1,mid+1,r);
		}
	}

	int mid = (tree[v].l+tree[v].r)>>1;
	if(r <= mid)
		return query(v*2,l,r);
	else if(l > mid)
		return query(v*2+1,l,r);
	else return query(v*2,l,mid) + query(v*2+1,mid+1,r);
}*/
int query(int v)
{
	if(tree[v].col != -1) //如果该区间有价值就返回。
		return tree[v].col * (tree[v].r-tree[v].l+1);
	else				 //否则说明它的价值已向下传递，返回左右子树的回溯
	{
		return query(v*2) + query(v*2+1);
	}
}

int main()
{
    int test;
    scanf("%d",&test);
    for(int item = 1; item <= test; item++)
    {
        int n,m;
        int x,y,z;
        scanf("%d",&n);
        build(1,1,n);

		scanf("%d",&m);

        while(m--)
        {
            scanf("%d %d %d",&x,&y,&z);
            update(1,x,y,z);
        }
       printf("Case %d: The total value of the hook is %d.\n",item,query(1));
    }
    return 0;
}

hdu 1698 Just a Hook(线段树 成段更新+总区间求和)

原文：http://blog.csdn.net/u013081425/article/details/19070703