hdu1698Just a Hook

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1698
区间更新，区间求和。
 1 //区间更新，求区间和
 2 #include<cstdio>
 3 #include<algorithm>
 4 using namespace std;
 5 #define ll long long
 6 #define lson l,m,rt<<1
 7 #define rson m+1,r,rt<<1|1
 8 const int maxn=100010;
 9 ll add[maxn<<2];
10 ll sum[maxn<<2];
11 
12 
13 void pushup(int rt)
14 {
15     sum[rt]=sum[rt<<1]+sum[rt<<1|1];
16 }
17 void pushdown(int rt,int m)
18 {
19     if(add[rt])
20     {
21         add[rt<<1]=add[rt];
22         add[rt<<1|1]=add[rt];
23         sum[rt<<1]=add[rt]*(m-(m>>1));
24         sum[rt<<1|1]=add[rt]*(m>>1);
25         add[rt]=0;
26     }
27 }
28 
29 void build(int l,int r,int rt)
30 {
31     add[rt]=0;
32     if(l==r) {
33         sum[rt]=1;
34         return;
35     }
36     int m=(l+r)>>1;
37     build(lson);
38     build(rson);
39     pushup(rt);
40 }
41 
42 void update(int L,int R,int c,int l,int r,int rt)
43 {
44     if(L<=l&&r<=R){
45              add[rt]=c;
46         sum[rt]=(ll)c*(r-l+1);
47         return ;
48     }
49     pushdown(rt,r-l+1);
50     int m=(l+r)>>1;
51     if(L<=m) update(L,R,c,lson);
52     if(R>m) update(L,R,c,rson);
53     pushup(rt);
54 }
55 
56 ll query(int L,int R,int l,int r,int rt)
57 {
58     if(L<=l&&r<=R)
59     {
60         return sum[rt];
61     }
62     pushdown(rt,r-l+1);
63     ll ans=0;
64     int m=(l+r)>>1;
65     if(L<=m) ans+=query(L,R,lson);
66     if(R>m) ans+=query(L,R,rson);
67     return ans;
68 }
69 
70 int main()
71 {
72     int n,m;
73     int t;
74     scanf("%d",&t);
75    for(int i=1;i<=t;i++)
76     {
77         scanf("%d%d",&n,&m);
78         build(1,n,1);
79         while(m--)
80         {
81             int a,b,c;
82             scanf("%d%d%d",&a,&b,&c);
83             update(a,b,c,1,n,1);
84         }
85         printf("Case %d: The total value of the hook is %lld.
",i,query(1,n,1,n,1));
86     }
87     return 0;
88 }