Hướng dẫn giải của [VT Thiếu nhi] BÀI 15: INVERT
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
Với mỗi truy vấn (L, R), đếm số cặp chỉ số i < j trong đoạn [L, R] mà Ai > Aj. Q ≤ 10 và N ≤ 1000 nên có thể đếm trực tiếp hoặc dùng merge sort.
Sub 1: Đếm trực tiếp mọi cặp — ~O(Q·N^2)~
Với mỗi truy vấn, xét mọi cặp (i, j) với L ≤ i < j ≤ R và đếm cặp có Ai > Aj. Đạt 20/20 test.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
if (fopen("INVERT.INP", "r")) { freopen("INVERT.INP", "r", stdin); freopen("INVERT.OUT", "w", stdout); }
int n, q;
cin >> n >> q;
vector<long long> a(n + 1);
for (int i = 1; i <= n; i++) cin >> a[i];
while (q--) {
int L, R;
cin >> L >> R;
// Vét cạn: xét mọi cặp (i, j) trong đoạn [L, R]
long long cnt = 0;
for (int i = L; i <= R; i++)
for (int j = i + 1; j <= R; j++)
if (a[i] > a[j]) cnt++;
cout << cnt << "\n";
}
return 0;
}
Sub 2: Merge sort đếm nghịch thế — ~O(Q·N·log N)~
Khi trộn hai nửa đã sắp xếp, nếu phần tử bên phải nhỏ hơn phần tử bên trái thì nó tạo ra (số phần tử còn lại bên trái) nghịch thế. Cộng dồn trong quá trình sắp xếp. Đạt 20/20 test.
#include <bits/stdc++.h>
using namespace std;
// Đếm nghịch thế bằng merge sort: khi trộn hai nửa đã sắp xếp,
// mỗi phần tử ở nửa phải nhỏ hơn phần tử còn lại ở nửa trái đều tạo ra một nghịch thế
long long mergeCount(vector<long long> &a, vector<long long> &tmp, int l, int r) {
if (r - l <= 1) return 0;
int m = (l + r) / 2;
long long cnt = mergeCount(a, tmp, l, m) + mergeCount(a, tmp, m, r);
int i = l, j = m, k = l;
while (i < m && j < r) {
if (a[i] <= a[j]) {
tmp[k++] = a[i++];
} else {
cnt += m - i; // a[j] nhỏ hơn mọi phần tử còn lại của nửa trái
tmp[k++] = a[j++];
}
}
while (i < m) tmp[k++] = a[i++];
while (j < r) tmp[k++] = a[j++];
for (int t = l; t < r; t++) a[t] = tmp[t];
return cnt;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
if (fopen("INVERT.INP", "r")) { freopen("INVERT.INP", "r", stdin); freopen("INVERT.OUT", "w", stdout); }
int n, q;
cin >> n >> q;
vector<long long> a(n + 1);
for (int i = 1; i <= n; i++) cin >> a[i];
while (q--) {
int L, R;
cin >> L >> R;
// Lấy đoạn con [L, R] ra một mảng riêng rồi đếm nghịch thế bằng merge sort
vector<long long> sub(a.begin() + L, a.begin() + R + 1);
vector<long long> tmp(sub.size());
cout << mergeCount(sub, tmp, 0, (int)sub.size()) << "\n";
}
return 0;
}
Bình luận