fork download
copy 
  1. // Cho mảng a độ dài n, xây dựng mảng sum là tổng tiền tố của mảng a  
  2. // ta có công thức: 
  3. // 	sum[0] = 0;   
  4. // 	sum[i] = sum[i - 1] + a[i]; i >= 1  
  5.  
  6. // sum[i] tổng của i phần tử đầu tiên của a  
  7.  
  8. // sum[0] = 0;  
  9. // for (int i = 1; i <= n; i++) sum[i] = sum[i - 1] + a[i]; 
  10.  
  11. // lấy tổng của đoạn [l, r]: sum[r] - sum[l - 1]
  12.  
  13. // Cho mảng a ban đầu có n phần tử có giá trị là 0 
  14. // cho Q truy vấn, mỗi truy vấn là tăng đoạn [l, r] của a lên x đơn vị 
  15. // Hỏi sau Q truy vấn thì các phần tử của a có giá trị bao nhiêu?
  16.  
  17. // n = 3 
  18. // a = [0, 0, 0] 
  19.  
  20. // Q = 2 
  21. // 1 2 3 -> tăng đoạn [1, 2] lên 3 đơn vị 
  22. // 1 3 5 -> tăng đoạn [1, 3] lên 5 đơn vị 
  23.  
  24. // -> a = [8, 8, 5] 
  25.  
  26. // thuật toán ngây thơ: O(Q * N)
  27.  
  28. // for (int i = 1; i <= Q; i++) {
  29. // 	int l, r, x; 
  30. // 	cin >> l >> r >> x;   
  31. // 	for (int j = l; j <= r; j++) a[j] += x;  
  32. // }
  33.  
  34. // phiên bản 2 của tổng tiền tố: O()
  35. // Giờ đã có mảng sum[] của a[], nếu ta tăng phần tử thứ i của a 
  36. // lên x đơn vị thì mảng sum[] thay đổi như thế nào?
  37.  
  38. //   a = [   1, 2, 4, 10]
  39. // sum = [0, 1, 3, 7, 17]
  40.  
  41. // tăng a[3] lên 4 đơn vị, thì mảng sum thay đổi như thế nào?
  42.  
  43.  
  44. //   a = [   1, 2,  8, 10]
  45. // sum = [0, 1, 3, 11, 21]
  46.  
  47. // giả sử tiếp tục tăng a[2] lên 3 đơn vị thì mảng sum[]
  48. // thay đổi như nào?  
  49.  
  50. //   a = [   1, 5, 8,  10]
  51. // sum = [0, 1, 6, 14, 24]
  52.  
  53. // => Nhận xét: nếu ta tăng phần tử thứ i của a lên x đơn vị,  
  54. // thì đoạn [i, n] của mảng sum cũng tăng lên x đơn vị.  
  55.  
  56.  
  57. // => Quay trở lại bài toán ban đầu, nếu ta muốn tăng đoạn [l, r]  
  58. // lên x đơn vị
  59.  
  60. // for (int i = 1; i <= Q; i++) { O(Q)
  61. // 	int l, r, x; 
  62. // 	cin >> l >> r >> x; 
  63. // 	a[l] += x; O(1)
  64. // 	a[r + 1] -= x; O(1)  
  65. // }
  66.  
  67. // for (int i = 1; i <= n; i++) a[i] += a[i - 1]; O(n)  
  68. // => O(Q + N)
  69.  
  70. #include <bits/stdc++.h>
  71. using namespace std; 
  72.  
  73. #define fst first
  74. #define snd second 
  75.  
  76. typedef long long ll; 
  77. typedef pair<int, int> ii; 
  78.  
  79. const ll LINF = (ll)1e18; 
  80. const int INF = (int)1e9;
  81.  
  82. const int N = (int)1e5 + 5;  
  83.  
  84. int n, Q; 
  85. int a[N];  
  86.  
  87. int main() {
  88. 	ios::sync_with_stdio(0); 
  89. 	cin.tie(0); 
  90. 	cin >> n; 
  91. 	cin >> Q;  
  92.  
  93. 	for (int i = 1; i <= Q; i++) {
  94. 		int l, r, x; 
  95. 		cin >> l >> r >> x;  
  96. 		a[l] += x;  
  97. 		a[r + 1] -= x;  
  98. 	}
  99.  
  100. 	for (int i = 1; i <= n; i++) a[i] += a[i - 1];   
  101.  
  102. 	cout << "Mang a sau Q truy van la:\n";
  103. 	for (int i = 1; i <= n; i++) cout << a[i] << ' '; cout << '\n';
  104. }
Success #stdin #stdout 0.01s 5304KB
comments (?)
stdin
copy 
3
2
1 2 3
1 3 5
stdout
copy 
Mang a sau Q truy van la:
8 8 5
https://ideone.com/emriDj
language:
C++14 (gcc 8.3)
created:
1 year ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!