Area of Union of Rectangles
(misc/rectangle_union.hpp)

• View this file on GitHub
• Last update: 2024-05-08 10:29:23+09:00
• Include: #include "misc/rectangle_union.hpp"

Depends on

• Segment Tree with Lazy Propagation (data-structure/segtree/lazy_segment_tree.hpp)

Verified with

• test/yosupo/area_of_union_of_rectangles.test.cpp

Code

#pragma once
#include <algorithm>
#include <vector>

#include "../data-structure/segtree/lazy_segment_tree.hpp"

/**
 * @brief Area of Union of Rectangles
 */
struct CountMinMonoid {
    using T = std::pair<int, int>;  // min, count
    static T id() { return {(1u << 31) - 1, 0}; }
    static T op(T a, T b) {
        if (a.first < b.first) return a;
        if (a.first > b.first) return b;
        return {a.first, a.second + b.second};
    }
};

struct AddMonoid {
    using T = int;
    static T id() { return 0; }
    static T op(T a, T b) { return a + b; }
};

CountMinMonoid::T act(CountMinMonoid::T a, AddMonoid::T b) {
    return {a.first + b, a.second};
}

// rectangles are given in the form (l, d, r, u)
long long area_of_union_of_rectangles(
    const std::vector<std::tuple<long long, long long, long long, long long>>&
        rects) {
    std::vector<long long> xs, ys;
    for (auto [l, d, r, u] : rects) {
        xs.push_back(l);
        xs.push_back(r);
        ys.push_back(d);
        ys.push_back(u);
    }
    std::ranges::sort(xs);
    xs.erase(std::ranges::unique(xs).begin(), xs.end());
    std::ranges::sort(ys);
    ys.erase(std::ranges::unique(ys).begin(), ys.end());

    std::vector<std::vector<std::tuple<long long, long long, int>>> update(
        ys.size());
    for (auto [l, d, r, u] : rects) {
        int cl = std::ranges::lower_bound(xs, l) - xs.begin();
        int cd = std::ranges::lower_bound(ys, d) - ys.begin();
        int cr = std::ranges::lower_bound(xs, r) - xs.begin();
        int cu = std::ranges::lower_bound(ys, u) - ys.begin();
        update[cd].push_back({cl, cr, 1});
        update[cu].push_back({cl, cr, -1});
    }

    std::vector<std::pair<int, int>> init(xs.size() - 1);
    for (int x = 0; x < (int)xs.size() - 1; ++x) {
        init[x] = {0, xs[x + 1] - xs[x]};
    }

    LazySegmentTree<CountMinMonoid, AddMonoid, act> st(init);
    long long ans = 0;
    long long xlen = xs.back() - xs[0];
    for (int y = 0; y < (int)ys.size() - 1; ++y) {
        for (auto [l, r, diff] : update[y]) {
            st.update(l, r, diff);
        }
        auto [minval, len0] = st.fold_all();
        if (minval > 0) len0 = 0;
        ans += (xlen - len0) * (ys[y + 1] - ys[y]);
    }
    return ans;
}

#line 2 "misc/rectangle_union.hpp"
#include <algorithm>
#include <vector>

#line 3 "data-structure/segtree/lazy_segment_tree.hpp"
#include <bit>
#include <numeric>
#line 6 "data-structure/segtree/lazy_segment_tree.hpp"

template <typename M, typename O,
          typename M::T (*act)(typename M::T, typename O::T)>
class LazySegmentTree {
    using T = M::T;
    using E = O::T;

   public:
    LazySegmentTree() = default;
    explicit LazySegmentTree(int n)
        : LazySegmentTree(std::vector<T>(n, M::id())) {}
    explicit LazySegmentTree(const std::vector<T>& v)
        : size(std::bit_ceil(v.size())),
          node(2 * size, M::id()),
          lazy(2 * size, O::id()) {
        std::ranges::copy(v, node.begin() + size);
        for (int i = size - 1; i > 0; --i) {
            node[i] = M::op(node[2 * i], node[2 * i + 1]);
        }
    }

    T operator[](int k) { return fold(k, k + 1); }

    void update(int l, int r, const E& x) { update(l, r, x, 1, 0, size); }

    T fold(int l, int r) { return fold(l, r, 1, 0, size); }

    T fold_all() {
        push(1);
        return node[1];
    }

    template <typename F>
    int find_first(int l, F cond) {
        T v = M::id();
        return find_first(l, size, 1, 0, size, v, cond);
    }

    template <typename F>
    int find_last(int r, F cond) {
        T v = M::id();
        return find_last(0, r, 1, 0, size, v, cond);
    }

   private:
    int size;
    std::vector<T> node;
    std::vector<E> lazy;

