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