Hướng dẫn giải của Đếm vị trí tă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.
Lời giải này đang bị ẩn cho đến khi bạn chọn mở ra.
Chúng tôi khuyên bạn nên tự thử giải bài trước. Việc mở lời giải có thể làm lộ mất ý tưởng chính trước khi bạn có cơ hội tự giải.
Bạn phải đăng nhập để mở lời giải này.
Đăng nhập
Tác giả: Hiếu Nguyễn
, , ,
Editorial for incpos: Đếm vị trí tăng
Hiểu bài toán
Bài toán yêu cầu xử lý một dãy số A độ dài N. Định nghĩa một vị trí i (1 ≤ i < N) là 'vị trí tăng' nếu A[i] > A[i+1].
Có Q truy vấn, mỗi truy vấn cung cấp (l, r, x) để cộng x vào tất cả phần tử từ chỉ số l đến r. Sau mỗi truy vấn, ta cần in ra số lượng vị trí tăng của dãy số hiện tại.
Giới hạn: N, Q ≤ 200,000.
Ví dụ: Dãy [5, 3, 4] có 1 vị trí tăng là i=1 (vì 5 > 3). Vị trí i=2 không tăng (3 <= 4).
Các cách tiếp cận
Cách Quy hoạch động thay đổi (Delta Update)
#include <iostream>
#include <vector>
using namespace std;
int main() {
int N, Q;
if (!(cin >> N >> Q)) return 0;
vector<long long> A(N + 1);
for (int i = 1; i <= N; ++i) cin >> A[i];
// D[i] = A[i] - A[i+1]
// A[i] > A[i+1] <=> D[i] > 0
vector<long long> D(N + 1, 0);
int ans = 0;
// Tính mảng D và số lượng ban đầu
for (int i = 1; i < N; ++i) {
D[i] = A[i] - A[i+1];
if (D[i] > 0) ans++;
}
while (Q--) {
int l, r, x;
cin >> l >> r >> x;
// Cập nhật D[r]: A[r] tang them x -> D[r] = (A[r] + x) - A[r+1] = D[r] + x
// Chỉ cập nhật nếu r < N
if (r < N) {
if (D[r] > 0) ans--; // Loại bỏ vị trí cũ nếu có
D[r] += x;
if (D[r] > 0) ans++; // Thêm vị trí mới nếu thỏa mãn
}
// Cập nhật D[l-1]: A[l-1] không đổi, A[l] tang them x -> D[l-1] = A[l-1] - (A[l] + x) = D[l-1] - x
// Chỉ cập nhật nếu l > 1
if (l > 1) {
if (D[l-1] > 0) ans--;
D[l-1] -= x;
if (D[l-1] > 0) ans++;
}
cout << ans << "\n";
}
return 0;
}
- Time Complexity: O(N + Q)
- Space Complexity: O(N)
Phương pháp này dựa trên nhận xét quan trọng: Khi cộng x vào đoạn [l, r], chỉ có hai ranh giới bị ảnh hưởng đến thứ tự tương đối:
- Vị trí l-1 (nếu l > 1): So sánh A[l-1] và A[l].
- Vị trí r (nếu r < N): So sánh A[r] và A[r+1].
Tất cả các vị trí ở giữa đoạn [l, r-1] đều được cộng thêm x cả hai bên, nên hiệu số A[i] - A[i+1] không thay đổi.
Ta duy trì mảng hiệu D[i] = A[i] - A[i+1]. Danh sách vị trí tăng chính là số lượng phần tử D[i] > 0. Với mỗi truy vấn, ta chỉ cần cập nhật D[l-1] và D[r] rồi cập nhật biến đếm ans một cách tức thì. Độ phức tạp O(1) cho mỗi truy vấn.
Cách Fenwick Tree & Set (Dynamic Maintenance)
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 200005;
long long A[MAXN];
long long bit[MAXN];
int N, Q;
void update_bit(int idx, long long val) {
for (; idx <= N; idx += idx & -idx) bit[idx] += val;
}
long long get_delta(int idx) {
long long sum = 0;
for (; idx > 0; idx -= idx & -idx) sum += bit[idx];
return sum;
}
long long get_current_A_value(int i) {
return A[i] + get_delta(i);
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
if (!(cin >> N >> Q)) return 0;
for (int i = 1; i <= N; ++i) cin >> A[i];
// Duy trì set chứa các chỉ số i mà A[i] > A[i+1]
set<int> increasing;
for (int i = 1; i < N; ++i) {
if (A[i] > A[i+1]) increasing.insert(i);
}
while (Q--) {
int l, r, x;
cin >> l >> r >> x;
// Cập nhật BIT
update_bit(l, x);
if (r + 1 <= N) update_bit(r + 1, -x);
// Kiểm tra và cập nhật các ranh giới bị ảnh hưởng
// Danh sách các chỉ số cần kiểm tra: l-1, l, r, r+1
vector<int> check_indices;
if (l > 1) check_indices.push_back(l - 1);
if (r < N) check_indices.push_back(r);
if (l > 1) check_indices.push_back(l); // Mới
if (r < N) check_indices.push_back(r + 1); // Mới
for (int idx : check_indices) {
// Xóa chỉ số cũ khỏi set
if (idx >= 1 && idx < N && increasing.count(idx)) {
increasing.erase(idx);
}
// Kiểm tra điều kiện mới
long long val1 = get_current_A_value(idx);
long long val2 = get_current_A_value(idx + 1);
if (val1 > val2) {
increasing.insert(idx);
}
}
cout << increasing.size() << "\n";
}
return 0;
}
- Time Complexity: O(Q log N)
- Space Complexity: O(N)
Sử dụng Fenwick Tree (Binary Indexed Tree) để xử lý Range Update và Point Query. Sau mỗi truy vấn, ta xác định các vị trí có thể thay đổi trạng thái (các ranh giới l-1, l, r, r+1).
Duy trì một cấu trúc set chứa các chỉ số i đang thỏa mãn A[i] > A[i+1]. Với mỗi truy vấn:
- Cập nhật BIT.
- Xóa các chỉ số liên quan khỏi set.
- Lấy giá trị mới từ BIT và thêm vào set nếu thỏa mãn.
Độ phức tạp O(log N) cho mỗi truy vấn do thao tác set và BIT.
Cách Brute Force
// Pseudocode for Brute Force
int main() {
cin >> N >> Q;
for (int i = 1; i <= N; i++) cin >> A[i];
while (Q--) {
int l, r, x; cin >> l >> r >> x;
// Update
for (int i = l; i <= r; i++) A[i] += x;
// Count
int ans = 0;
for (int i = 1; i < N; i++) {
if (A[i] > A[i+1]) ans++;
}
cout << ans << "\n";
}
}
- Time Complexity: O(N * Q)
- Space Complexity: O(N)
Duyệt mảng để cập nhật giá trị, sau đó duyệt lại toàn bộ mảng để đếm số vị trí tăng. Cách này chỉ phù hợp với N, Q nhỏ (subtask 1).
Phân tích độ phức tạp
| Cách tiếp cận | Time | Space | Tên |
|---|---|---|---|
| 1 | O(N + Q) | O(N) | Quy hoạch động thay đổi (Delta Update) |
| 2 | O(Q log N) | O(N) | Fenwick Tree & Set (Dynamic Maintenance) |
| 3 | O(N * Q) | O(N) | Brute Force |
Bài học kinh nghiệm
- Sự thay đổi của một truy vấn Range Add chỉ ảnh hưởng trực tiếp đến 2 vị trí ranh giới: l-1 và r (so sánh phần tử trước và sau vùng cập nhật). Các vị trí nằm giữa vùng cập nhật không thay đổi thứ tự tương đối.
- Bài toán có thể được chuyển đổi sang việc theo dõi mảng hiệu D[i] = A[i] - A[i+1]. Một vị trí tăng tương ứng với D[i] > 0.
Lỗi thường gặp
- Quên kiểm tra ranh giới của mảng (ví dụ: l=1 thì không có phần tử trước, r=N thì không có phần tử sau) dẫn đến truy cập ngoài vùng nhớ.
- Sử dụng biến lưu kết quả trung gian không đúng cách (nếu bạn tính lại toàn bộ ans từ đầu trong mỗi truy vấn mà không dùng delta update).
- Lỗi số nguyên (integer overflow) khi A[i] và x có giá trị lớn. Cần sử dụng kiểu dữ liệu 64-bit (long long).
Bình luận