Hướng giải của Điểm phủ nhiều hình chữ nhật nhất
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
Dùng sweep line hai chiều kết hợp segment tree với lazy propagation. Quét một đường thẳng đứng từ trái sang phải. Tại mỗi sự kiện (cạnh trái: thêm +1 vào đoạn \([y_1, y_2)\), cạnh phải: thêm -1), cập nhật segment tree và truy vấn giá trị lớn nhất toàn cục.
Độ phức tạp: \(O(N \log N)\).
Mã nguồn C++
#include <bits/stdc++.h>
using namespace std;
struct Event {
int x, y1, y2, type;
Event(int x, int y1, int y2, int type) : x(x), y1(y1), y2(y2), type(type) {}
bool operator<(const Event& o) const { return x < o.x; }
};
struct SegTree {
int n;
vector<int> mx, lazy;
SegTree(int n) : n(n) {
mx.assign(4 * n, 0);
lazy.assign(4 * n, 0);
}
void push(int id) {
if (lazy[id]) {
mx[id * 2] += lazy[id]; lazy[id * 2] += lazy[id];
mx[id * 2 + 1] += lazy[id]; lazy[id * 2 + 1] += lazy[id];
lazy[id] = 0;
}
}
void update(int l, int r, int val, int id, int L, int R) {
if (l >= R || r <= L) return;
if (l <= L && R <= r) {
mx[id] += val; lazy[id] += val;
return;
}
push(id);
int M = (L + R) / 2;
update(l, r, val, id * 2, L, M);
update(l, r, val, id * 2 + 1, M, R);
mx[id] = max(mx[id * 2], mx[id * 2 + 1]);
}
void update(int l, int r, int val) { update(l, r, val, 1, 0, n); }
int query() { return mx[1]; }
};
int main() {
ios_base::sync_with_stdio(false); cin.tie(NULL);
int n; cin >> n;
vector<Event> events;
vector<int> ys;
for (int i = 0; i < n; i++) {
int x1, y1, x2, y2;
cin >> x1 >> y1 >> x2 >> y2;
events.emplace_back(x1, y1, y2, 1);
events.emplace_back(x2, y1, y2, -1);
ys.push_back(y1); ys.push_back(y2);
}
sort(ys.begin(), ys.end());
ys.erase(unique(ys.begin(), ys.end()), ys.end());
sort(events.begin(), events.end());
SegTree st(ys.size() - 1);
int ans = 0;
for (auto& e : events) {
int l = lower_bound(ys.begin(), ys.end(), e.y1) - ys.begin();
int r = lower_bound(ys.begin(), ys.end(), e.y2) - ys.begin();
st.update(l, r, e.type);
ans = max(ans, st.query());
}
cout << ans << "\n";
return 0;
}
Nhận xét