Hướng dẫn giải của Cập nhật dãy (Đề HSG 12 Phú Thọ 2021-2022)
Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Hướng dẫn giải
Có ~m~ lệnh cộng ~k~ vào các phần tử ~a_i, ..., a_j~ của dãy ban đầu toàn số 0. Cho biết dãy sau cùng.
Sub 1: Cộng trực tiếp — ~O(n \cdot m)~, dùng khi ~n, m \le 10^4~
Mỗi lệnh duyệt từ ~i~ đến ~j~ và cộng ~k~ vào từng phần tử. Đơn giản, đúng, nhưng chậm khi dữ liệu lớn.
Nếu chỉ nộp sub này: đúng 15/20 test.
Sub 2: Mảng hiệu — ~O(n + m)~
Mỗi lệnh chỉ sửa hai ô: cộng ~k~ vào ~d_i~ và trừ ~k~ khỏi ~d_{j+1}~. Cuối cùng lấy tổng cộng dồn ~d_1 + ... + d_p~ là giá trị ~a_p~. Giá trị có thể lên tới ~10^{10}~ nên dùng long long.
Nếu chỉ nộp sub này: đúng 20/20 test.
Chương trình hoàn chỉnh
Hàm main đọc dữ liệu rồi chọn sub theo kích thước: dữ liệu nhỏ gọi sub 1 (vét cạn), dữ liệu lớn gọi sub cuối. Khi đi thi, nên nộp đầy đủ như vậy: nếu sub sau sai hoặc chưa kịp làm thì vẫn ăn điểm các sub trước.
#include <bits/stdc++.h>
using namespace std;
int n, m;
vector<int> I, J;
vector<long long> K;
// Sub 1: vét cạn — mỗi lệnh cộng trực tiếp k vào từng phần tử của đoạn [i, j]. O(n*m)
void sub1() {
vector<long long> a(n + 1, 0);
for (int t = 0; t < m; t++)
for (int p = I[t]; p <= J[t]; p++) a[p] += K[t];
for (int p = 1; p <= n; p++) cout << a[p] << (p == n ? "\n" : " ");
}
// Sub 2: mảng hiệu — mỗi lệnh chỉ sửa 2 ô, cuối cùng lấy tổng cộng dồn. O(n + m)
void sub2() {
vector<long long> d(n + 2, 0);
for (int t = 0; t < m; t++) {
d[I[t]] += K[t];
d[J[t] + 1] -= K[t];
}
long long cur = 0;
for (int p = 1; p <= n; p++) {
cur += d[p];
cout << cur << (p == n ? "\n" : " ");
}
}
int main() {
freopen("UDTSEQ.INP", "r", stdin);
freopen("UDTSEQ.OUT", "w", stdout);
ios::sync_with_stdio(false); cin.tie(nullptr);
cin >> n >> m;
I.resize(m); J.resize(m); K.resize(m);
for (int t = 0; t < m; t++) cin >> I[t] >> J[t] >> K[t];
if (n <= 10000 && m <= 10000) sub1(); // dữ liệu nhỏ: cộng trực tiếp
else sub2();
return 0;
}
Bình luận