HDU 1698.Just a Hook-线段树(成段替换、输出总和tree[1])

 1 #include<iostream>
 2 #include<cstring>
 3 #include<cstdio>
 4 #include<cmath>
 5 #include<algorithm>
 6 #include<cstdlib>
 7 #include<queue>
 8 #include<stack>
 9 #include<map>
10 using namespace std;
11 typedef long long ll;
12 const int maxn=1e5+10;
13 const int inf=0x3f3f3f3f;
14 const double eps=1e-5;
15 #define lson l,m,rt<<1
16 #define rson m+1,r,rt<<1|1
17 int tree[maxn<<2],add[maxn<<2];
18 void pushup(int rt)
19 {
20     tree[rt]=tree[rt<<1]+tree[rt<<1|1];
21 }
22 void pushdown(int rt,int m)
23 {
24     if(add[rt]){
25         add[rt<<1]=add[rt<<1|1]=add[rt];
26         tree[rt<<1]=(m-(m>>1))*add[rt];
27         tree[rt<<1|1]=(m>>1)*add[rt];
28         add[rt]=0;
29     }
30 }
31 void build(int l,int r,int rt)
32 {
33     add[rt]=0;
34     tree[rt]=1;
35     if(l==r){
36         return ;
37     }
38 
39     int m=(l+r)>>1;
40     build(lson);
41     build(rson);
42     pushup(rt);
43 }
44 void update(int L,int R,int c,int l,int r,int rt)
45 {
46     if(L<=l&&r<=R){
47         add[rt]=c;
48         tree[rt]=c*(r-l+1);
49         return ;
50     }
51 
52     pushdown(rt,r-l+1);
53     int m=(l+r)>>1;
54     if(L<=m) update(L,R,c,lson);
55     if(R> m) update(L,R,c,rson);
56     pushup(rt);
57 }
58 int main()
59 {
60     int t,n,m;
61     while(~scanf("%d",&t)){
62         int cas=0;
63         while(t--){
64             cas++;
65             scanf("%d%d",&n,&m);
66             build(1,n,1);
67             for(int i=1;i<=m;i++){
68                 int l,r,c;
69                 scanf("%d%d%d",&l,&r,&c);
70                 update(l,r,c,1,n,1);
71             }
72             printf("Case %d: The total value of the hook is %d.
",cas,tree[1]);
73         }
74     }
75     return 0;
76 }