This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub ebi-fly13/Library
#include "data_structure/area_of_union_of_rectangles.hpp"
複数の長方形の和集合の面積を求める。長方形の個数を $N$ として $O(N\log{N})$
長方形 $\lbrace (x, y): l \leq x \leq r, d \leq y \leq u\rbrace$ を追加する。
長方形の和集合の面積を求める。
#pragma once #include <cassert> #include <limits> #include <vector> #include "../data_structure/compress.hpp" #include "../data_structure/lazy_segtree.hpp" #include "../template/int_alias.hpp" namespace ebi { struct area_of_union_of_rectangles { private: using S = std::pair<int, i64>; static S op(S a, S b) { if (a.first == b.first) return {a.first, a.second + b.second}; else if (a.first < b.first) return a; else return b; } static S e() { return {std::numeric_limits<int>::max(), 0}; } static S mapping(int f, S x) { return {x.first + f, x.second}; } static int composition(int f, int g) { return f + g; } static int id() { return 0; } public: area_of_union_of_rectangles() = default; void add_rectangle(i64 l, i64 d, i64 r, i64 u) { qs.push_back({l, d, r, u}); cp_x.add(l); cp_x.add(r); cp_y.add(d); cp_y.add(u); } i64 run() { assert(is_first); is_first = false; cp_x.build(); cp_y.build(); int n = cp_x.size(), m = cp_y.size(); lazy_segtree<S, op, e, int, mapping, composition, id> seg( [&]() -> std::vector<S> { std::vector<S> data(m - 1); for (int i = 0; i < m - 1; i++) { data[i] = {0, cp_y.val(i + 1) - cp_y.val(i)}; } return data; }()); std::vector table(n, std::vector(2, std::vector<std::pair<i64, i64>>())); for (auto [l, d, r, u] : qs) { int x = cp_y.get(d); int y = cp_y.get(u); table[cp_x.get(l)][0].emplace_back(x, y); table[cp_x.get(r)][1].emplace_back(x, y); } i64 ans = 0; for (int i = 0; i < n - 1; i++) { i64 wy = cp_y.val(m - 1) - cp_y.val(0); i64 wx = cp_x.val(i + 1) - cp_x.val(i); for (auto [d, u] : table[i][0]) { seg.apply(d, u, 1); } for (auto [d, u] : table[i][1]) { seg.apply(d, u, -1); } auto [min, cnt] = seg.all_prod(); if (min == 0) wy -= cnt; ans += wx * wy; } return ans; } private: bool is_first = true; std::vector<std::array<i64, 4>> qs; compress<i64> cp_x, cp_y; }; } // namespace ebi
#line 2 "data_structure/area_of_union_of_rectangles.hpp" #include <cassert> #include <limits> #include <vector> #line 2 "data_structure/compress.hpp" #include <algorithm> #line 6 "data_structure/compress.hpp" namespace ebi { template <class T> struct compress { private: std::vector<T> cp; public: compress() = default; compress(std::vector<T> cp_) : cp(cp_) { build(); } void build() { std::sort(cp.begin(), cp.end()); cp.erase(std::unique(cp.begin(), cp.end()), cp.end()); } void add(const T &val) { cp.emplace_back(val); } int get(const T &val) const { return std::lower_bound(cp.begin(), cp.end(), val) - cp.begin(); } int size() const { return cp.size(); } bool find(const T &val) const { auto itr = std::lower_bound(cp.begin(), cp.end(), val); if (itr == cp.end()) return false; else return *itr == val; } T val(int idx) const { assert(0 <= idx && idx < (int)cp.size()); return cp[idx]; } }; } // namespace ebi #line 2 "data_structure/lazy_segtree.hpp" /* reference: https://atcoder.github.io/ac-library/master/document_ja/lazysegtree.html */ #include <bit> #line 10 "data_structure/lazy_segtree.hpp" #include <cstdint> #include <ranges> #line 13 "data_structure/lazy_segtree.hpp" namespace ebi { template <class S, S (*op)(S, S), S (*e)(), class F, S (*mapping)(F, S), F (*composition)(F, F), F (*id)()> struct lazy_segtree { private: void update(int i) { data[i] = op(data[2 * i], data[2 * i + 1]); } void all_apply(int k, F f) { data[k] = mapping(f, data[k]); if (k < sz) lazy[k] = composition(f, lazy[k]); } void push(int i) { all_apply(2 * i, lazy[i]); all_apply(2 * i + 1, lazy[i]); lazy[i] = id(); } public: lazy_segtree(int n_) : lazy_segtree(std::vector<S>(n_, e())) {} lazy_segtree(const std::vector<S> &a) : n(a.size()), sz(std::bit_ceil(a.size())), lg2(std::countr_zero(std::uint32_t(sz))) { data = std::vector<S>(2 * sz, e()); lazy = std::vector<F>(sz, id()); for (int i : std::views::iota(0, n)) { data[sz + i] = a[i]; } for (int i : std::views::iota(1, sz) | std::views::reverse) { update(i); } } void set(int p, S x) { assert(0 <= p && p < n); p += sz; for (int i = lg2; i >= 1; i--) push(p >> i); data[p] = x; for (int i = 1; i <= lg2; i++) update(p >> i); } S get(int p) { assert(0 <= p && p < n); p += sz; for (int i = lg2; i >= 1; i--) push(p >> i); return data[p]; } S prod(int l, int r) { assert(0 <= l && l <= r && r <= n); if (l == r) return e(); l += sz; r += sz; for (int i = lg2; i >= 1; i--) { if (((l >> i) << i) != l) push(l >> i); if (((r >> i) << i) != r) push((r - 1) >> i); } S sml = e(), smr = e(); while (l < r) { if (l & 1) sml = op(sml, data[l++]); if (r & 1) smr = op(data[--r], smr); l >>= 1; r >>= 1; } return op(sml, smr); } S all_prod() const { return data[1]; } void apply(int p, F f) { assert(0 <= p && p < n); p += sz; for (int i = lg2; i >= 1; i--) push(p >> i); data[p] = mapping(f, data[p]); for (int i = 1; i <= lg2; i++) update(p >> i); } void apply(int l, int r, F f) { assert(0 <= l && l <= r && r <= n); l += sz; r += sz; for (int i = lg2; i >= 1; i--) { if (((l >> i) << i) != l) push(l >> i); if (((r >> i) << i) != r) push((r - 1) >> i); } { int memo_l = l, memo_r = r; while (l < r) { if (l & 1) all_apply(l++, f); if (r & 1) all_apply(--r, f); l >>= 1; r >>= 1; } l = memo_l; r = memo_r; } for (int i = 1; i <= lg2; i++) { if (((l >> i) << i) != l) update(l >> i); if (((r >> i) << i) != r) update((r - 1) >> i); } } template <class G> int max_right(int l, G g) { assert(0 <= l && l <= n); assert(g(e())); if (l == n) return n; l += sz; for (int i = lg2; i >= 1; i--) push(l >> i); S sm = e(); do { while (l % 2 == 0) l >>= 1; if (!g(op(sm, data[l]))) { while (l < sz) { push(l); l = l << 1; if (g(op(sm, data[l]))) { sm = op(sm, data[l]); l++; } } return l - sz; } sm = op(sm, data[l]); l++; } while ((l & -l) != l); return n; } template <class G> int min_left(int r, G g) { assert(0 <= r && r <= n); assert(g(e())); if (r == 0) return 0; r += sz; for (int i = lg2; i >= 1; i--) push((r - 1) >> i); S sm = e(); do { r--; while (r > 1 && r % 2) r >>= 1; if (!g(op(data[r], sm))) { while (r < sz) { push(r); r = (r << 1) + 1; if (g(op(data[r], sm))) { sm = op(data[r], sm); r--; } } return r + 1 - sz; } sm = op(data[r], sm); } while ((r & -r) != r); return 0; } private: int n, sz, lg2; std::vector<S> data; std::vector<F> lazy; }; } // namespace ebi #line 2 "template/int_alias.hpp" #line 4 "template/int_alias.hpp" namespace ebi { using ld = long double; using std::size_t; using i8 = std::int8_t; using u8 = std::uint8_t; using i16 = std::int16_t; using u16 = std::uint16_t; using i32 = std::int32_t; using u32 = std::uint32_t; using i64 = std::int64_t; using u64 = std::uint64_t; using i128 = __int128_t; using u128 = __uint128_t; } // namespace ebi #line 10 "data_structure/area_of_union_of_rectangles.hpp" namespace ebi { struct area_of_union_of_rectangles { private: using S = std::pair<int, i64>; static S op(S a, S b) { if (a.first == b.first) return {a.first, a.second + b.second}; else if (a.first < b.first) return a; else return b; } static S e() { return {std::numeric_limits<int>::max(), 0}; } static S mapping(int f, S x) { return {x.first + f, x.second}; } static int composition(int f, int g) { return f + g; } static int id() { return 0; } public: area_of_union_of_rectangles() = default; void add_rectangle(i64 l, i64 d, i64 r, i64 u) { qs.push_back({l, d, r, u}); cp_x.add(l); cp_x.add(r); cp_y.add(d); cp_y.add(u); } i64 run() { assert(is_first); is_first = false; cp_x.build(); cp_y.build(); int n = cp_x.size(), m = cp_y.size(); lazy_segtree<S, op, e, int, mapping, composition, id> seg( [&]() -> std::vector<S> { std::vector<S> data(m - 1); for (int i = 0; i < m - 1; i++) { data[i] = {0, cp_y.val(i + 1) - cp_y.val(i)}; } return data; }()); std::vector table(n, std::vector(2, std::vector<std::pair<i64, i64>>())); for (auto [l, d, r, u] : qs) { int x = cp_y.get(d); int y = cp_y.get(u); table[cp_x.get(l)][0].emplace_back(x, y); table[cp_x.get(r)][1].emplace_back(x, y); } i64 ans = 0; for (int i = 0; i < n - 1; i++) { i64 wy = cp_y.val(m - 1) - cp_y.val(0); i64 wx = cp_x.val(i + 1) - cp_x.val(i); for (auto [d, u] : table[i][0]) { seg.apply(d, u, 1); } for (auto [d, u] : table[i][1]) { seg.apply(d, u, -1); } auto [min, cnt] = seg.all_prod(); if (min == 0) wy -= cnt; ans += wx * wy; } return ans; } private: bool is_first = true; std::vector<std::array<i64, 4>> qs; compress<i64> cp_x, cp_y; }; } // namespace ebi