首页 > 其他 > 详细

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

时间:2014-02-11 21:44:59      阅读:380      评论:0      收藏:0      [点我收藏+]

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

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!