题目：http://acm.hdu.edu.cn/showproblem.php?pid=1698

线段树， 区间更新， 用到了Lazy思想。利用已更新区间来减少未更新区间用时。（自己的理解， 应该是对的)

 

#include <cstdio>

#include <cstring>

#include <iostream>

using 

namespace std;

int Node[

100100<<

2], n, m, lazy[

100100<<

2];

void Pushup(

int root)

{

    Node[root] = Node[root<<

1] + Node[root<<

1|

1]; 

}

void Pushdown(

int l, 

int r, 

int root)

{

    

int mid = (l + r) >> 

1;

    Node[root<<

1] = (mid - l + 

1)*lazy[root];

    Node[root<<

1|

1] = (r - mid)*lazy[root];

    lazy[root<<

1] = lazy[root<<

1|

1] = lazy[root];

    lazy[root] = 

0;

}

void Build(

int l, 

int r, 

int root)

{

    lazy[root] = 

0;

    

if(l==r)

    {

        Node[root] = 

1;

        

return;

     }    

     

int mid = (l + r) >> 

1;

    Build(l, mid, root<<

1);

    Build(mid + 

1, r, root<<

1|

1);

    Pushup(root); 

} 

void Update(

int x, 

int y, 

int val, 

int l, 

int r, 

int root)

{

    

if(x == l && y == r)

    {

        lazy[root] = val;

        Node[root] = val*(y-x+

1);

        

return;

    }    

    

if(lazy[root])

        Pushdown(l, r, root);

    

int mid = (l + r) >> 

1;

    

if(y <= mid)

        Update(x, y, val, l, mid, root<<

1);

    

else

        

if(x > mid)

            Update(x, y, val, mid + 

1, r, root<<

1|

1);

    

else

    {

        Update(x, mid, val, l, mid, root<<

1);

        Update(mid+

1, y, val, mid+

1, r, root<<

1|

1);

    }

    Pushup(root);

}

int main()

{

    

int T, temp = 

1;

    scanf(

"

%d

", &T); 

    

while(T--)

    {

        scanf(

"

%d%d

", &n, &m);

        Build(

1, n, 

1);

        

while(m--)

        {

            

int a, b, c;

            scanf(

"

%d%d%d

", &a, &b, &c);

            Update(a, b, c, 

1, n, 

1);

        }

        printf(

"

Case %d: The total value of the hook is %d.\n

", temp++, Node[

1]);

    }

    

return 

0;}