题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1698 首先对我自己做一个无语的表情 ，考试周了我还在每天刷题，不过这个不是终点啦 题意就是dota里面的屠夫的钩人技能，每钩一个单位长度产生一定的伤害，初始伤害都是1，可以任意改，有三种钩子，金钩银钩铁钩子，三种钩子的单位伤害分别为3，2，1，可以将任意区间内的钩子替换，问最终的总伤害是多少。 裸的区间更新线段树，由于问的是最终的总伤害，只需要求出来根节点的权值就行啦。
  view code
1 #include <iostream>
2 #include <cstdio>
3 #include <cstring>
4 #include <cstdlib>
5 #include <cmath>
6 #include <algorithm>
7 using namespace std;
8 #define lson l, m, rt << 1
9 #define rson m + 1, r, rt << 1 | 1
10 const int maxn = 100010;
11 int sum[maxn << 2], col[maxn << 2];
12 void PushUp(int rt)
13 {
14 sum[rt] = sum[rt << 1] + sum[rt << 1 | 1];
15 }
16 void PushDown(int rt, int m)
17 {
18 if (col[rt])
19 {
20 col[rt << 1] = col[rt << 1 | 1] = col[rt];
21 sum[rt << 1] = col[rt] * (m - (m >> 1));
22 sum[rt << 1 | 1] = col[rt] * (m >> 1);
23 col[rt] = 0;
24 }
25 }
26 void build(int l, int r, int rt)
27 {
28 col[rt] = 0;
29 if (l == r)
30 {
31 sum[rt] = 1;
32 return;
33 }
34 int m = (l + r) >> 1;
35 build(lson);
36 build(rson);
37 PushUp(rt);
38 }
39 void update(int ll, int rr, int c, int l, int r, int rt)
40 {
41 if (ll <= l && rr >= r)
42 {
43 col[rt] = c;
44 sum[rt] = c * (r - l + 1);
45 return;
46 }
47 PushDown(rt, r - l + 1);
48 int m = (l + r) >> 1;
49 if (ll <= m) update(ll, rr, c, lson);
50 if (rr > m) update(ll, rr, c, rson);
51 PushUp(rt);
52 }
53 int main()
54 {
55 int t;
56 scanf("%d", &t);
57 for (int i = 1; i <= t; i++)
58 {
59 int n, m;
60 scanf("%d%d", &n, &m);
61 build(1, n, 1);
62 while(m--)
63 {
64 int x, y, z;
65 scanf("%d%d%d", &x, &y, &z);
66 update(x, y, z, 1, n, 1);
67 }
68 printf("Case %d: The total value of the hook is %d.\n", i, sum[1]);
69 }
70 return 0;
71
|