hdu 1698 线段树（成段替换区间求和）

一条钩子由许多小钩子组成更新一段小钩子变成铜银金价值分别变成1 2 3 输出最后的总价值

Sample Input
1
10
2
1 5 2
5 9 3

Sample Output
Case 1: The total value of the hook is 24.

 1 # include <iostream>
 2 # include <cstdio>
 3 # include <cstring>
 4 # include <algorithm>
 5 # include <cmath>
 6 # include <queue>
 7 # define LL long long
 8 using namespace std ;
 9 
10 
11 const int maxn = 100010;
12 
13 int sum[maxn<<2] ; //结点开4倍
14 int col[maxn<<2] ; //延迟标记
15 
16 void PushUP(int rt) //更新到父节点
17 {
18     sum[rt] = sum[rt * 2] + sum[rt * 2 + 1] ; //rt 为当前结点
19 }
20 
21 void PushDown(int rt , int m )  //向下更新
22 {
23     if (col[rt])
24     {
25         col[rt * 2] = col[rt * 2 + 1] = col[rt] ;
26         sum[rt * 2] = (m - m / 2) * col[rt] ;
27         sum[rt * 2 + 1] = (m / 2) * col[rt] ;
28         col[rt] = 0 ;
29     }
30 }
31 
32 void build(int l , int r , int rt) //构建线段树
33 {
34     col[rt] = 0 ;
35     if (l == r)
36     {
37         sum[rt] = 1 ;
38         return ;
39     }
40     int m = (l + r) / 2 ;
41     build(l , m , rt * 2) ;
42     build(m + 1 , r , rt * 2 +1) ;
43     PushUP(rt) ;
44 }
45 
46 void updata(int L , int R , int c , int l , int r , int rt)
47 {
48     if (L <= l && r <= R)
49         {
50             col[rt] = c ;
51             sum[rt] = (r - l + 1) * c ;
52             return  ;
53         }
54     PushDown(rt , r - l + 1) ;
55     int m = (l + r) / 2 ;
56 
57     if (L <= m)
58        updata(L , R , c , l , m , rt * 2) ;
59     if (R > m)
60        updata(L , R , c , m + 1 , r , rt * 2 + 1) ;
61 
62     PushUP(rt) ;
63 }
64 
65 
66 
67 int main ()
68 {
69     //freopen("in.txt","r",stdin) ;
70     int n , m ;
71     int T ;
72     int Case = 0 ;
73     scanf("%d" , &T) ;
74     while(T--)
75     {
76         Case++ ;
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             updata(a , b , c , 1 , n , 1) ;
84         }
85         printf("Case %d: The total value of the hook is %d.
",Case , sum[1]);
86     }
87 
88     return 0 ;
89 }

View Code

hdu 1698 线段树（成段替换 区间求和）

hdu 1698 线段树（成段替换区间求和）