Hướng dẫn giải của Đếm số nghịch thế
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 magb: Đếm số nghịch thế
Hiểu bài toán
Bài toán yêu cầu đếm số lượng cặp nghịch thế trong một dãy số. Cặp nghịch thế được định nghĩa là một cặp chỉ số (i, j) sao cho i < j và ai > aj. Với n lên tới 100,000, giải thuật O(n^2) sẽ không khả thi. Cần sử dụng các thuật toán hiệu quả hơn như Merge Sort hoặc cây Fenwick (BIT) để đếm các cặp nghịch thế trong thời gian O(n log n).
Các cách tiếp cận
Cách Brute Force (Đối sánh mọi cặp)
#include <iostream>
#include <vector>
using namespace std;
int main() {
int n;
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; ++i) {
cin >> a[i];
}
long long ans = 0;
for (int i = 0; i < n; ++i) {
for (int j = i + 1; j < n; ++j) {
if (a[i] > a[j]) {
ans++;
}
}
}
cout << ans << endl;
return 0;
}
- Time Complexity: O(n^2)
- Space Complexity: O(1)
Giải thuật này sử dụng hai vòng lặp lồng nhau để duyệt qua tất cả các cặp (i, j) thỏa mãn i < j. Với mỗi cặp, ta kiểm tra điều kiện a[i] > a[j]. Nếu thỏa mãn thì tăng biến đếm. Giải thuật này đơn giản nhưng rất chậm, chỉ phù hợp với n nhỏ (< 10^4). Với n = 10^5, thời gian chạy khoảng 10^10 thao tác, vượt quá giới hạn.
Cách Merge Sort (Phân chia - Đếm)
#include <stdio.h>
#include <stdlib.h>
long long merge(int arr[], int temp[], int left, int mid, int right) {
int i = left;
int j = mid + 1;
int k = left;
long long inv_count = 0;
while ((i <= mid) && (j <= right)) {
if (arr[i] <= arr[j]) {
temp[k++] = arr[i++];
} else {
temp[k++] = arr[j++];
// Nếu arr[i] > arr[j], thì tất cả phần tử còn lại trong mảng con trái
// (từ arr[i] đến arr[mid]) đều lớn hơn arr[j].
inv_count += (long long)(mid - i + 1);
}
}
while (i <= mid)
temp[k++] = arr[i++];
while (j <= right)
temp[k++] = arr[j++];
for (i = left; i <= right; i++)
arr[i] = temp[i];
return inv_count;
}
long long mergeSort(int arr[], int temp[], int left, int right) {
long long inv_count = 0;
if (left < right) {
int mid = (left + right) / 2;
inv_count += mergeSort(arr, temp, left, mid);
inv_count += mergeSort(arr, temp, mid + 1, right);
inv_count += merge(arr, temp, left, mid, right);
}
return inv_count;
}
int main() {
int n;
if (scanf("%d", &n) != 1) return 1;
int* arr = (int*)malloc(n * sizeof(int));
int* temp = (int*)malloc(n * sizeof(int));
for (int i = 0; i < n; i++) {
scanf("%d", &arr[i]);
}
long long result = mergeSort(arr, temp, 0, n - 1);
printf("%lld", result);
free(arr);
free(temp);
return 0;
}
- Time Complexity: O(n log n)
- Space Complexity: O(n)
Đây là cách tiếp cận chia để trị. Ta chia mảng thành hai nửa, đếm số cặp nghịch thế trong nửa trái, nửa phải, và số cặp nghịch thế với phần tử ở nửa trái lớn hơn phần tử ở nửa phải. Trong quá trình trộn (merge), nếu một phần tử từ nửa phải được lấy vào mảng kết quả trước một phần tử ở nửa trái, điều đó có nghĩa là phần tử nửa phải nhỏ hơn phần tử nửa trái đó. Do mảng con đã được sắp xếp, tất cả các phần tử còn lại trong mảng con trái đều lớn hơn phần tử nửa phải này. Do đó, ta cộng thêm (số phần tử còn lại trong nửa trái) vào biến đếm.
Cách Cây Fenwick (BIT)
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;
const int MAXN = 100005;
int bit[MAXN];
int n;
// Cập nhật giá trị tại chỉ số idx
void update(int idx, int val) {
for (; idx <= n; idx += idx & -idx)
bit[idx] += val;
}
// Truy vấn tổng giá trị từ 1 đến idx
int query(int idx) {
int sum = 0;
for (; idx > 0; idx -= idx & -idx)
sum += bit[idx];
return sum;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> n;
vector<int> a(n);
vector<int> sorted_a;
for (int i = 0; i < n; ++i) {
cin >> a[i];
sorted_a.push_back(a[i]);
}
// Nén giá trị (Coordinate Compression) để xử lý giá trị lớn và âm
sort(sorted_a.begin(), sorted_a.end());
sorted_a.erase(unique(sorted_a.begin(), sorted_a.end()), sorted_a.end());
long long ans = 0;
memset(bit, 0, sizeof(bit));
for (int i = 0; i < n; ++i) {
// Lấy chỉ số rank (1-based)
int rank = lower_bound(sorted_a.begin(), sorted_a.end(), a[i]) - sorted_a.begin() + 1;
// Số phần tử xuất hiện trước đó có giá trị <= a[i]
int count_smaller_equal = query(rank);
// Số cặp nghịch thế với a[i] là phần tử sau là:
// (số phần tử đã duyệt) - (số phần tử <= a[i])
// Tức là số phần tử > a[i]
ans += (i - count_smaller_equal);
// Thêm a[i] vào cây
update(rank, 1);
}
cout << ans << endl;
return 0;
}
- Time Complexity: O(n log n)
- Space Complexity: O(n)
Giải thuật sử dụng cây Fenwick (Binary Indexed Tree) để đếm số lượng phần tử đã xuất hiện. Ta duyệt mảng từ trái sang phải. Với mỗi phần tử a[i], ta cần biết có bao nhiêu phần tử đã xuất hiện trước đó (bên trái) có giá trị lớn hơn a[i].
- Nén tọa độ các giá trị của mảng về dải [1, n] để có thể dùng làm chỉ số BIT.
- Duyệt a[i]:
- Truy vấn BIT để lấy tổng số phần tử có giá trị <= a[i] đã xuất hiện.
- Số phần tử lớn hơn a[i] = i (số phần tử đã duyệt) - tổng lấy được.
- Cộng vào kết quả.
- Cập nhật BIT tại vị trí của a[i].
Phân tích độ phức tạp
| Cách tiếp cận | Time | Space | Tên |
|---|---|---|---|
| 1 | O(n^2) | O(1) | Brute Force (Đối sánh mọi cặp) |
| 2 | O(n log n) | O(n) | Merge Sort (Phân chia - Đếm) |
| 3 | O(n log n) | O(n) | Cây Fenwick (BIT) |
Bài học kinh nghiệm
- Bài toán yêu cầu đếm số cặp nghịch thế (i < j và a[i] > a[j]).
- Giải thuật O(n^2) không khả thi do giới hạn n=10^5.
- Có thể dùng Merge Sort (O(n log n) thời gian, O(n) bộ nhớ) hoặc Cây Fenwick (O(n log n) thời gian, O(n) bộ nhớ).
- Luôn sử dụng biến đếm kiểu 64-bit (long long) để tránh tràn số.
Lỗi thường gặp
- Quên cập nhật chỉ số BIT (phải là 1-based) hoặc sai logic cập nhật.
- Tràn bộ nhớ hoặc thời gian với giải thuật O(n^2).
- Xử lý các phần tử bằng nhau không đúng trong logic Merge Sort (phải dùng <= để ưu tiên phần tử bên trái).
Bình luận