Hướng giải của Khung Tranh Bao Nhau
Nhớ rằng hướng dẫn giải này chỉ nên sử dụng khi bế tắc, và tuyệt đối không nên sao chép mã nguồn kèm theo. Hãy tôn trọng tác giả bài tập và người viết hướng dẫn giải.
Nộp mã nguồn lời giải chính thức trước khi giải bài tập đó có thể khiến bạn bị ban.
Nộp mã nguồn lời giải chính thức trước khi giải bài tập đó có thể khiến bạn bị ban.
Tác giả:
Hướng dẫn giải
Bài toán đếm số lượng hình chữ nhật bao nhau. Khung tranh \(A\) bao hoàn toàn khung tranh \(B\) nếu: \[x_1(A) \le x_1(B) \le x_2(B) \le x_2(A)\] \[y_1(A) \le y_1(B) \le y_2(B) \le y_2(A)\]
Đây là bài toán hình học kết hợp cấu trúc dữ liệu.
- Rời rạc hóa tọa độ: Rời rạc hóa toàn bộ tọa độ trục \(y\) (\(y_1\) và \(y_2\)) và tọa độ đầu mút phải \(x_2\) về các chỉ số nguyên nhỏ hơn hoặc bằng \(2N\).
- Sắp xếp (Sweep-line): Sắp xếp các hình chữ nhật theo chiều tăng dần của góc trái \(x_1\). Nếu \(x_1\) bằng nhau, ưu tiên hình chữ nhật có \(x_2\) lớn hơn đặt lên trước.
- Duyệt ngược và đếm:
- Duyệt ngược các hình chữ nhật từ cuối về đầu. Khi duyệt đến hình chữ nhật \(i\), mọi hình chữ nhật \(j > i\) đã được duyệt đều thỏa mãn \(x_1(i) \le x_1(j)\) do ta duyệt từ phải sang trái.
- Lúc này, hình chữ nhật \(i\) bao \(j\) nếu: \[x_2(j) \le x_2(i)\] \[y_1(i) \le y_1(j) \le y_2(j) \le y_2(i)\]
- Ta sử dụng một cây BIT 2D quản lý số lượng các hình chữ nhật đã duyệt dựa trên cặp chỉ số \((x_2, y_1)\) của chúng.
- Để đếm số hình chữ nhật \(j\) có \(x_2(j) \le x_2(i)\) và \(y_1(j) \ge y_1(i)\), ta truy vấn tiền tố trên BIT 2D từ \(1\) đến \(x_2(i)\) ở chiều thứ nhất, và từ \(y_1(i)\) đến cực đại \(2N\) ở chiều thứ hai.
- Sau đó, thêm hình chữ nhật \(i\) vào BIT 2D tại vị trí \((x_2(i), y_1(i))\).
Mã nguồn C++ mẫu
#include <bits/stdc++.h>
using namespace std;
struct Rect {
int x1, y1, x2, y2, id;
};
int main(){
ios_base::sync_with_stdio(false); cin.tie(NULL);
int n; if (!(cin >> n)) return 0;
vector<Rect> rects(n);
vector<int> ys;
for (int i = 0; i < n; i++) {
cin >> rects[i].x1 >> rects[i].y1 >> rects[i].x2 >> rects[i].y2;
rects[i].id = i;
ys.push_back(rects[i].y1);
ys.push_back(rects[i].y2);
}
sort(ys.begin(), ys.end());
ys.erase(unique(ys.begin(), ys.end()), ys.end());
auto get_y = [&](int y) { return lower_bound(ys.begin(), ys.end(), y) - ys.begin() + 1; };
sort(rects.begin(), rects.end(), [](const Rect& a, const Rect& b) {
if (a.x1 == b.x1) return a.x2 > b.x2;
return a.x1 < b.x1;
});
vector<int> xs2;
for (int i = 0; i < n; i++) xs2.push_back(rects[i].x2);
sort(xs2.begin(), xs2.end());
xs2.erase(unique(xs2.begin(), xs2.end()), xs2.end());
auto get_x2 = [&](int x) { return lower_bound(xs2.begin(), xs2.end(), x) - xs2.begin() + 1; };
int lim_x = xs2.size();
int lim_y = ys.size();
vector<vector<int>> bit(lim_x + 2, vector<int>(lim_y + 2, 0));
auto update = [&](int x, int y, int val) {
for (int i = x; i <= lim_x; i += i & -i) {
for (int j = y; j <= lim_y; j += j & -j) {
bit[i][j] += val;
}
}
};
auto query = [&](int x, int y) {
int s = 0;
for (int i = x; i > 0; i -= i & -i) {
for (int j = y; j > 0; j -= j & -j) {
s += bit[i][j];
}
}
return s;
};
vector<int> ans(n, 0);
for (int i = n - 1; i >= 0; i--) {
int x2_idx = get_x2(rects[i].x2);
int y1_idx = get_y(rects[i].y1);
int y2_idx = get_y(rects[i].y2);
ans[rects[i].id] = query(x2_idx, lim_y) - query(x2_idx, y1_idx - 1);
update(x2_idx, y1_idx, 1);
}
for (int i = 0; i < n; i++) {
cout << ans[i] << (i == n - 1 ? "" : " ");
}
cout << "\n";
}
Nhận xét