hdu 1698 线段树区间更新**懒惰标记

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

题意：给n个钩子，每次都会更新从X到Y这个范围的钩子价值，最后求钩子的总价值。初始的钩子价值为1.

直接暴力求解是会超时，需要有线段树懒惰标记维护数据。

线段树的懒惰标记，直接记录了在X到Y之间的数据，这样可以减少递归总数。

 1 #include<cstdio>
 2 #include<cstring>
 3 using namespace std;
 4 const int maxn=100006;
 5 int t[maxn*4],lazy[maxn*4];
 6 
 7 void update(int now){
 8     t[now]=t[now<<1|1]+t[now<<1];
 9 }
10 
11 void build(int x,int y,int now){
12     lazy[now]=-1; t[now]=1;
13     if(x==y)
14         return ;
15     int mid=(x+y)>>1;
16     build(x,mid,now<<1);
17     build(mid+1,y,now<<1|1);
18     update(now);
19 }
20 
21 void pushdata(int now,int x){
22     if(lazy[now]!=-1){
23         lazy[now<<1]=lazy[now<<1|1]=lazy[now];
24         t[now<<1]=(x-(x>>1))*lazy[now];
25         t[now<<1|1]=(x>>1)*lazy[now];
26         lazy[now]=-1;
27     }
28 }
29 
30 void add(int x,int y,int now,int goal_x,int goal_y,int change){
31     if(goal_x<=x&&y<=goal_y){
32         lazy[now]=change;
33         t[now]=(y-x+1)*change;
34         return ;
35     }
36     pushdata( now, y-x+1);
37     int mid=(x+y)>>1;
38     if(goal_x<=mid) add( x, mid, now<<1, goal_x, goal_y, change);
39     if(mid<goal_y) add( mid+1, y, now<<1|1, goal_x, goal_y, change);
40     update(now);
41 }
42 
43 int main(){
44     int x,y,z,n,m,T,kkk=0;
45     scanf("%d",&T);
46     while(T--){
47         scanf("%d%d",&n,&m);
48         build( 1, n, 1);
49         while(m--){
50             scanf("%d%d%d",&x,&y,&z);
51             add( 1, n, 1, x, y, z);
52         }
53         printf("Case %d: The total value of the hook is %d.
",++kkk, t[1]);
54     }
55 
56     return 0;
57 }