[关闭]
@Dmaxiya 2020-08-25T00:41:34.000000Z 字数 4617 阅读 993

2月27—— 线段树题解

Hello_World

A. 敌兵布阵

题解

线段树单点增减、区间求和裸题。

过题代码

  1. #include <iostream>
  2. #include <cstdio>
  3. #include <cstdlib>
  4. #include <cmath>
  5. #include <climits>
  6. #include <cstring>
  7. #include <string>
  8. #include <vector>
  9. #include <list>
  10. #include <queue>
  11. #include <stack>
  12. #include <map>
  13. #include <set>
  14. #include <bitset>
  15. #include <algorithm>
  16. #include <functional>
  17. #include <iomanip>
  18. using namespace std;
  20. #define LL long long
  21. const int maxn = 50000 + 100;
  22. int T, n, Index, tmp;
  23. char str[10];
  24. int sum[maxn << 2];
  26. void push_up(int rt) {
  27.     sum[rt] = sum[rt << 1] + sum[rt << 1 | 1];
  28. }
  30. void build(int l, int r, int rt) {
  31.     if(l == r) {
  32.         scanf("%d", &sum[rt]);
  33.         return ;
  34.     }
  35.     int m = (l + r) >> 1;
  36.     build(l, m, rt << 1);
  37.     build(m + 1, r, rt << 1 | 1);
  38.     push_up(rt);
  39. }
  41. void add(int Index, int tmp, int l, int r, int rt) {
  42.     if(l == r) {
  43.         sum[rt] += tmp;
  44.         return ;
  45.     }
  46.     int m = (l + r) >> 1;
  47.     if(Index <= m) {
  48.         add(Index, tmp, l, m, rt << 1);
  49.     } else {
  50.         add(Index, tmp, m + 1, r, rt << 1 | 1);
  51.     }
  52.     push_up(rt);
  53. }
  55. int query(int L, int R, int l, int r, int rt) {
  56.     if(L <= l && r <= R) {
  57.         return sum[rt];
  58.     }
  59.     int m = (l + r) >> 1;
  60.     int ret = 0;
  61.     if(L <= m) {
  62.         ret += query(L, R, l, m, rt << 1);
  63.     }
  64.     if(m < R) {
  65.         ret += query(L, R, m + 1, r, rt << 1 | 1);
  66.     }
  67.     return ret;
  68. }
  70. int main() {
  71.     #ifdef LOCAL
  72.     freopen("test.txt", "r", stdin);
  73. //    freopen("out.txt", "w", stdout);
  74.     #endif // LOCAL
  75.     ios::sync_with_stdio(false);
  77.     scanf("%d", &T);
  78.     for(int cas = 1; cas <= T; ++cas) {
  79.         printf("Case %d:\n", cas);
  80.         scanf("%d", &n);
  81.         build(1, n, 1);
  82.         while(scanf("%s", str), str[0] != 'E') {
  83.             scanf("%d%d", &Index, &tmp);
  84.             if(str[0] == 'Q') {
  85.                 printf("%d\n", query(Index, tmp, 1, n, 1));
  86.             } else if(str[0] == 'A') {
  87.                 add(Index, tmp, 1, n, 1);
  88.             } else {
  89.                 add(Index, -tmp, 1, n, 1);
  90.             }
  91.         }
  92.     }
  94.     return 0;
  95. }

B. Just a Hook

题意

在 游戏中，有一种肉勾，这种肉勾可以由等长度的、不同材质的长棒组成，分别有金、银、铜三种材料，铜的价值为 ，银的价值为 ，金的价值为 ，现在有 组数据，每组数据的肉勾总共有 段长棒， 次操作，每次操作将区间 上的所有长棒材料换为指定材料，问最后长棒的价值。

数据范围

题解

线段树区间更新、区间求和裸题。由于最后只对整段区间求和查询，所以直接输出 就行，不用 函数。

过题代码

  1. #include <iostream>
  2. #include <cstdio>
  3. #include <cstdlib>
  4. #include <cmath>
  5. #include <climits>
  6. #include <cstring>
  7. #include <string>
  8. #include <vector>
  9. #include <list>
  10. #include <queue>
  11. #include <stack>
  12. #include <map>
  13. #include <set>
  14. #include <bitset>
  15. #include <algorithm>
  16. #include <functional>
  17. #include <iomanip>
  18. using namespace std;
  20. #define LL long long
  21. const int maxn = 100000 + 100;
  22. int T, n, q, l, r, num;
  23. int sum[maxn << 2], lazy[maxn << 2];
  25. void push_up(int rt) {
  26.     sum[rt] = sum[rt << 1] + sum[rt << 1 | 1];
  27. }
  29. void push_down(int rt, int len) {
  30.     if(lazy[rt] != 0) {
  31.         lazy[rt << 1] = lazy[rt << 1 | 1] = lazy[rt];
  32.         sum[rt << 1] = (len - (len >> 1)) * lazy[rt];
  33.         sum[rt << 1 | 1] = (len >> 1) * lazy[rt];
  34.         lazy[rt] = 0;
  35.     }
  36. }
  38. void build(int l, int r, int rt) {
  39.     lazy[rt] = 0;
  40.     if(l == r) {
  41.         sum[rt] = 1;
  42.         return ;
  43.     }
  44.     int m = (l + r) >> 1;
  45.     build(l, m, rt << 1);
  46.     build(m + 1, r, rt << 1 | 1);
  47.     push_up(rt);
  48. }
  50. void update(int L, int R, int tmp, int l, int r, int rt) {
  51.     if(L <= l && r <= R) {
  52.         lazy[rt] = tmp;
  53.         sum[rt] = (r - l + 1) * tmp;
  54.         return ;
  55.     }
  56.     push_down(rt, r - l + 1);
  57.     int m = (l + r) >> 1;
  58.     if(L <= m) {
  59.         update(L, R, tmp, l, m, rt << 1);
  60.     }
  61.     if(m < R) {
  62.         update(L, R, tmp, m + 1, r, rt << 1 | 1);
  63.     }
  64.     push_up(rt);
  65. }
  67. int main() {
  68.     #ifdef LOCAL
  69.     freopen("test.txt", "r", stdin);
  70. //    freopen("out.txt", "w", stdout);
  71.     #endif // LOCAL
  72.     ios::sync_with_stdio(false);
  74.     scanf("%d", &T);
  75.     for(int cas = 1; cas <= T; ++cas) {
  76.         scanf("%d", &n);
  77.         build(1, n, 1);
  78.         scanf("%d", &q);
  79.         for(int i = 0; i < q; ++i) {
  80.             scanf("%d%d%d", &l, &r, &num);
  81.             update(l, r, num, 1, n, 1);
  82.         }
  83.         printf("Case %d: The total value of the hook is %d.\n", cas, sum[1]);
  84.     }
  86.     return 0;
  87. }

