Hướng dẫn giải của [Beginner Free Contest 04] INCPOS
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
Yêu cầu: cho dãy ~A~, mỗi truy vấn cộng ~x~ vào đoạn ~[l, r]~; sau mỗi truy vấn đếm số vị trí ~i~ có ~A_i > A_{i+1}~.
Sub 1: Cập nhật trực tiếp — ~O(N \cdot Q)~, dùng khi ~N, Q \le 2000~
Cộng ~x~ vào từng phần tử của đoạn, rồi đếm lại toàn bộ vị trí tăng.
Nếu chỉ nộp sub này: đúng 4/10 test.
Sub 2: Theo hiệu liền kề — ~O(N + Q)~
Đặt ~d_i = A_{i+1} - A_i~. Cộng ~x~ vào ~A[l..r]~ chỉ đổi ~d_{l-1}~ (cộng ~x~) và ~d_r~ (trừ ~x~). Vị trí ~i~ là vị trí tăng khi ~d_i < 0~, nên mỗi truy vấn cập nhật đếm trong ~O(1)~.
Nếu chỉ nộp sub này: đúng 10/10 test.
Chương trình hoàn chỉnh
Với ~N, Q \le 2000~ gọi sub 1, còn lại gọi sub 2. 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;
int N, Q;
vector<long long> A; // A[1..N]
vector<int> L, R; // truy vấn thứ q: đoạn [L[q], R[q]]
vector<long long> X; // và giá trị cộng thêm X[q]
// Sub 1: cộng trực tiếp rồi đếm lại O(N*Q) — dùng khi N, Q <= 2000
void sub1() {
for (int q = 0; q < Q; q++) {
for (int i = L[q]; i <= R[q]; i++) A[i] += X[q];
int cnt = 0;
for (int i = 1; i < N; i++)
if (A[i] > A[i + 1]) cnt++;
cout << cnt << "\n";
}
}
// Sub 2: theo hiệu d[i] = A[i+1] - A[i] — lời giải đầy đủ
// Cộng x vào A[l..r] chỉ đổi d[l-1] (+x) và d[r] (-x). Vị trí i tăng <=> d[i] < 0.
void sub2() {
vector<long long> d(N + 1, 0);
int cnt = 0;
for (int i = 1; i < N; i++) {
d[i] = A[i + 1] - A[i];
if (d[i] < 0) cnt++;
}
for (int q = 0; q < Q; q++) {
int l = L[q], r = R[q];
long long x = X[q];
if (l > 1) {
int i = l - 1;
if (d[i] < 0) cnt--;
d[i] += x;
if (d[i] < 0) cnt++;
}
if (r < N) {
int i = r;
if (d[i] < 0) cnt--;
d[i] -= x;
if (d[i] < 0) cnt++;
}
cout << cnt << "\n";
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> N >> Q;
A.assign(N + 2, 0);
for (int i = 1; i <= N; i++) cin >> A[i];
L.resize(Q);
R.resize(Q);
X.resize(Q);
for (int q = 0; q < Q; q++) cin >> L[q] >> R[q] >> X[q];
if (N <= 2000 && Q <= 2000) sub1();
else sub2();
return 0;
}
Bình luận