2017-08-30 16:44:33

writer：pprp

上午刚刚复习了一下不带有lazy标记的线段树，

下午开始学带有lazy标记的线段树

这个是我看大佬代码敲的，但是出了很多问题，

这提醒我：

1、要注意边界条件，一个边界条件的取等或者不取等，小于或者大于出错的话就直接运行不了了

2、注意输入输出，经过多次测试，果然还是用scanf比较保险，试了试用fast_io的cin结果还是TLE

　　所以以后不要用cin了，cin害人啊，两个混用就更加麻烦了

这个题就是区间修改，区间查询的一道题，但是大佬没有用指针构造一个结构体

仅仅抽象了一个sum和一个add（lazy标记）

感觉简单了不少

代码如下：

/*@theme:segmentation/interval tree@writer:pprp@begin:15:26@end:16:13@declare: 使用lazy标记的线段树,HDU 1698@date:2017/8/30*/#include 
     
      #include 
      
       #define Mid ((l+r)>>1)#define lson rt<<1,l,Mid#define rson rt<<1|1,Mid+1,rconst int maxn = 100010;int sum[maxn<<2],add[maxn<<2];using namespace std;void build(int rt,int l, int r){    add[rt] = 0;    //这里是每个节点都是1的情况    if(l == r)        sum[rt] = 1;    else    {        build(rson);        build(lson);        sum[rt] = sum[rt<<1]+sum[rt<<1|1];    }}void pushDown(int rt, int len){    //将父节点的add值传递下来    add[rt<<1] = add[rt<<1|1] = add[rt];    //将左右的值进行区间更新    sum[rt<<1] =  (len - (len>>1))*add[rt];    sum[rt<<1|1] = (len>>1)*add[rt];    //将父节点的add值清空    add[rt] =0;}//L,R代表的要更新区间的左右端点，z是区间增加的值void update(int rt, int l,int r, int L, int R, int z){    //如果在L,R的内部    if(L <= l && r <= R)   //error before    {        add[rt] = z;        sum[rt] = (r - l + 1) * z;    }    else  //没有找到该节点    {        if(add[rt])//当前节点不为空，要传下去            pushDown(rt,r-l+1);        if(L <= Mid)            update(lson,L,R,z);        if(R > Mid) //error before            update(rson,L,R,z);        sum[rt] = sum[rt<<1]+sum[rt<<1|1];    }}int main()  {  //    RE;      int t,n,q,x,y,z;      int cnt=1;      scanf("%d",&t);      while(t--){          scanf("%d%d",&n,&q);          build(1,1,n);          while(q--){              scanf("%d%d%d",&x,&y,&z);              update(1,1,n,x,y,z);          }          printf("Case %d: The total value of the hook is %d.\n", cnt++,sum[1]);      }      return 0;  }