【题意】：总所周知，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