hdu 1698 线段树

因为最后要求的是区间和，所以其实color不用存下来，这里将color当做lazy标记：color为-1表示已经pushdown或为初始状态；color为1、2、3时表示区间为相应颜色。
 1 #include <iostream>
 2 #include <cstring>
 3 #include <cstdio>
 4 using namespace std;
 5 
 6 const int N = 100001;
 7 
 8 struct Node 
 9 {
10     int l, r, sum, color;
11 } node[N << 2];
12 
13 void build( int i, int l, int r )
14 {
15     node[i].l = l, node[i].r = r, node[i].sum = r - l + 1, node[i].color = -1;
16     if ( l == r ) return ;
17     int mid = ( l + r ) >> 1;
18     build( i << 1, l, mid );
19     build( i << 1 | 1, mid + 1, r );
20 }
21 
22 void pushup( int i )
23 {
24     node[i].sum = node[i << 1].sum + node[i << 1 | 1].sum;
25 }
26 
27 void pushdown( int i )
28 {
29     if ( node[i].color != -1 )
30     {
31         int lc = i << 1, rc = lc | 1;
32         node[lc].color = node[rc].color = node[i].color;
33         node[lc].sum = ( node[lc].r - node[lc].l + 1 ) * node[i].color;
34         node[rc].sum = ( node[rc].r - node[rc].l + 1 ) * node[i].color;
35         node[i].color = -1;
36     }
37 }
38 
39 void update( int i, int l, int r, int c )
40 {
41     if ( node[i].l == l && node[i].r == r )
42     {
43         node[i].color = c;
44         node[i].sum = ( r - l + 1 ) * c;        
45         return ;        
46     }
47     pushdown(i);
48     int mid = ( node[i].l + node[i].r ) >> 1;
49     if ( r <= mid )
50     {
51         update( i << 1, l, r, c );
52     }
53     else if ( l > mid )
54     {
55         update( i << 1 | 1, l, r, c );        
56     }
57     else
58     {
59         update( i << 1, l, mid, c );
60         update( i << 1 | 1, mid + 1, r, c );        
61     }
62     pushup(i);
63 }
64 
65 int main ()
66 {
67     int t;
68     scanf("%d", &t);
69     for ( int _case = 1; _case <= t; _case++ )    
70     {
71         int n, m;
72         scanf("%d%d", &n, &m);        
73         build( 1, 1, n );
74         while ( m-- )
75         {
76             int a, b, c;
77             scanf("%d%d%d", &a, &b, &c);
78             update( 1, a, b, c );
79         }
80         printf("Case %d: The total value of the hook is %d.
", _case, node[1].sum);
81     }
82     return 0;
83 }