题解：
和hdu1166敌兵布阵不同的是 这道题需要区间更新(成段更新)。
单点更新不用说了比较简单，区间更新的话，如果每次都更新到底的话，有点费时间。
这里就体现了线段树的另一个重要思想：延迟标记。
在定义树节点结构体的时候加一个标记:flag。
typedef struct node
{
node():l(0),r(0),data(0),flag(0){} //构造函数 初始化数据成员
int l,r;
int data; //每个节点的数据
int flag; //延迟标记
}TNode;
更新的时候 如果当前区间 被 要更新的区间包括，则标志一下操作 flag，更新一下当前数据 ，直接返回，不必更新到叶子节点。
然后再次 更新或查询的时候 如果该节点有标记，则把当前节点的数据更新，把标志传到孩子节点，再把标志清0。
这就是lazy（延迟、懒惰）思想。
它的好处是更新的时候可以节省大量时间。
知道了lazy思想，那么怎么实现呢？看代码：
#include <iostream>
#include <cstdio>
#include <cstring> using namespace std; const int MAX=100001; typedef struct node
{
node():l(0),r(0),data(0),flag(0){} //构造函数 初始化数据成员
int l,r;
int data; //每个节点的数据
int flag; //延迟标记
}TNode; TNode tNode[MAX<<4]; void pushup(int p) //向上更新
{
tNode[p].data=tNode[p<<1].data+tNode[p<<1|1].data;
} void pushdown(int p) //向下更新
{
tNode[p<<1].flag=tNode[p<<1|1].flag=tNode[p].flag; //把当前节点的标志传到孩子节点
tNode[p<<1].data=(tNode[p<<1].r-tNode[p<<1].l+1)*tNode[p].flag; //更新孩子节点的data数据
tNode[p<<1|1].data=(tNode[p<<1|1].r-tNode[p<<1|1].l+1)*tNode[p].flag;
tNode[p].flag=0; //标志清0
} void buildTree(int p,int l,int r)
{
tNode[p].l=l;
tNode[p].r=r;
tNode[p].flag=0; //建树的时候flag要为0，表示没有操作
if(l==r)
{
tNode[p].data=1;
return;
}
int mid=(l+r)>>1;
buildTree(p<<1,l,mid);
buildTree(p<<1|1,mid+1,r);
pushup(p);
return;
} void update(int p,int l,int r,int x)
{
if(tNode[p].l>=l&&tNode[p].r<=r) //找到 被要更新的区间[l,r]包括的 节点
{
tNode[p].flag=x; //标志一下操作，意思就是把当前以及孩子节点的data值赋值为x。
tNode[p].data=(tNode[p].r-tNode[p].l+1)*x; //更新当前节点的data值。当前区间[l,r]。则它的和为(r-l+1)*x。没毛病！！
return;
}
if(tNode[p].l>r||tNode[p].r<l) //如果当前区间和要更新的区间没有交集
{
return;
}
if(tNode[p].flag!=0) pushdown(p); //如果当前区间有操作标记，则向下更新并把标记传给左右孩子节点
update(p<<1,l,r,x); //更新左孩子
update(p<<1|1,l,r,x); //更新右孩子
pushup(p); //回溯的时候向上更新 } //这个方法这道题没用到
int query(int p,int l,int r)
{
if(tNode[p].l>=l&&tNode[p].r<=r)
{
return tNode[p].data;
}
if(tNode[p].l>r||tNode[p].r<l)
{
return 0;
}
int sum=0;
sum+=query(p<<1,l,r);
sum+=query(p<<1|1,l,r);
return sum;
} int main()
{
int Case;
scanf("%d",&Case);
for(int t=1;t<=Case;t++)
{
int n,op;
scanf("%d%d",&n,&op);
buildTree(1,1,n);
while(op--)
{
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
update(1,a,b,c);
}
printf("Case %d: The total value of the hook is %d.\n",t,tNode[1].data);
}
return 0;
}