hdu1698Just a Hook

题目大意: 有一个区间1~n,初始值每个点的值都是1,现在要对区间的子区间内的点的值做统一的一些修改,每次修改的值为1~3之间,当这些修改完毕之后要求你求1~n之间的所有点的和。
题目连接http://acm.hdu.edu.cn/showproblem.php?pid=1698
解题思路: 这其实就是一个入门级别的带区间更新的线段树!前面我已经讲过线段树的创建、单点更新和简单的查询了、所以这里我着重要讲的就是线段树的区间更新问题。
我们知道线段树的没一个节点其实代表的都是一个区间里面的最值,但是在这个问题里面我们表示将不在是这个区间的最值,而是这个区间的统一的值,或者是不统一的值,因此我们在定义节点结构体的时候,里面应该加一个属性叫做value,就本题而言,value的取值范围是1、2、3,0,前面三个属性其实代表的就是节点代表的区间的统一的一个值,而当value=https://www.it610.com/article/0的时候,就意味着这个节点内有多种不同的值,所以当我们求和的时候,就应该进入下一层节点,将这些值不同的区间分别相加!

typedef struct node{ int left; int right; int value; };

首先我们建树,将所有节点的value值赋值为1.
node tree[4*N]; void build(int root,int l,int r){ tree[root].left= l; tree[root].right=r; tree[root].value=https://www.it610.com/article/1; if(l==r) return ; int mid=(l+r)/2; build(root*2,l,mid); build(root*2+1,mid+1,r); return ; }

然后我们要写区间更新的函数了,在区间更新的时候应该怎么样取跟新呢?这里要顺带提一下线段树的精髓,lazy标记。 什么是lazy标记?
其实从字面意思理解就是一种懒惰的标记的方法,就是说,每次更新的时候,就没必要将每一个子节点都更新了?为什么可以这样呢?试想一下,如果说我要将区间[1~n]的值全部变为3,然后要你求出区间[1~n]的和,你还有必要将[1,n]下面的子节点的值都一一改变吗?答案肯定是NO!。
再考虑我们要修改区间[1,5]内的所有值为2,那么这应该怎么样修改呢?,我们知道节点[1,10]的左子树和右子树所代表的区间分别是[1,5],和[6,10],大家仔细看看左子树[1,5],这是一个多么亮的亮点啊!!!,对!没错,我们的目的不就是要将左子树[1,5]的value的值变为2吗?那父节点[1,10]和右边的兄弟[6,10]怎么办?对于[6,10]又不用做任何的修改,所以不动它就行了,但是对于父节点[1,10]它的两个子节点区间的值并不相等,怎么办?前面我们已经说过了,当区间没有统一的值的时候令value值为0就可以了,这样当要进行查询的时候就知道该区间内没有统一的值,应该去找子树中有统一值得区间,计算!

void updata(int root,int l,int r,int v){ if(tree[root].value=https://www.it610.com/article/=v) return ; if(tree[root].left==l&&tree[root].right==r){ tree[root].value=v; return ; } if(tree[root].value){ tree[root*2].value=tree[root*2+1].value=tree[root].value; tree[root].value=0; } int mid=(tree[root].left+tree[root].right)/2; if(l>mid) updata(root*2+1,l,r,v); else if(r<=mid){ updata(root*2,l,r,v); } else{ updata(root*2,l,mid,v); updata(root*2+1,mid+1,r,v); } return ; }

最后我们来想一下计算的部分,对于被修改过的线段树,我们应该怎么样求得整个区间的值呢?其实我们可以从根节点开始,从上到下进行如下操作就可以了。 一、假设当且节点的value的值大于零,也就意味着这个节点的代表的区间有统一的值value,那么这个区间的和值就等于==区间长度*value
二、节点value的值等于0,那么这个区间的和值就等于==左子树区间和值+右子树区间和.
从上面可以看出这个其实就是一个递归的过程!
【hdu1698Just a Hook】
int getAns(int root,int l,int r){ if(tree[root].value){ return (tree[root].right-tree[root].left+1)*tree[root].value; } int mid=(tree[root].left+tree[root].right)/2; return getAns(root*2,l,mid)+getAns(root*2+1,mid+1,r); }

对于所有的操作讲解完毕了!发个本题代码。
#include #define N 100010 typedef struct node{ int left; int right; int value; }; node tree[4*N]; void build(int root,int l,int r){ tree[root].left= l; tree[root].right=r; tree[root].value=1; if(l==r) return ; int mid=(l+r)/2; build(root*2,l,mid); build(root*2+1,mid+1,r); return ; } void updata(int root,int l,int r,int v){ if(tree[root].value=https://www.it610.com/article/=v) return ; if(tree[root].left==l&&tree[root].right==r){ tree[root].value=v; return ; } if(tree[root].value){ tree[root*2].value=tree[root*2+1].value=tree[root].value; tree[root].value=0; } int mid=(tree[root].left+tree[root].right)/2; if(l>mid) updata(root*2+1,l,r,v); else if(r<=mid){ updata(root*2,l,r,v); } else{ updata(root*2,l,mid,v); updata(root*2+1,mid+1,r,v); } return ; } int getAns(int root,int l,int r){ if(tree[root].value){ return (tree[root].right-tree[root].left+1)*tree[root].value; } int mid=(tree[root].left+tree[root].right)/2; return getAns(root*2,l,mid)+getAns(root*2+1,mid+1,r); } int main(){ int cas=1; int t,n,m; scanf("%d",&t); int a,b,v,ans; while(t--){ scanf("%d",&n); build(1,1,n); scanf("%d",&m); while(m--){ scanf("%d%d%d",&a,&b,&v); updata(1,a,b,v); } ans=getAns(1,1,n); printf("Case %d: The total value of the hook is %d.\n",cas,ans); ++cas; } return 0; }






    推荐阅读