Hướng dẫn giải của Phát thưởng
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
Mỗi lượt phát quà cộng thêm ~K~ cho các bạn từ ~L~ đến ~R~. Với mỗi câu hỏi vị trí ~P~, cần tổng các ~K~ của những lượt có ~L \le P \le R~.
Sub 1: Vét cạn — ~O(n \cdot m)~, dùng khi ~n \le 1000~
Cộng trực tiếp ~K~ vào từng bạn trong đoạn ~[L; R]~ của mỗi lượt, sau đó trả lời mỗi câu hỏi bằng một lần tra mảng. Nếu chỉ nộp sub này: đúng 6/20 test.
Sub 2: Mảng hiệu — ~O(n + m + Q)~, dùng khi ~n \le 10^6~
Cộng ~K~ tại vị trí ~L~ và trừ ~K~ tại vị trí ~R+1~, rồi cộng dồn để có giá trị từng bạn. Nếu chỉ nộp sub này: đúng 12/20 test.
Sub 3: Fenwick tree trên tọa độ nén — ~O((m + Q) \log m)~, không phụ thuộc ~n~
Khi ~n~ lên đến ~10^9~ không thể lưu mảng. Ta chỉ nén các mốc ~L~, ~R+1~ và vị trí hỏi, rồi dùng cây Fenwick để lấy tổng tiền tố của mảng hiệu. Nếu chỉ nộp sub này: đúng 20/20 test.
Chương trình hoàn chỉnh
Đọc dữ liệu, chọn sub theo ~n~: ~n \le 1000~ dùng sub 1, ~n \le 10^6~ dùng sub 2, còn lại dùng sub 3. Khi đi thi nên viết như vậy: sub sau có sai hoặc chưa kịp làm thì vẫn ăn điểm sub trước.
#include <bits/stdc++.h>
using namespace std;
long long n; // so ban
int m, Q; // so luot phat qua, so cau hoi
vector<long long> Lv, Rv, Kv, Pv; // luot i: tu L den R, gia tri K; cau hoi: vi tri P
// Sub 1: cong truc tiep K vao tung ban trong [L, R] — dung khi n <= 1000
void sub1() {
vector<long long> a(n + 2, 0);
for (int i = 0; i < m; i++)
for (long long p = Lv[i]; p <= Rv[i]; p++) a[p] += Kv[i];
for (int i = 0; i < Q; i++) cout << a[Pv[i]] << "\n";
}
// Sub 2: mang hieu — cong K tai L, tru K tai R+1, roi cong don — dung khi n <= 10^6
void sub2() {
vector<long long> d(n + 2, 0);
for (int i = 0; i < m; i++) { d[Lv[i]] += Kv[i]; d[Rv[i] + 1] -= Kv[i]; }
for (long long i = 1; i <= n + 1; i++) d[i] += d[i - 1];
for (int i = 0; i < Q; i++) cout << d[Pv[i]] << "\n";
}
// Sub 3: day du — nen cac moc L, R+1 roi dung Fenwick tree tren diem sai phan
void sub3() {
vector<long long> xs;
for (int i = 0; i < m; i++) { xs.push_back(Lv[i]); xs.push_back(Rv[i] + 1); }
sort(xs.begin(), xs.end());
xs.erase(unique(xs.begin(), xs.end()), xs.end());
int S = xs.size();
vector<long long> bit(S + 1, 0);
auto add = [&](int i, long long v) { for (i++; i <= S; i += i & -i) bit[i] += v; };
auto prefix = [&](int i) { long long s = 0; for (i++; i > 0; i -= i & -i) s += bit[i]; return s; };
for (int i = 0; i < m; i++) {
add(lower_bound(xs.begin(), xs.end(), Lv[i]) - xs.begin(), Kv[i]);
add(lower_bound(xs.begin(), xs.end(), Rv[i] + 1) - xs.begin(), -Kv[i]);
}
for (int i = 0; i < Q; i++) {
int idx = upper_bound(xs.begin(), xs.end(), Pv[i]) - xs.begin() - 1; // moc lon nhat <= P
cout << (idx < 0 ? 0 : prefix(idx)) << "\n";
}
}
int main() {
ios::sync_with_stdio(false); cin.tie(nullptr);
cin >> n >> m >> Q;
Lv.resize(m); Rv.resize(m); Kv.resize(m); Pv.resize(Q);
for (int i = 0; i < m; i++) cin >> Lv[i] >> Rv[i] >> Kv[i];
for (int i = 0; i < Q; i++) cin >> Pv[i];
if (n <= 1000) sub1();
else if (n <= 1000000) sub2();
else sub3();
return 0;
}
Bình luận