    void push(int k) {
        if (lazy[k] == O::id()) return;
        if (k < size) {
            lazy[2 * k] = O::op(lazy[2 * k], lazy[k]);
            lazy[2 * k + 1] = O::op(lazy[2 * k + 1], lazy[k]);
        }
        node[k] = act(node[k], lazy[k]);
        lazy[k] = O::id();
    }

    void update(int a, int b, const E& x, int k, int l, int r) {
        push(k);
        if (r <= a || b <= l) return;
        if (a <= l && r <= b) {
            lazy[k] = O::op(lazy[k], x);
            push(k);
            return;
        }
        int m = std::midpoint(l, r);
        update(a, b, x, 2 * k, l, m);
        update(a, b, x, 2 * k + 1, m, r);
        node[k] = M::op(node[2 * k], node[2 * k + 1]);
    }

    T fold(int a, int b, int k, int l, int r) {
        push(k);
        if (r <= a || b <= l) return M::id();
        if (a <= l && r <= b) return node[k];
        int m = std::midpoint(l, r);
        return M::op(fold(a, b, 2 * k, l, m), fold(a, b, 2 * k + 1, m, r));
    }

    template <typename F>
    int find_first(int a, int b, int k, int l, int r, T& v, F cond) {
        push(k);
        if (r <= a) return -1;
        if (b <= l) return l;
        if (a <= l && r <= b && !cond(M::op(v, node[k]))) {
            v = M::op(v, node[k]);
            return -1;
        }
        if (r - l == 1) return r;
        int m = std::midpoint(l, r);
        int res = find_first(a, b, 2 * k, l, m, v, cond);
        if (res != -1) return res;
        return find_first(a, b, 2 * k + 1, m, r, v, cond);
    }

    template <typename F>
    int find_last(int a, int b, int k, int l, int r, T& v, F cond) {
        push(k);
        if (b <= l) return -1;
        if (r <= a) return r;
        if (a <= l && r <= b && !cond(M::op(node[k], v))) {
            v = M::op(node[k], v);
            return -1;
        }
        if (r - l == 1) return l;
        int m = std::midpoint(l, r);
        int res = find_last(a, b, 2 * k + 1, m, r, v, cond);
        if (res != -1) return res;
        return find_last(a, b, 2 * k, l, m, v, cond);
    }
};
#line 6 "misc/rectangle_union.hpp"

/**
 * @brief Area of Union of Rectangles
 */
struct CountMinMonoid {
    using T = std::pair<int, int>;  // min, count
    static T id() { return {(1u << 31) - 1, 0}; }
    static T op(T a, T b) {
        if (a.first < b.first) return a;
        if (a.first > b.first) return b;
        return {a.first, a.second + b.second};
    }
};

struct AddMonoid {
    using T = int;
    static T id() { return 0; }
    static T op(T a, T b) { return a + b; }
};

CountMinMonoid::T act(CountMinMonoid::T a, AddMonoid::T b) {
    return {a.first + b, a.second};
}

// rectangles are given in the form (l, d, r, u)
long long area_of_union_of_rectangles(
    const std::vector<std::tuple<long long, long long, long long, long long>>&
        rects) {
    std::vector<long long> xs, ys;
    for (auto [l, d, r, u] : rects) {
        xs.push_back(l);
        xs.push_back(r);
        ys.push_back(d);
        ys.push_back(u);
    }
    std::ranges::sort(xs);
    xs.erase(std::ranges::unique(xs).begin(), xs.end());
    std::ranges::sort(ys);
    ys.erase(std::ranges::unique(ys).begin(), ys.end());

    std::vector<std::vector<std::tuple<long long, long long, int>>> update(
        ys.size());
    for (auto [l, d, r, u] : rects) {
        int cl = std::ranges::lower_bound(xs, l) - xs.begin();
        int cd = std::ranges::lower_bound(ys, d) - ys.begin();
        int cr = std::ranges::lower_bound(xs, r) - xs.begin();
        int cu = std::ranges::lower_bound(ys, u) - ys.begin();
        update[cd].push_back({cl, cr, 1});
        update[cu].push_back({cl, cr, -1});
    }

    std::vector<std::pair<int, int>> init(xs.size() - 1);
    for (int x = 0; x < (int)xs.size() - 1; ++x) {
        init[x] = {0, xs[x + 1] - xs[x]};
    }

    LazySegmentTree<CountMinMonoid, AddMonoid, act> st(init);
    long long ans = 0;
    long long xlen = xs.back() - xs[0];
    for (int y = 0; y < (int)ys.size() - 1; ++y) {
        for (auto [l, r, diff] : update[y]) {
            st.update(l, r, diff);
        }
        auto [minval, len0] = st.fold_all();
        if (minval > 0) len0 = 0;
        ans += (xlen - len0) * (ys[y + 1] - ys[y]);
    }
    return ans;
}

Back to top page