本文主要是介绍hdu 1698 Just a Hook(线段树区间更新·经典)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目：http://acm.hdu.edu.cn/showproblem.php?pid=1698
数据：case,n,q,q行x,y,z。在长度为n的hook上进行q次区间更新，把它们的价值改变。最后统计总的价值。x,y,z分别表示把[x,y]内的hook变成价值为z的hook。
开始写它时，对于样例程序运行的结果总是20，我就纳闷了，怎么改都不对，在反复研究中发现了这样一个问题（bug源于update函数）：
void update(int a,int b,int root,int tg){if(a==tree[root].l&&b==tree[root].r){tree[root].tag=tg;tree[root].val=(tree[root].r-tree[root].l+1)*tree[root].tag;return ;}int m=tree[root].mid();if(a>m) update(a,b,2*root+1,tg);else if(b<=m) update(a,b,2*root,tg);else {update(a,m,2*root,tg);update(m+1,b,2*root+1,tg);}tree[root].val=tree[2*root].val+tree[2*root+1].val;
}我设置了这样的输入：
2
10
2
1 5 2
5 9 3
10
1
1 5 2
也就是第二个输入比第一个输入少了第二步5 9 3，其他都一样，产生的结果是20; 15.我将所有的数据统统输出来，画出线段树：
(1)：
(2)：
啊，操作一和操作二都有作用，但在样例一中操作二把操作一的数据污染了，也就是新插入5~9中的5那一点让10直接变成了7不是加上1。所以，在update函数里有必要对 懒惰标记不是初始化数据的情况下再对其子树进行处理。如更新第5个点时，势必会先过原val=10的父节点，把它的左子树val变成6，再对右子树处理：left=2, right=3, myval=5,再向上传：
(3):
嘿嘿，应该不会犯错了：
#include <iostream>
#include <cstdio>
using namespace std;
const int maxn=1e5+5;
#define l_t 2*root
#define r_t 2*root+1
struct node{int l,r,val,tag; //tag:1 2 3 -1int mid(){ return (l+r)/2; }
}tree[maxn<<2];
void update(int a,int b,int root,int tg){if(a==tree[root].l&&b==tree[root].r){tree[root].tag=tg;tree[root].val=(tree[root].r-tree[root].l+1)*tg;return ;}if(tree[root].tag!=-1){tree[l_t].tag=tree[root].tag;tree[l_t].val=tree[l_t].tag*(tree[l_t].r-tree[l_t].l+1);tree[r_t].tag=tree[root].tag;tree[r_t].val=tree[r_t].tag*(tree[r_t].r-tree[r_t].l+1);tree[root].tag=-1;}int m=tree[root].mid();if(a>m) update(a,b,r_t,tg);else if(b<=m) update(a,b,l_t,tg);else {update(a,m,l_t,tg);update(m+1,b,r_t,tg);}tree[root].val=tree[l_t].val+tree[r_t].val;
}
void build(int l,int r,int root){tree[root].l=l;tree[root].r=r;tree[root].tag=-1;if(r==l){tree[root].val=1;return ;}int mid=(l+r)/2;build(l,mid,l_t);build(mid+1,r,r_t);tree[root].val=tree[l_t].val+tree[r_t].val;
}int main()
{//freopen("cin.txt","r",stdin);int ca;cin>>ca;for(int k=1;k<=ca;k++){int n,q;scanf("%d",&n);build(1,n,1);scanf("%d",&q);for(int i=0;i<q;i++){int x,y,z;scanf("%d%d%d",&x,&y,&z);update(x,y,1,z);}printf("Case %d: The total value of the hook is %d.\n",k,tree[1].val);}return 0;
}这篇关于hdu 1698 Just a Hook(线段树区间更新·经典)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
