devbox
weixin_40725706
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

牛客竞赛数据结构专题班树状数组、线段树练习题

作者：weixin_40725706 | 2024-08-19 09:04:32

赞

踩

牛客竞赛数据结构专题班树状数组、线段树练习题

牛客竞赛_ACM/NOI/CSP/CCPC/ICPC算法编程高难度练习赛_牛客竞赛OJ

G 智乃酱的平方数列（线段树，等差数列，多项式）

题目描述
想必你一定会用线段树维护等差数列吧？让我们来看看它的升级版。

请你维护一个长度为5×10 ^5的数组，一开始数组中每个元素都为0，要求支持以下两个操作：

1、区间[l,r]加自然数的平方数组，即al+=1，al+1+=4，al+2+=9，al+3+=16...ar+=(r−l+1)∗(r−l+1)
2、区间[l,r]查询区间和mod 10^9 + 7

输入描述:
第一行输入n,m,(1≤n,m≤5*10 ^5)
接下来m行，对于每行，先读入一个整数q。
当q的值为1时，还需读入两个整l,r,(1≤l≤r≤n)表示需要对区间[l,r]进行操作，让第一个元素加1，第二个元素加4，第三个元素加9...以此类推。
当q的值为2时，还需读入两个整数l,r(1≤l≤r≤n)表示查询l到r的元素和

输出描述:
对于每一个q=2，输出一行一个非负整数，表示l到r的区间和mod 110^9+7。
示例1

输入
复制

4 4
2 1 4
1 1 4
1 3 4
2 1 4
输出
复制

0
35
示例2

输入
复制

10 6
1 1 6
1 8 9
1 3 6
2 1 10
1 1 10
2 1 10
输出
复制

126
511


解析： 

