题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1698 首先对我自己做一个无语的表情 ,考试周了我还在每天刷题,不过这个不是终点啦![大笑](http://static.blog.csdn.net/xheditor/xheditor_emot/default/laugh.gif) 题意就是dota里面的屠夫的钩人技能,每钩一个单位长度产生一定的伤害,初始伤害都是1,可以任意改,有三种钩子,金钩银钩铁钩子,三种钩子的单位伤害分别为3,2,1,可以将任意区间内的钩子替换,问最终的总伤害是多少。 裸的区间更新线段树,由于问的是最终的总伤害,只需要求出来根节点的权值就行啦。
![](/Images/OutliningIndicators/ContractedBlock.gif) 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
|