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

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;
  19. #define LL long long
  20. const int maxn = 50000 + 100;
  21. int T, n, Index, tmp;
  22. char str[10];
  23. int sum[maxn << 2];
  24. void push_up(int rt) {
  25. sum[rt] = sum[rt << 1] + sum[rt << 1 | 1];
  26. }
  27. void build(int l, int r, int rt) {
  28. if(l == r) {
  29. scanf("%d", &sum[rt]);
  30. return ;
  31. }
  32. int m = (l + r) >> 1;
  33. build(l, m, rt << 1);
  34. build(m + 1, r, rt << 1 | 1);
  35. push_up(rt);
  36. }
  37. void add(int Index, int tmp, int l, int r, int rt) {
  38. if(l == r) {
  39. sum[rt] += tmp;
  40. return ;
  41. }
  42. int m = (l + r) >> 1;
  43. if(Index <= m) {
  44. add(Index, tmp, l, m, rt << 1);
  45. } else {
  46. add(Index, tmp, m + 1, r, rt << 1 | 1);
  47. }
  48. push_up(rt);
  49. }
  50. int query(int L, int R, int l, int r, int rt) {
  51. if(L <= l && r <= R) {
  52. return sum[rt];
  53. }
  54. int m = (l + r) >> 1;
  55. int ret = 0;
  56. if(L <= m) {
  57. ret += query(L, R, l, m, rt << 1);
  58. }
  59. if(m < R) {
  60. ret += query(L, R, m + 1, r, rt << 1 | 1);
  61. }
  62. return ret;
  63. }
  64. int main() {
  65. #ifdef LOCAL
  66. freopen("test.txt", "r", stdin);
  67. // freopen("out.txt", "w", stdout);
  68. #endif // LOCAL
  69. ios::sync_with_stdio(false);
  70. scanf("%d", &T);
  71. for(int cas = 1; cas <= T; ++cas) {
  72. printf("Case %d:\n", cas);
  73. scanf("%d", &n);
  74. build(1, n, 1);
  75. while(scanf("%s", str), str[0] != 'E') {
  76. scanf("%d%d", &Index, &tmp);
  77. if(str[0] == 'Q') {
  78. printf("%d\n", query(Index, tmp, 1, n, 1));
  79. } else if(str[0] == 'A') {
  80. add(Index, tmp, 1, n, 1);
  81. } else {
  82. add(Index, -tmp, 1, n, 1);
  83. }
  84. }
  85. }
  86. return 0;
  87. }

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;
  19. #define LL long long
  20. const int maxn = 100000 + 100;
  21. int T, n, q, l, r, num;
  22. int sum[maxn << 2], lazy[maxn << 2];
  23. void push_up(int rt) {
  24. sum[rt] = sum[rt << 1] + sum[rt << 1 | 1];
  25. }
  26. void push_down(int rt, int len) {
  27. if(lazy[rt] != 0) {
  28. lazy[rt << 1] = lazy[rt << 1 | 1] = lazy[rt];
  29. sum[rt << 1] = (len - (len >> 1)) * lazy[rt];
  30. sum[rt << 1 | 1] = (len >> 1) * lazy[rt];
  31. lazy[rt] = 0;
  32. }
  33. }
  34. void build(int l, int r, int rt) {
  35. lazy[rt] = 0;
  36. if(l == r) {
  37. sum[rt] = 1;
  38. return ;
  39. }
  40. int m = (l + r) >> 1;
  41. build(l, m, rt << 1);
  42. build(m + 1, r, rt << 1 | 1);
  43. push_up(rt);
  44. }
  45. void update(int L, int R, int tmp, int l, int r, int rt) {
  46. if(L <= l && r <= R) {
  47. lazy[rt] = tmp;
  48. sum[rt] = (r - l + 1) * tmp;
  49. return ;
  50. }
  51. push_down(rt, r - l + 1);
  52. int m = (l + r) >> 1;
  53. if(L <= m) {
  54. update(L, R, tmp, l, m, rt << 1);
  55. }
  56. if(m < R) {
  57. update(L, R, tmp, m + 1, r, rt << 1 | 1);
  58. }
  59. push_up(rt);
  60. }
  61. int main() {
  62. #ifdef LOCAL
  63. freopen("test.txt", "r", stdin);
  64. // freopen("out.txt", "w", stdout);
  65. #endif // LOCAL
  66. ios::sync_with_stdio(false);
  67. scanf("%d", &T);
  68. for(int cas = 1; cas <= T; ++cas) {
  69. scanf("%d", &n);
  70. build(1, n, 1);
  71. scanf("%d", &q);
  72. for(int i = 0; i < q; ++i) {
  73. scanf("%d%d%d", &l, &r, &num);
  74. update(l, r, num, 1, n, 1);
  75. }
  76. printf("Case %d: The total value of the hook is %d.\n", cas, sum[1]);
  77. }
  78. return 0;
  79. }

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;
  19. #define LL long long
  20. const int maxn = 100000 + 100;
  21. int n, q, a, b, c;
  22. char ch[2];
  23. LL sum[maxn << 2], lazy[maxn << 2];
  24. void push_up(int rt) {
  25. sum[rt] = sum[rt << 1] + sum[rt << 1 | 1];
  26. }
  27. void push_down(int rt, int len) {
  28. if(lazy[rt] != 0) {
  29. lazy[rt << 1] += lazy[rt];
  30. lazy[rt << 1 | 1] += lazy[rt];
  31. sum[rt << 1] += (len - (len >> 1)) * lazy[rt];
  32. sum[rt << 1 | 1] += (len >> 1) * lazy[rt];
  33. lazy[rt] = 0;
  34. }
  35. }
  36. void build(int l, int r, int rt) {
  37. lazy[rt] = 0;
  38. if(l == r) {
  39. scanf("%lld", &sum[rt]);
  40. return ;
  41. }
  42. int m = (l + r) >> 1;
  43. build(l, m, rt << 1);
  44. build(m + 1, r, rt << 1 | 1);
  45. push_up(rt);
  46. }
  47. void add(int L, int R, int tmp, int l, int r, int rt) {
  48. if(L <= l && r <= R) {
  49. lazy[rt] += tmp;
  50. sum[rt] += (r - l + 1) * tmp;
  51. return ;
  52. }
  53. push_down(rt, r - l + 1);
  54. int m = (l + r) >> 1;
  55. if(L <= m) {
  56. add(L, R, tmp, l, m, rt << 1);
  57. }
  58. if(R > m) {
  59. add(L, R, tmp, m + 1, r, rt << 1 | 1);
  60. }
  61. push_up(rt);
  62. }
  63. LL query(int L, int R, int l, int r, int rt) {
  64. if(L <= l && r <= R) {
  65. return sum[rt];
  66. }
  67. push_down(rt, r - l + 1);
  68. int m = (l + r) >> 1;
  69. LL ret = 0;
  70. if(L <= m) {
  71. ret += query(L, R, l, m, rt << 1);
  72. }
  73. if(m < R) {
  74. ret += query(L, R, m + 1, r, rt << 1 | 1);
  75. }
  76. return ret;
  77. }
  78. int main() {
  79. #ifdef LOCAL
  80. freopen("test.txt", "r", stdin);
  81. // freopen("out.txt", "w", stdout);
  82. #endif // LOCAL
  83. ios::sync_with_stdio(false);
  84. while(scanf("%d%d", &n, &q) != EOF) {
  85. build(1, n, 1);
  86. while(q--) {
  87. scanf("%s", ch);
  88. if(ch[0] == 'Q') {
  89. scanf("%d%d", &a, &b);
  90. printf("%lld\n", query(a, b, 1, n, 1));
  91. } else {
  92. scanf("%d%d%d", &a, &b, &c);
  93. add(a, b, c, 1, n, 1);
  94. }
  95. }
  96. }
  97. return 0;
  98. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注