全站最先发讨论
原题链接：55135.Overplanting S
2025-07-14 21:29:49
发布于：四川
#include <iostream>
#include <vector>
#include <algorithm>
struct Event {
int x;
int y_low;
int y_high;
int type;
bool operator<(const Event& other) const {
return x < other.x;
}
};
struct Node {
int count;
long long covered_length;
};
stdvector<int> all_y;
stdvector<Node> tree;
void push_up(int node_index, int l, int r) {
if (tree[node_index].count > 0) {
tree[node_index].covered_length = all_y[r + 1] - all_y[l];
} else if (l == r) {
tree[node_index].covered_length = 0;
} else {
tree[node_index].covered_length = tree[node_index * 2].covered_length + tree[node_index * 2 + 1].covered_length;
}
}
void update(int node_index, int l, int r, int update_l, int update_r, int val) {
if (l > update_r || r < update_l) {
return;
}
if (l >= update_l && r <= update_r) {
tree[node_index].count += val;
} else {
int mid = l + (r - l) / 2;
update(node_index * 2, l, mid, update_l, update_r, val);
update(node_index * 2 + 1, mid + 1, r, update_l, update_r, val);
}
push_up(node_index, l, r);
}
void solve() {
int n;
std::cin >> n;
std::vector<Event> events;
for (int i = 0; i < n; ++i) {
int x1, y1_in, x2, y2_in;
std::cin >> x1 >> y1_in >> x2 >> y2_in;
events.push_back({x1, y2_in, y1_in, 1});
events.push_back({x2, y2_in, y1_in, -1});
all_y.push_back(y2_in);
all_y.push_back(y1_in);
}
std::sort(all_y.begin(), all_y.end());
all_y.erase(std::unique(all_y.begin(), all_y.end()), all_y.end());
std::sort(events.begin(), events.end());
int m = all_y.size();
tree.resize(static_cast<size_t>(m) * 4);
long long total_area = 0;
for (size_t i = 0; i < events.size() - 1; ++i) {
auto y_low_it = std::lower_bound(all_y.begin(), all_y.end(), events[i].y_low);
auto y_high_it = std::lower_bound(all_y.begin(), all_y.end(), events[i].y_high);
int y_low_idx = y_low_it - all_y.begin();
int y_high_idx = y_high_it - all_y.begin();
if (y_low_idx < y_high_idx) {
update(1, 0, m - 2, y_low_idx, y_high_idx - 1, events[i].type);
}
long long width = events[i + 1].x - events[i].x;
if (width > 0) {
total_area += width * tree[1].covered_length;
}
}
std::cout << total_area << '\n';
}
int main() {
stdios_basesync_with_stdio(false);
std::cin.tie(NULL);
solve();
return 0;
}
这里空空如也
有帮助，赞一个