等差数列可以写成 [x-(l-1)]^2,其中 x 表示当前的位置，等价于 x^2-2*x*(l-1)+(l-1)^2，通过线段树维护其系数即可

  1. #include <iostream>
  2. #include <string>
  3. #include <cstring>
  4. #include <cmath>
  5. #include <ctime>
  6. #include <algorithm>
  7. #include <utility>
  8. #include <stack>
  9. #include <queue>
  10. #include <vector>
  11. #include <set>
  12. #include <math.h>
  13. #include <map>
  14. #include <sstream>
  15. #include <deque>
  16. #include <unordered_map>
  17. #include <unordered_set>
  18. #include <bitset>
  19. #include <stdio.h>
  20. #include <tuple>
  21. using namespace std;
  22. /*
  23. ios::sync_with_stdio(false);
  24. cin.tie(nullptr);
  25. cout.tie(nullptr);
  26. */
  27. typedef long long LL;
  28. #define int long long
  29. #define ld long double
  30. //#define INT __int128
  31. const LL INF = 0x3f3f3f3f3f3f3f3f;
  32. typedef unsigned long long ULL;
  33. typedef pair<long long, long long> PLL;
  34. typedef pair<int, int> PII;
  35. typedef pair<double, double> PDD;
  36. const int inf = 0x3f3f3f3f;
  37. const LL mod = 1e9+7;
  38. const ld eps = 1e-12;
  39. const int N = 5e5 + 10, M = N + 10;
  40. int n, m;
  41. struct TREE {
  42. 	int l, r;
  43. 	int la1, la2, la3;
  44. 	int sum;
  45. 	int base1, base2;
  46. }tr[N << 2];
  47. #define ls u<<1
  48. #define rs u<<1|1
  49. void cal(int u, int la1, int la2, int la3) {
  50. 	la3 %= mod;
  51. 	int len = tr[u].r - tr[u].l + 1;
  52. 	tr[u].sum = (tr[u].sum + len * la3 % mod) % mod;
  53. 	tr[u].sum = (tr[u].sum - 2 * tr[u].base2 * la2 % mod + mod) % mod;
  54. 	tr[u].sum = (tr[u].sum + tr[u].base1 * la1 % mod) % mod;
  55. 	tr[u].la1 = (tr[u].la1 + la1) % mod;
  56. 	tr[u].la2 = (tr[u].la2 + la2) % mod;
  57. 	tr[u].la3 = (tr[u].la3 + la3) % mod;
  58. }
  59. void up(int u) {
  60. 	tr[u].sum = (tr[ls].sum + tr[rs].sum) % mod;
  61. }
  62. void down(int u) {
  63. 	if (tr[u].la1||tr[u].la2||tr[u].la3) {
  64. 		cal(ls, tr[u].la1, tr[u].la2, tr[u].la3);
  65. 		cal(rs, tr[u].la1, tr[u].la2, tr[u].la3);
  66. 		tr[u].la1 = tr[u].la2 = tr[u].la3 = 0;
  67. 	}
  68. }
  69. void build(int u, int l, int r) {
  70. 	tr[u].l = l, tr[u].r = r;
  71. 	if (l == r) {
  72. 		tr[u].base1 = (l * l) % mod , tr[u].base2 = l;
  73. 		return;
  74. 	}
  75. 	int mid = (l + r) >> 1;
  76. 	build(ls, l, mid), build(rs, mid + 1, r);
  77. 	tr[u].base1 = (tr[ls].base1 + tr[rs].base1) % mod;
  78. 	tr[u].base2 = (tr[ls].base2 + tr[rs].base2) % mod;
  79. }
  80. void modify(int u, int l, int r, int d) {
  81. 	if (l <= tr[u].l && tr[u].r <= r) {
  82. 		cal(u, 1, d, d * d);
  83. 		return;
  84. 	}
  85. 	down(u);
  86. 	int mid = (tr[u].l + tr[u].r) >> 1;
  87. 	if (l <= mid)modify(ls, l, r, d);
  88. 	if (r > mid)modify(rs, l, r, d);
  89. 	up(u);
  90. }
  91. int query(int u, int l, int r) {
  92. 	if (l <= tr[u].l && tr[u].r <= r) {
  93. 		return tr[u].sum;
  94. 	}
  95. 	down(u);
  96. 	int ret = 0;
  97. 	int mid = (tr[u].l + tr[u].r) >> 1;
  98. 	if (l <= mid)ret = (ret + query(ls, l, r)) % mod;
  99. 	if (r > mid)ret = (ret + query(rs, l, r)) % mod;
  100. 	//up(u);
  101. 	return ret;
  102. }
  103. signed main() {
  104. 	ios::sync_with_stdio(false);
  105. 	cin.tie(nullptr);
  106. 	cout.tie(nullptr);
  107. 	cin >> n >> m;
  108. 	build(1, 1, n);
  109. 	int op, l, r;
  110. 	while (m--) {
  111. 		cin >> op >> l >> r;
  112. 		if (op == 1) {
  113. 			modify(1, l, r, l - 1);
  114. 		}
  115. 		else {
  116. 			cout << query(1, l, r) << endl;
  117. 		}
  118. 	}
  119. 	return 0;
  120. }
  121. /*
  122. 4 5
  123. 2 1 4
  124. 1 1 4
  125. 2 1 4
  126. 1 3 4
  127. 2 1 4
  128. 4 5
  129. 2 1 4
  130. 1 3 4
  131. 2 1 4
  132. 1 1 4
  133. 2 1 4
  134. */

K    智乃酱的双塔问题·改（线段树，dp，矩阵连乘)

解析：

不能发现这个问题如果不带修改则可以用 dp+前缀和（矩阵乘法）解决，带修改则可以用线段树维护区间和。

令 f[i][0/1] 表示从第 1 层的左边（0）或右边（1）到第 i 层的左边（0）或右边（1）的方案数

