題目鏈接：http://acm.hdu.edu.cn/showproblem.php?pid=1698 首先對我自己做一個無語的表情 ，考試周了我還在每天刷題，不過這個不是終點(diǎn)啦 題意就是dota里面的屠夫的鉤人技能，每鉤一個單位長度產(chǎn)生一定的傷害，初始傷害都是1，可以任意改，有三種鉤子，金鉤銀鉤鐵鉤子，三種鉤子的單位傷害分別為3，2，1，可以將任意區(qū)間內(nèi)的鉤子替換，問最終的總傷害是多少。 裸的區(qū)間更新線段樹，由于問的是最終的總傷害，只需要求出來根節(jié)點(diǎn)的權(quán)值就行啦。
  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
|