area of union of rectangles

ソースコード

  1#include <vector>
  2#include "titan_cpplib/algorithm/zaatsu.cpp"
  3#include "titan_cpplib/data_structures/lazy_segment_tree.cpp"
  4using namespace std;
  5
  6namespace titan23 {
  7
  8namespace AOUFR {
  9using S = long long;
 10using F = int;
 11const int bit = 31;
 12const int msk = (1ll<<bit)-1;
 13S op(S s, S t) {
 14    int s_val = s>>bit, s_cnt = s&msk;
 15    int t_val = t>>bit, t_cnt = t&msk;
 16    if (s_val < t_val) return s;
 17    if (t_val < s_val) return t;
 18    return (long long)s_val<<bit | (s_cnt + t_cnt);
 19}
 20S mapping(F f, S s) {
 21    int s_val = s>>bit, s_cnt = s&msk;
 22    return ((long long)s_val+f)<<bit | s_cnt;
 23}
 24F composition(F f, F g) {
 25    return f + g;
 26}
 27S e() {
 28    return 1ll<<61;
 29}
 30F id() {
 31    return 0;
 32}
 33} // namespace AOUFR
 34
 35template<typename T>
 36class AreaOfUnionOfRectangles {
 37  private:
 38    int n;
 39    vector<tuple<T, T, T, T>> ldru;
 40    vector<int> X, Y;
 41
 42  public:
 43    AreaOfUnionOfRectangles() : n(0) {}
 44    AreaOfUnionOfRectangles(int n) : n(n) {
 45        ldru.reserve(n);
 46        X.reserve(2*n);
 47        Y.reserve(2*n);
 48    }
 49
 50    void add_rectangle(T l, T d, T r, T u) {
 51        ldru.emplace_back(l, d, r, u);
 52        X.emplace_back(l);
 53        X.emplace_back(r);
 54        Y.emplace_back(d);
 55        Y.emplace_back(u);
 56    }
 57
 58    T get_sum() {
 59        titan23::Zaatsu<int> ZX(X), ZY(Y);
 60        vector<vector<pair<int, int>>> left(ZY.len()), right(ZY.len());
 61        for (auto [l, d, r, u] : ldru) {
 62            l = ZX.to_zaatsu(l);
 63            r = ZX.to_zaatsu(r);
 64            d = ZY.to_zaatsu(d);
 65            u = ZY.to_zaatsu(u);
 66            left[d].emplace_back(l, r);
 67            right[u].emplace_back(l, r);
 68        }
 69
 70        vector<int> nX(ZX.len()), nY(ZY.len());
 71        for (int i = 0; i < ZX.len(); ++i) {
 72            nX[i] = ZX.to_origin(i);
 73        }
 74        for (int i = 0; i < ZY.len(); ++i) {
 75            nY[i] = ZY.to_origin(i);
 76        }
 77        vector<AOUFR::S> init(ZX.len()-1);
 78        for (int i = 0; i < ZX.len()-1; ++i) {
 79            init[i] = nX[i+1] - nX[i];
 80        }
 81        titan23::LazySegmentTree<AOUFR::S, AOUFR::op, AOUFR::e, AOUFR::F, AOUFR::mapping, AOUFR::composition, AOUFR::id> seg(init);
 82
 83        T ans = 0;
 84        T s = nX.back() - nX[0];
 85        for (int i = 0; i < ZY.len()-1; ++i) {
 86            for (auto [l, r] : left[i]) {
 87                seg.apply(l, r, 1);
 88            }
 89
 90            T p_all = seg.all_prod();
 91            int p_val = p_all>>AOUFR::bit, p_cnt = p_all&AOUFR::msk;
 92            T p = p_val == 0 ? s-p_cnt : s;
 93            ans += p * (nY[i+1]-nY[i]);
 94
 95            for (auto [l, r] : right[i+1]) {
 96                seg.apply(l, r, -1);
 97            }
 98        }
 99
100        return ans;
101    }
102};
103}

仕様

Warning

doxygenfile: Cannot find file “titan_cpplib/data_structures/area_of_union_of_rectangles.cpp