我们可以将每一层的转移状态用矩阵表示，

  1. #include <iostream>
  2. #include <string>
  3. #include <cstring>
  4. #include <cmath>
  5. #include <ctime>
  6. #include <algorithm>
  7. #include <utility>
  8. #include <stack>
  9. #include <queue>
  10. #include <vector>
  11. #include <set>
  12. #include <math.h>
  13. #include <map>
  14. #include <sstream>
  15. #include <deque>
  16. #include <unordered_map>
  17. #include <unordered_set>
  18. #include <bitset>
  19. #include <stdio.h>
  20. #include <tuple>
  21. using namespace std;
  22. /*
  23. ios::sync_with_stdio(false);
  24. cin.tie(nullptr);
  25. cout.tie(nullptr);
  26. */
  27. typedef long long LL;
  28. //#define int long long
  29. #define ld long double
  30. //#define INT __int128
  31. const LL INF = 0x3f3f3f3f3f3f3f3f;
  32. typedef unsigned long long ULL;
  33. typedef pair<long long, long long> PLL;
  34. typedef pair<int, int> PII;
  35. typedef pair<double, double> PDD;
  36. const int inf = 0x3f3f3f3f;
  37. const LL mod = 1e9 + 7;
  38. const ld eps = 1e-12;
  39. const int N = 2e5 + 10, M = N + 10;
  40. int n, m;
  41. char s[N];
  42. struct MATRIX {
  43. 	LL a[2][2];
  44. 	void init(int b1,int b2,int b3,int b4) {
  45. 		a[0][0] = b1, a[0][1] = b2;
  46. 		a[1][0] = b3, a[1][1] = b4;
  47. 	}
  48. 	MATRIX operator*(MATRIX oth) {
  49. 		MATRIX ret;
  50. 		ret.init(0, 0, 0, 0);
  51. 		for (int i = 0; i < 2; i++) {
  52. 			for (int j = 0; j < 2; j++) {
  53. 				for (int k = 0; k < 2; k++) {
  54. 					(ret.a[i][j] += a[i][k] * oth.a[k][j] % mod) %= mod;
  55. 				}
  56. 			}
  57. 		}
  58. 		return ret;
  59. 	}
  60. };
  61.  
  62. struct TREE {
  63. 	int l, r;
  64. 	MATRIX ma;
  65. }tr[N << 2];
  66. #define ls u<<1
  67. #define rs u<<1|1
  68. void up(int u) {
  69. 	tr[u].ma = tr[ls].ma * tr[rs].ma;
  70. }
  71. void build(int u, int l, int r) {
  72. 	tr[u].l = l, tr[u].r = r;
  73. 	if (l == r) {
  74. 		tr[u].ma.init(1, s[l] == '/', s[l] != '/', 1);
  75. 		return;
  76. 	}
  77. 	int mid = l + r >> 1;
  78. 	build(ls, l, mid), build(rs, mid + 1, r);
  79. 	up(u);
  80. }
  81. void modify(int u, int pos, char ch) {
  82. 	if (tr[u].l == tr[u].r) {
  83. 		tr[u].ma.init(1, ch == '/', ch != '/', 1);
  84. 		return;
  85. 	}
  86. 	int mid = tr[u].l + tr[u].r >> 1;
  87. 	if (pos <= mid)modify(ls, pos, ch);
  88. 	if (pos > mid)modify(rs, pos, ch);
  89. 	up(u);
  90. }
  91. MATRIX query(int u, int l, int r) {
  92. 	if (l <= tr[u].l && tr[u].r <= r) {
  93. 		return tr[u].ma;
  94. 	}
  95. 	int mid = tr[u].l + tr[u].r >> 1;
  96. 	MATRIX ret;
  97. 	ret.init(1, 0, 0, 1);
  98. 	if (l <= mid)ret = (ret * query(ls, l, r));
  99. 	if (r > mid)ret = (ret * query(rs, l, r));
  100. 	return ret;
  101. }
  102. signed main() {
  103. 	cin >> n >> m;
  104. 	scanf("%s", s + 1);
  105. 	build(1, 1, n - 1);
  106. 	int op, ht, hs, h;
  107. 	for (int i = 1; i <= m; i++) {
  108. 		scanf("%d", &op);
  109. 		if (op == 0) {
  110. 			char c[2];
  111. 			scanf("%d%s",&h, c);
  112. 			modify(1, h,c[0]);
  113. 		}
  114. 		else {
  115. 			int ps, pt;
  116. 			scanf("%d%d%d%d",&hs,&ht, &ps, &pt);
  117. 			auto ret = query(1, hs, ht - 1);
  118. 			/*cout << "__________________" << endl;
  119. 			for (int i = 0; i < 2; i++) {
  120. 				cout << ret.a[i][0] << " " << ret.a[i][1] << endl;
  121. 			}
  122. 			cout << endl;*/
  123. 			LL ans = ret.a[ps][pt];
  124. 			printf("%lld\n", ans);
  125. 		}
  126. 	}
  127. 	return 0;
  128. }

