学习线段树第二天，这道题属于第二简单的线段树，第一简单是单点更新，这个属于区间更新。
区间更新就是lazy思想，我来按照自己浅薄的理解谈谈lazy思想：
就是在数据结构中，树形结构可以线性存储(线性表)也可以树状存储(链表)
树形
typedef struct node
{
int data;
struct node* Lchild;
struct node* Rchild;
}Btree,*BTree;
BTree = (BTree)malloc(Btree);
好像是这样吧...大半个暑假过去忘得一干二净...这个并不重要....
然后顺序就是存到顺序表了，第i个节点的左孩子节点就是i*2，右孩子节点就是i*2+1,这个是一个性质。
这个题就是用了树结构的顺序表。
好像也没啥说的，简单的模板题，看代码吧：
#include<cstdio>
#define N 100003
using namespace std;
struct nod
{
int data,l,r,lazy;
}tree[*N]; void push_up(int i)
{
tree[i].data = tree[i*].data+tree[i*+].data;
} void build_tree(int i,int l,int r)
{
tree[i].l = l;
tree[i].r = r;
tree[i].lazy = -;
if(l==r){
tree[i].data = ;
return;
}
int mid = (r + l)/;
build_tree(i*,l,mid);
build_tree(i*+,mid+,r);
push_up(i);
} void push_down(int i)
{
tree[i*].data = tree[i].lazy*(tree[i*].r-tree[i*].l+);
tree[i*+].lazy = tree[i*].lazy = tree[i].lazy;
tree[i*+].data = tree[i].lazy*(tree[i*+].r-tree[i*+].l+);
tree[i].lazy = -;
} void updata(int i,int v,int l,int r)
{
if(l<=tree[i].l&&tree[i].r<=r)
{
tree[i].data = (tree[i].r-tree[i].l+)*v;
tree[i].lazy = v;
return;
}
if(tree[i].lazy!=-) push_down(i);
int mid = (tree[i].l+tree[i].r)/;
if(l<=mid)
updata(i*,v,l,r);
if(r > mid)
updata(i*+,v,l,r);
push_up(i);
} int query(int i,int l,int r)
{
if(l<=tree[i].l&&tree[i].r<=r)
{
return tree[i].data;
}
if(tree[i].lazy!=-)
push_down(i);
int mid=(tree[i].l+tree[i].r)/;
if(r<=mid)
return query(i*,l,r);
if(l>=mid+)
return query(i*+,l,r);
return query(i*,l,r)+query(i*+,l,r);
} int main()
{
int noc,ug;
scanf("%d",&noc);
ug = noc;
while(noc--)
{
int n,q,x,y,z;
scanf("%d",&n);
build_tree(,,n);
scanf("%d",&q);
for(int i=;i<=q;i++)
{
scanf("%d%d%d",&x,&y,&z);
updata(,z,x,y);
}
printf("Case %d: The total value of the hook is %d.\n",ug-noc,tree[].data);
}
}