【题意】:总所周知,Dota里面有个屠夫,他有个吊钩。现在考虑他的吊钩由n(n<=100000)段小棒组成,初始时,都是铜棒。给出q(q<=100000)个操作,每个操作都可以把第i段到第j段的小棒替换成其他类型的棒(铜棒,银棒,金棒,价值分别为1,2,3)。问,经过q个操作之后,这个吊钩的总价值为多少。

【题解】:线段树,区间替换,区间查询。
               初学线段树,理解延迟标记是关键。
               本题比较特殊,查询只有一次,而且是查询整个区间,输出stick[1]即可。

【代码】:
 1 #include "iostream"
 2 #include "cstdio"
 3 #include "cstring"
 4 #include "algorithm"
 5 #include "vector"
 6 #include "queue"
 7 using namespace std;
 8 #define pb push_back
 9 #define lc(x) (x << 1)
10 #define rc(x) (x << 1 | 1)
11 #define MAX 100005
12 int stick[MAX<<2], n, m;
13 int lazy[MAX<<2];
14 
15 void pushup(int p) {
16     stick[p] = stick[lc(p)] + stick[rc(p)];
17 }
18 
19 void pushdown(int p, int len) {
20     if(lazy[p]) {
21         lazy[lc(p)] = lazy[rc(p)] = lazy[p];
22         stick[lc(p)] = (len - (len >> 1)) * lazy[p];
23         stick[rc(p)] = (len >> 1) * lazy[p];
24         lazy[p] = 0;
25     }
26 }
27 
28 void build(int l, int r, int p) {
29     lazy[p] = 0;
30     if(l == r) {
31         stick[p] = 1;
32         return;
33     }
34     int mid = (l + r) >> 1;
35     build(l, mid, lc(p));
36     build(mid + 1, r, rc(p));
37     pushup(p);
38 }
39 
40 void update(int L, int R, int c, int l, int r, int p) {
41     if(L <= l && r <= R) {
42         lazy[p] = c;
43         stick[p] = c * (r - l + 1);
44         return;
45     }
46     pushdown(p, r - l + 1);
47     int mid = (l + r) >> 1;
48     if(L <= mid) update(L, R, c, l, mid, lc(p));
49     if(R > mid) update(L, R, c, mid + 1, r, rc(p));
50     pushup(p);
51 }
52 
53 int main() {
54     int T, Case = 1;
55     int x, y, z;
56     scanf("%d", &T);
57     while(T--) {
58         scanf("%d%d", &n, &m);
59         build(1, n, 1);
60         while(m--) {
61             scanf("%d%d%d", &x, &y, &z);
62             update(x, y, z, 1, n, 1);
63         }
64         printf("Case %d: The total value of the hook is %d.\n", Case++, stick[1]);
65     }
66     return 0;
67 }
68