C. A Simple Problem with Integers

题意

对于给定的 个数据 ，有 次操作，第一种操作为将区间 上的数字都加上 ，第二种操作为求区间 上的所有数字的和。

数据范围

题解

线段树区间增减、区间求和裸题。注意 。

过题代码

  1. #include <iostream>
  2. #include <cstdio>
  3. #include <cstdlib>
  4. #include <cmath>
  5. #include <climits>
  6. #include <cstring>
  7. #include <string>
  8. #include <vector>
  9. #include <list>
  10. #include <queue>
  11. #include <stack>
  12. #include <map>
  13. #include <set>
  14. #include <bitset>
  15. #include <algorithm>
  16. #include <functional>
  17. #include <iomanip>
  18. using namespace std;
  20. #define LL long long
  21. const int maxn = 100000 + 100;
  22. int n, q, a, b, c;
  23. char ch[2];
  24. LL sum[maxn << 2], lazy[maxn << 2];
  26. void push_up(int rt) {
  27.     sum[rt] = sum[rt << 1] + sum[rt << 1 | 1];
  28. }
  30. void push_down(int rt, int len) {
  31.     if(lazy[rt] != 0) {
  32.         lazy[rt << 1] += lazy[rt];
  33.         lazy[rt << 1 | 1] += lazy[rt];
  34.         sum[rt << 1] += (len - (len >> 1)) * lazy[rt];
  35.         sum[rt << 1 | 1] += (len >> 1) * lazy[rt];
  36.         lazy[rt] = 0;
  37.     }
  38. }
  40. void build(int l, int r, int rt) {
  41.     lazy[rt] = 0;
  42.     if(l == r) {
  43.         scanf("%lld", &sum[rt]);
  44.         return ;
  45.     }
  46.     int m = (l + r) >> 1;
  47.     build(l, m, rt << 1);
  48.     build(m + 1, r, rt << 1 | 1);
  49.     push_up(rt);
  50. }
  52. void add(int L, int R, int tmp, int l, int r, int rt) {
  53.     if(L <= l && r <= R) {
  54.         lazy[rt] += tmp;
  55.         sum[rt] += (r - l + 1) * tmp;
  56.         return ;
  57.     }
  58.     push_down(rt, r - l + 1);
  59.     int m = (l + r) >> 1;
  60.     if(L <= m) {
  61.         add(L, R, tmp, l, m, rt << 1);
  62.     }
  63.     if(R > m) {
  64.         add(L, R, tmp, m + 1, r, rt << 1 | 1);
  65.     }
  66.     push_up(rt);
  67. }
  69. LL query(int L, int R, int l, int r, int rt) {
  70.     if(L <= l && r <= R) {
  71.         return sum[rt];
  72.     }
  73.     push_down(rt, r - l + 1);
  74.     int m = (l + r) >> 1;
  75.     LL ret = 0;
  76.     if(L <= m) {
  77.         ret += query(L, R, l, m, rt << 1);
  78.     }
  79.     if(m < R) {
  80.         ret += query(L, R, m + 1, r, rt << 1 | 1);
  81.     }
  82.     return ret;
  83. }
  85. int main() {
  86.     #ifdef LOCAL
  87.     freopen("test.txt", "r", stdin);
  88. //    freopen("out.txt", "w", stdout);
  89.     #endif // LOCAL
  90.     ios::sync_with_stdio(false);
  92.     while(scanf("%d%d", &n, &q) != EOF) {
  93.         build(1, n, 1);
  94.         while(q--) {
  95.             scanf("%s", ch);
  96.             if(ch[0] == 'Q') {
  97.                 scanf("%d%d", &a, &b);
  98.                 printf("%lld\n", query(a, b, 1, n, 1));
  99.             } else {
  100.                 scanf("%d%d%d", &a, &b, &c);
  101.                 add(a, b, c, 1, n, 1);
  102.             }
  103.         }
  104.     }
  106.     return 0;
  107. }
添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注