This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub suisen-cp/cp-library-cpp
#include "library/algorithm/area_of_union_of_rectangles.hpp"
#ifndef SUISEN_AREA_OF_UNION_OF_RECTANGLES #define SUISEN_AREA_OF_UNION_OF_RECTANGLES #include <limits> #include <tuple> #include <vector> #include <atcoder/lazysegtree> namespace suisen { namespace internal::area_of_union_of_rectangles { constexpr int inf = std::numeric_limits<int>::max() / 2; template <typename T> struct S { int min_cnt; T len; }; template <typename T> S<T> op(S<T> x, S<T> y) { if (x.min_cnt < y.min_cnt) return x; else if (x.min_cnt > y.min_cnt) return y; else return { x.min_cnt, x.len + y.len }; } template <typename T> S<T> e() { return { inf , 0 }; } template <typename T> S<T> mapping(int f, S<T> x) { return { x.min_cnt + f, x.len }; } int composition(int f, int g) { return f + g; } int id() { return 0; } } /** * @brief Calculates area of union of rectangles in O(NlogN) time. * @tparam T type of coordinates * @param rects vector of { l, r, d, u }. * @return area of union of rectangles */ template <typename T> T area_of_union_of_rectangles(const std::vector<std::tuple<T, T, T, T>> &rects) { if (rects.empty()) return T{0}; using namespace internal::area_of_union_of_rectangles; const int k = rects.size(); std::vector<std::tuple<T, T, T, bool>> event; event.reserve(2 * k); std::vector<T> ys; ys.reserve(2 * k); for (const auto &[l, r, d, u] : rects) { event.emplace_back(l, d, u, true); event.emplace_back(r, d, u, false); ys.push_back(d), ys.push_back(u); } std::sort(event.begin(), event.end(), [](const auto& e1, const auto &e2) { return std::get<0>(e1) < std::get<0>(e2); }); std::sort(ys.begin(), ys.end()), ys.erase(std::unique(ys.begin(), ys.end()), ys.end()); const int m = ys.size(); std::vector<S<T>> init(m - 1); for (int i = 0; i < m - 1; ++i) { init[i] = { 0, ys[i + 1] - ys[i] }; } atcoder::lazy_segtree<S<T>, op<T>, e<T>, int, mapping<T>, composition, id> seg(init); T ans = 0; T lx = std::get<0>(event.front()); for (int i = 0; lx != std::get<0>(event.back());) { for (;; ++i) { auto [xi, d, u, b] = event[i]; if (xi != lx) break; int ly = std::lower_bound(ys.begin(), ys.end(), d) - ys.begin(); int ry = std::lower_bound(ys.begin(), ys.end(), u) - ys.begin(); seg.apply(ly, ry, b ? +1 : -1); } T rx = std::get<0>(event[i]); auto [min_cnt, len] = seg.all_prod(); ans += (rx - lx) * (ys.back() - ys.front() - (min_cnt == 0 ? len : T{0})); lx = rx; } return ans; } } // namespace suisen #endif // SUISEN_AREA_OF_UNION_OF_RECTANGLES
#line 1 "library/algorithm/area_of_union_of_rectangles.hpp" #include <limits> #include <tuple> #include <vector> #include <atcoder/lazysegtree> namespace suisen { namespace internal::area_of_union_of_rectangles { constexpr int inf = std::numeric_limits<int>::max() / 2; template <typename T> struct S { int min_cnt; T len; }; template <typename T> S<T> op(S<T> x, S<T> y) { if (x.min_cnt < y.min_cnt) return x; else if (x.min_cnt > y.min_cnt) return y; else return { x.min_cnt, x.len + y.len }; } template <typename T> S<T> e() { return { inf , 0 }; } template <typename T> S<T> mapping(int f, S<T> x) { return { x.min_cnt + f, x.len }; } int composition(int f, int g) { return f + g; } int id() { return 0; } } /** * @brief Calculates area of union of rectangles in O(NlogN) time. * @tparam T type of coordinates * @param rects vector of { l, r, d, u }. * @return area of union of rectangles */ template <typename T> T area_of_union_of_rectangles(const std::vector<std::tuple<T, T, T, T>> &rects) { if (rects.empty()) return T{0}; using namespace internal::area_of_union_of_rectangles; const int k = rects.size(); std::vector<std::tuple<T, T, T, bool>> event; event.reserve(2 * k); std::vector<T> ys; ys.reserve(2 * k); for (const auto &[l, r, d, u] : rects) { event.emplace_back(l, d, u, true); event.emplace_back(r, d, u, false); ys.push_back(d), ys.push_back(u); } std::sort(event.begin(), event.end(), [](const auto& e1, const auto &e2) { return std::get<0>(e1) < std::get<0>(e2); }); std::sort(ys.begin(), ys.end()), ys.erase(std::unique(ys.begin(), ys.end()), ys.end()); const int m = ys.size(); std::vector<S<T>> init(m - 1); for (int i = 0; i < m - 1; ++i) { init[i] = { 0, ys[i + 1] - ys[i] }; } atcoder::lazy_segtree<S<T>, op<T>, e<T>, int, mapping<T>, composition, id> seg(init); T ans = 0; T lx = std::get<0>(event.front()); for (int i = 0; lx != std::get<0>(event.back());) { for (;; ++i) { auto [xi, d, u, b] = event[i]; if (xi != lx) break; int ly = std::lower_bound(ys.begin(), ys.end(), d) - ys.begin(); int ry = std::lower_bound(ys.begin(), ys.end(), u) - ys.begin(); seg.apply(ly, ry, b ? +1 : -1); } T rx = std::get<0>(event[i]); auto [min_cnt, len] = seg.all_prod(); ans += (rx - lx) * (ys.back() - ys.front() - (min_cnt == 0 ? len : T{0})); lx = rx; } return ans; } } // namespace suisen