J    智乃酱的双塔问题·极（带修改的DP，DDP）

这题思路与上题一样，只不过将矩阵的乘法运算换成 floyd 算法，矩阵的含义变为图的邻接矩阵。（可以变的主要原因是因为 floyd 算法的运算形式与矩阵连乘的形式很相似）

  1. #include <iostream>
  2. #include <string>
  3. #include <cstring>
  4. #include <cmath>
  5. #include <ctime>
  6. #include <algorithm>
  7. #include <utility>
  8. #include <stack>
  9. #include <queue>
  10. #include <vector>
  11. #include <set>
  12. #include <math.h>
  13. #include <map>
  14. #include <sstream>
  15. #include <deque>
  16. #include <unordered_map>
  17. #include <unordered_set>
  18. #include <bitset>
  19. #include <stdio.h>
  20. #include <tuple>
  21. using namespace std;
  22. /*
  23. ios::sync_with_stdio(false);
  24. cin.tie(nullptr);
  25. cout.tie(nullptr);
  26. */
  27. typedef long long LL;
  28. //#define int long long
  29. #define ld long double
  30. //#define INT __int128
  31. const LL INF = 0x3f3f3f3f3f3f3f3f;
  32. typedef unsigned long long ULL;
  33. typedef pair<long long, long long> PLL;
  34. typedef pair<int, int> PII;
  35. typedef pair<double, double> PDD;
  36. const int inf = 0x3f3f3f3f;
  37. const LL mod = 1e9 + 7;
  38. const ld eps = 1e-12;
  39. const int N = 1e5 + 10, M = N + 10;
  40. int n, m;
  41. int val[N][3];
  42. char s[N];
  43. #define inf INF
  44. struct MATRIX {
  45. 	LL a[2][2];
  46. 	void init(LL b1, LL b2, LL b3, LL b4) {
  47. 		a[0][0] = b1, a[0][1] = b2;
  48. 		a[1][0] = b3, a[1][1] = b4;
  49. 	}
  50. 	MATRIX operator*(MATRIX oth) {
  51. 		MATRIX ret;
  52. 		ret.init(inf, inf, inf, inf);
  53. 		for (int i = 0; i < 2; i++) {
  54. 			for (int j = 0; j < 2; j++) {
  55. 				for (int k = 0; k < 2; k++) {
  56. 					//(ret.a[i][j] += a[i][k] * oth.a[k][j] % mod) %= mod;
  57. 					if (a[i][k] == inf || oth.a[k][j] == inf)continue;
  58. 					ret.a[i][j] = min(ret.a[i][j], (a[i][k] + oth.a[k][j]));
  59. 				}
  60. 			}
  61. 		}
  62. 		return ret;
  63. 	}
  64. };
  65.  
  66. struct TREE {
  67. 	int l, r;
  68. 	MATRIX ma;
  69. }tr[N << 2];
  70. #define ls u<<1
  71. #define rs u<<1|1
  72. void up(int u) {
  73. 	tr[u].ma = tr[ls].ma * tr[rs].ma;
  74. }
  75. void build(int u, int l, int r) {
  76. 	tr[u].l = l, tr[u].r = r;
  77. 	if (l == r) {
  78. 		if (s[l] == '/')
  79. 			tr[u].ma.init(val[l][0], val[l][2], inf, val[l][1]);
  80. 		else tr[u].ma.init(val[l][0], inf, val[l][2], val[l][1]);
  81. 		return;
  82. 	}
  83. 	int mid = l + r >> 1;
  84. 	build(ls, l, mid), build(rs, mid + 1, r);
  85. 	up(u);
  86. }
  87. void modify(int u, int pos, char ch, int val1, int val2, int val3) {
  88. 	if (tr[u].l == tr[u].r) {
  89. 		if (ch == '/')
  90. 			tr[u].ma.init(val1, val3, inf, val2);
  91. 		else tr[u].ma.init(val1, inf, val3, val2);
  92. 		return;
  93. 	}
  94. 	int mid = tr[u].l + tr[u].r >> 1;
  95. 	if (pos <= mid)modify(ls, pos, ch, val1, val2, val3);
  96. 	if (pos > mid)modify(rs, pos, ch, val1, val2, val3);
  97. 	up(u);
  98. }
  99. MATRIX query(int u, int l, int r) {
  100. 	if (l <= tr[u].l && tr[u].r <= r) {
  101. 		return tr[u].ma;
  102. 	}
  103. 	int mid = tr[u].l + tr[u].r >> 1;
  104. 	MATRIX ret;
  105. 	ret.init(0, inf, inf, 0);
  106. 	if (l <= mid)ret = ret * query(ls, l, r);
  107. 	if (r > mid)ret = ret * query(rs, l, r);
  108. 	return ret;
  109. }
  110. signed main() {
  111. 	cin >> n >> m;
  112. 	scanf("%s", s + 1);
  113. 	for (int i = 1; i < n; i++) {
  114. 		scanf("%d%d%d", &val[i][0], &val[i][1], &val[i][2]);
  115. 	}
  116. 	build(1, 1, n - 1);
  117. 	int op, ht, hs, h;
  118. 	for (int i = 1; i <= m; i++) {
  119. 		scanf("%d", &op);
  120. 		if (op == 0) {
  121. 			char c[2];
  122. 			scanf("%d%s", &h, c);
  123. 			//cout << "______" << c[0] << endl;
  124. 			s[h] = c[0];
  125. 			modify(1, h, c[0], val[h][0], val[h][1], val[h][2]);
  126. 		}
  127. 		else if (op == 1) {
  128. 			int val1, val2, val3;
  129. 			scanf("%d%d%d%d", &h, &val1, &val2, &val3);
  130. 			val[h][0] = val1, val[h][1] = val2, val[h][2] = val3;
  131. 			modify(1, h, s[h], val1, val2, val3);
  132. 		}
  133. 		else {
  134. 			int ps, pt;
  135. 			scanf("%d%d%d%d", &hs, &ht, &ps, &pt);
  136. 			auto ret = query(1, hs, ht - 1);
  137. 			/*cout << "__________________" << endl;
  138. 			for (int i = 0; i < 2; i++) {
  139. 				cout << ret.a[i][0] << " " << ret.a[i][1] << endl;
  140. 			}
  141. 			cout << endl;*/
  142. 			LL ans = ret.a[ps][pt];
  143. 			if (ans == inf) {
  144. 				printf("-1\n");
  145. 			}
  146. 			else
  147. 				printf("%lld\n", ans);
  148. 		}
  149. 	}
  150. 	return 0;
  151. }
  152.  
  153. /*
  154. 4 13
  155. ///
  156. 1 2 1
  157. 2 3 5
  158. 8 8 1
  159. 2 1 4 1 0
  160. 2 1 2 1 0
  161. 2 2 3 1 0
  162. 2 3 4 1 0
  163. 0 3 \
  164. 2 1 4 0 0
  165. 2 2 4 0 0
  166. 2 2 4 0 1
  167. 2 3 4 0 1
  168. 2 3 4 1 0
  169. 1 1 1 1 1
  170. 1 2 1 1 1
  171. 1 3 1 1 1
  172. 2 1 4 1 0
  173. 0 3 /
  174. 2 1 4 1 0
  177. 4 13
  178. ///
  179. 1 2 1
  180. 2 3 5
  181. 8 8 1
  182. 2 1 4 1 0
  183. 0 3 \
  184. 2 1 4 0 0
  185. 2 2 4 0 0
  186. 2 2 4 0 1
  187. 2 3 4 0 1
  188. 2 3 4 1 0
  189. 1 1 1 1 1
  190. 1 2 1 1 1
  191. 1 3 1 1 1
  192. 2 1 4 1 0
  193. 0 3 /
  194. 2 1 4 1 0
  195. */

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/weixin_40725706/article/detail/1001619
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号