rectangle_union_area.hpp¶
精确计算多个半开轴对齐整数矩形的并面积；结果须能用 128 位有符号整数表示。
Complexity: Time: \(O(n \log n)\). Space: \(O(n)\).
AC 记录：area_of_union_of_rectangles。
Implementation¶
当前头文件，省略 include guard；依赖见 #include。
/// @complexity Time: O(n log n).
/// Space: O(n).
#include <algorithm>
#include <array>
#include <cassert>
#include <cstdint>
#include <numeric>
#include <vector>
namespace noya {
/// @brief Exact union area of half-open axis-aligned integer rectangles by a
/// sweep line and covered-length segment tree in O(n log n).
/// The total area must fit in signed 128 bits.
inline __int128
rectangle_union_area(const std::vector<std::array<std::int64_t, 4>> &rec) {
struct event {
std::int64_t x;
int lo;
int hi;
int dlt;
};
std::vector<event> ev;
std::vector<std::int64_t> xs;
xs.reserve(rec.size() * 2);
for (auto [l, r, lo, hi] : rec) {
assert(l <= r && lo <= hi);
if (l == r || lo == hi) {
continue;
}
xs.push_back(lo);
xs.push_back(hi);
}
if (xs.empty()) {
return 0;
}
std::sort(xs.begin(), xs.end());
xs.erase(std::unique(xs.begin(), xs.end()), xs.end());
// Both x events share one compressed y interval.
ev.reserve(rec.size() * 2);
for (auto [l, r, lo, hi] : rec) {
if (l == r || lo == hi) continue;
int a = int(std::lower_bound(xs.begin(), xs.end(), lo) - xs.begin());
int b = int(std::lower_bound(xs.begin(), xs.end(), hi) - xs.begin());
ev.push_back({l, a, b, 1});
ev.push_back({r, a, b, -1});
}
std::sort(ev.begin(), ev.end(),
[](const event &a, const event &b) { return a.x < b.x; });
int n = int(xs.size()) - 1;
std::vector<int> cov(n * 4 + 4);
std::vector<__int128> len(n * 4 + 4);
auto up = [&](int nd, int l, int r) {
if (cov[nd] > 0) {
len[nd] = __int128(xs[r]) - xs[l];
} else if (r - l == 1) {
len[nd] = 0;
} else {
len[nd] = len[nd * 2] + len[nd * 2 + 1];
}
};
auto upd = [&](auto &self, int nd, int l, int r, int ql, int qr,
int dlt) -> void {
if (qr <= l || r <= ql) {
return;
}
if (ql <= l && r <= qr) {
cov[nd] += dlt;
up(nd, l, r);
return;
}
int mid = std::midpoint(l, r);
self(self, nd * 2, l, mid, ql, qr, dlt);
self(self, nd * 2 + 1, mid, r, ql, qr, dlt);
up(nd, l, r);
};
__int128 s = 0;
std::int64_t px = ev[0].x;
for (int i = 0; i < int(ev.size());) {
std::int64_t x1 = ev[i].x;
s += (__int128(x1) - px) * len[1];
while (i < int(ev.size()) && ev[i].x == x1) {
upd(upd, 1, 0, n, ev[i].lo, ev[i].hi, ev[i].dlt);
i++;
}
px = x1;
}
return s;
}
} // namespace noya
// NOYA_RECTANGLE_UNION_AREA_HPP
#ifndef NOYA_RECTANGLE_UNION_AREA_HPP
#define NOYA_RECTANGLE_UNION_AREA_HPP 1
/// @complexity Time: O(n log n).
/// Space: O(n).
#include <algorithm>
#include <array>
#include <cassert>
#include <cstdint>
#include <numeric>
#include <vector>
namespace noya {
/// @brief Exact union area of half-open axis-aligned integer rectangles by a
/// sweep line and covered-length segment tree in O(n log n).
/// The total area must fit in signed 128 bits.
inline __int128
rectangle_union_area(const std::vector<std::array<std::int64_t, 4>> &rec) {
struct event {
std::int64_t x;
int lo;
int hi;
int dlt;
};
std::vector<event> ev;
std::vector<std::int64_t> xs;
xs.reserve(rec.size() * 2);
for (auto [l, r, lo, hi] : rec) {
assert(l <= r && lo <= hi);
if (l == r || lo == hi) {
continue;
}
xs.push_back(lo);
xs.push_back(hi);
}
if (xs.empty()) {
return 0;
}
std::sort(xs.begin(), xs.end());
xs.erase(std::unique(xs.begin(), xs.end()), xs.end());
// Both x events share one compressed y interval.
ev.reserve(rec.size() * 2);
for (auto [l, r, lo, hi] : rec) {
if (l == r || lo == hi) continue;
int a = int(std::lower_bound(xs.begin(), xs.end(), lo) - xs.begin());
int b = int(std::lower_bound(xs.begin(), xs.end(), hi) - xs.begin());
ev.push_back({l, a, b, 1});
ev.push_back({r, a, b, -1});
}
std::sort(ev.begin(), ev.end(),
[](const event &a, const event &b) { return a.x < b.x; });
int n = int(xs.size()) - 1;
std::vector<int> cov(n * 4 + 4);
std::vector<__int128> len(n * 4 + 4);
auto up = [&](int nd, int l, int r) {
if (cov[nd] > 0) {
len[nd] = __int128(xs[r]) - xs[l];
} else if (r - l == 1) {
len[nd] = 0;
} else {
len[nd] = len[nd * 2] + len[nd * 2 + 1];
}
};
auto upd = [&](auto &self, int nd, int l, int r, int ql, int qr,
int dlt) -> void {
if (qr <= l || r <= ql) {
return;
}
if (ql <= l && r <= qr) {
cov[nd] += dlt;
up(nd, l, r);
return;
}
int mid = std::midpoint(l, r);
self(self, nd * 2, l, mid, ql, qr, dlt);
self(self, nd * 2 + 1, mid, r, ql, qr, dlt);
up(nd, l, r);
};
__int128 s = 0;
std::int64_t px = ev[0].x;
for (int i = 0; i < int(ev.size());) {
std::int64_t x1 = ev[i].x;
s += (__int128(x1) - px) * len[1];
while (i < int(ev.size()) && ev[i].x == x1) {
upd(upd, 1, 0, n, ev[i].lo, ev[i].hi, ev[i].dlt);
i++;
}
px = x1;
}
return s;
}
} // namespace noya
#endif // NOYA_RECTANGLE_UNION_AREA_HPP
/// @complexity Time: O(n log n).
/// Space: O(n).
#include <algorithm>
#include <array>
#include <cassert>
#include <cstdint>
#include <numeric>
#include <vector>
namespace noya {
/// @brief Exact union area of half-open axis-aligned integer rectangles by a
/// sweep line and covered-length segment tree in O(n log n).
/// The total area must fit in signed 128 bits.
inline __int128
rectangle_union_area(const std::vector<std::array<std::int64_t, 4>> &rec) {
struct event {
std::int64_t x;
int lo;
int hi;
int dlt;
};
std::vector<event> ev;
std::vector<std::int64_t> xs;
xs.reserve(rec.size() * 2);
for (auto [l, r, lo, hi] : rec) {
assert(l <= r && lo <= hi);
if (l == r || lo == hi) {
continue;
}
xs.push_back(lo);
xs.push_back(hi);
}
if (xs.empty()) {
return 0;
}
std::sort(xs.begin(), xs.end());
xs.erase(std::unique(xs.begin(), xs.end()), xs.end());
// Both x events share one compressed y interval.
ev.reserve(rec.size() * 2);
for (auto [l, r, lo, hi] : rec) {
if (l == r || lo == hi) continue;
int a = int(std::lower_bound(xs.begin(), xs.end(), lo) - xs.begin());
int b = int(std::lower_bound(xs.begin(), xs.end(), hi) - xs.begin());
ev.push_back({l, a, b, 1});
ev.push_back({r, a, b, -1});
}
std::sort(ev.begin(), ev.end(),
[](const event &a, const event &b) { return a.x < b.x; });
int n = int(xs.size()) - 1;
std::vector<int> cov(n * 4 + 4);
std::vector<__int128> len(n * 4 + 4);
auto up = [&](int nd, int l, int r) {
if (cov[nd] > 0) {
len[nd] = __int128(xs[r]) - xs[l];
} else if (r - l == 1) {
len[nd] = 0;
} else {
len[nd] = len[nd * 2] + len[nd * 2 + 1];
}
};
auto upd = [&](auto &self, int nd, int l, int r, int ql, int qr,
int dlt) -> void {
if (qr <= l || r <= ql) {
return;
}
if (ql <= l && r <= qr) {
cov[nd] += dlt;
up(nd, l, r);
return;
}
int mid = std::midpoint(l, r);
self(self, nd * 2, l, mid, ql, qr, dlt);
self(self, nd * 2 + 1, mid, r, ql, qr, dlt);
up(nd, l, r);
};
__int128 s = 0;
std::int64_t px = ev[0].x;
for (int i = 0; i < int(ev.size());) {
std::int64_t x1 = ev[i].x;
s += (__int128(x1) - px) * len[1];
while (i < int(ev.size()) && ev[i].x == x1) {
upd(upd, 1, 0, n, ev[i].lo, ev[i].hi, ev[i].dlt);
i++;
}
px = x1;
}
return s;
}
} // namespace noya
// NOYA_RECTANGLE_UNION_AREA_HPP