学步园

题意：dota中的英雄 Pudge 有一hook 这hook 可由三种材料构成 分别如下
For each cupreous stick, the value is 1.
For each silver stick, the value is 2.
For each golden stick, the value is 3.
现输入 x y z 表示x到y的hook 的值变为z 。z如上如述
求最后，hook的值

思路：线段树 普通的线段树会超时，得成段更新 用到了延迟覆盖
//890MS   
5336K

#include <stdio.h>
#define M 100005

struct data
{
    int
l,r;
    int
add,val,cover;
}node[3*M];

void BuildTree(int left,int right,int u)
{
    node[u].l =
left;
    node[u].r =
right;
    node[u].add
= 1;
   
node[u].cover = 1;
    node[u].val
= (right-left)+1;
    if (left ==
right)
       
return ;
    int mid =
(left+right)>>1;
   
BuildTree(left,mid,u<<1);
   
BuildTree(mid+1,right,(u<<1)+1);

}

void get_down (int
u)       
//延迟覆盖
{
   
node[u<<1].add = node[u].add;
   
node[u<<1].val =
(node[u<<1].r-node[u<<1].l+1)*node[u].add;

   
node[u<<1].cover = 1;
   
node[(u<<1)+1].add =
node[u].add;
   
node[(u<<1)+1].val =
(node[(u<<1)+1].r-node[(u<<1)+1].l+1)*node[u].add;

   
node[(u<<1)+1].cover = 1;
   
node[u].cover = 0;
}
void updata (int left,int right,int op,int u)
{
    if
(node[u].l == left&&node[u].r ==
right)  //成段更新
    {
       
node[u].cover = 1;
       
node[u].add = op;
       
node[u].val = (node[u].r - node[u].l+1)*op;
       
return ;
    }
    if
(node[u].cover)   

       
get_down(u);
    int mid =
(node[u].l + node[u].r)>>1;
    if (right
<= mid)
       
updata (left,right,op,u<<1);
    else if
(left >= mid+1)
       
updata
(left,right,op,(u<<1)+1);
    else {
       
updata (left,mid,op,u<<1);
       
updata
(mid+1,right,op,(u<<1)+1);
    }
    node[u].val
= node[u<<1].val +
node[(u<<1)+1].val;   
//递归回来 修改父亲结点的val
}
int main ()
{
    int
t,n,m,x,y,op,count = 0;
    scanf
("%d",&t);
    while (t
--)
    {
       
scanf ("%d%d",&n,&m);
       
BuildTree(1,n,1);
       
while (m --)
       
{
           
scanf
("%d%d%d",&x,&y,&op);

           
updata (x,y,op,1);
       
}
       
int ans = node[1].val;