Area of Union of Rectangles
(data-structure/rectangle-union-area.hpp)

• View this file on GitHub
• Last update: 2026-09-05 04:46:11+09:00
• Include: #include "data-structure/rectangle-union-area.hpp"

長方形の和集合の面積を求める．

RectangleUnionArea<I> として使う．座標と面積の型 I の既定値は long long．長方形は半開領域 $[lx,rx)\times[ly,ry)$ で表す．

• add_rectangle(lx, rx, ly, ry)：$lx<rx$ かつ $ly<ry$ を満たす長方形を追加する．
• calc()：追加した長方形の和集合の面積を返す．

長方形の個数を $N$ として，calc() は $O(N\log N)$ 時間，$O(N)$ 空間．

アルゴリズム

$x$ 座標順に長方形の左辺と右辺を処理する．$y$ 座標を座標圧縮し，各区間を覆う長方形の個数の最小値と，その最小値を取る区間幅を Lazy Segment Tree で管理する．隣り合うイベント間の幅と，少なくとも一つの長方形に覆われる $y$ 方向の長さの積を加算する．

資料

• Library Checker: Area of Union of Rectangles

Depends on

• algebraic-structure/magma.hpp
• algebraic-structure/monoid-action.hpp
• algebraic-structure/monoid.hpp
• algebraic-structure/util.hpp
• Lazy Segment Tree (segment-tree/lazy-segment-tree.hpp)

Verified with

• verify/data-structure/LC_area_of_union_of_rectangles.test.cpp

Code

#pragma once

#include "segment-tree/lazy-segment-tree.hpp"

template <class I = long long>
struct RectangleUnionArea {
  void add_rectangle(I lx, I rx, I ly, I ry) {
    assert(lx < rx && ly < ry);
    rects.push_back({lx, rx, ly, ry});
  }
  I calc() const {
    if (rects.empty()) return I(0);
    struct Event {
      I x;
      int l, r, add;
      bool operator<(const Event& e) const { return x < e.x; }
    };
    vector<I> ys;
    ys.reserve(rects.size() * 2);
    for (auto [lx, rx, ly, ry] : rects) ys.push_back(ly), ys.push_back(ry);
    sort(ys.begin(), ys.end());
    ys.erase(unique(ys.begin(), ys.end()), ys.end());
    vector<Event> events;
    events.reserve(rects.size() * 2);
    for (auto [lx, rx, ly, ry] : rects) {
      int l = LB(ys, ly), r = LB(ys, ry);
      events.push_back({lx, l, r, 1});
      events.push_back({rx, l, r, -1});
    }
    sort(events.begin(), events.end());
    vector<T> data(ys.size() - 1);
    for (int i = 0; i + 1 < (int)ys.size(); i++) data[i] = {0, ys[i + 1] - ys[i]};
    LazySegmentTree<Action> seg(data);
    I ret = 0, covered = 0, prev = events[0].x;
    for (int i = 0; i < (int)events.size();) {
      I x = events[i].x;
      ret += (x - prev) * covered;
      while (i < (int)events.size() && events[i].x == x) {
        seg.apply(events[i].l, events[i].r, events[i].add);
        i++;
      }
      auto [mn, width] = seg.all_prod();
      covered = ys.back() - ys.front() - (mn == 0 ? width : I(0));
      prev = x;
    }
    return ret;
  }

 private:
  using T = pair<int, I>;
  struct ValueMonoid {
    using value_type = T;
    static T op(T x, T y) {
      if (x.first == y.first) return {x.first, x.second + y.second};
      return x.first < y.first ? x : y;
    }
    static T e() { return {1 << 30, I(0)}; }
  };
  struct OperatorMonoid {
    using value_type = int;
    static int op(int x, int y) { return x + y; }
    static int e() { return 0; }
  };
  struct Action {
    using value_monoid = ValueMonoid;
    using operator_monoid = OperatorMonoid;
    static T mapping(int f, T x) { return {x.first + f, x.second}; }
  };
  vector<array<I, 4>> rects;
};

/**
 * @brief Area of Union of Rectangles
 * @docs docs/data-structure/rectangle-union-area.md
 */

#line 2 "data-structure/rectangle-union-area.hpp"

#line 2 "algebraic-structure/util.hpp"
#ifdef __cpp_concepts
#define REQUIRES(...) requires __VA_ARGS__
#else
#define REQUIRES(...)
#endif
#line 3 "algebraic-structure/magma.hpp"

#ifdef __cpp_concepts
template <class M>
concept Magma = requires(typename M::value_type x, typename M::value_type y) {
  typename M::value_type;
  { M::op(x, y) } -> same_as<typename M::value_type>;
};
#endif

template <class T>
struct AddMagma {
  using value_type = T;
  static T op(T x, T y) { return x + y; }
};
template <class T>
struct MulMagma {
  using value_type = T;
  static T op(T x, T y) { return x * y; }
};
template <class T, T id>
struct MaxMagma {
  using value_type = T;
  static T op(T x, T y) { return x > y ? x : y; }
};
template <class T, T id>
struct MinMagma {
  using value_type = T;
  static T op(T x, T y) { return x < y ? x : y; }
};
#line 3 "algebraic-structure/monoid.hpp"

#ifdef __cpp_concepts
template <class M>
concept Monoid = Magma<M> && requires {
  { M::e() } -> same_as<typename M::value_type>;
};
#endif

template <class T>
struct AddMonoid {
  using value_type = T;
  static T op(T x, T y) { return x + y; }
  static T e() { return T(0); }
};
template <class T>
struct MulMonoid {
  using value_type = T;
  static T op(T x, T y) { return x * y; }
  static T e() { return T(1); }
};
template <class T, T id>
struct MaxMonoid {
  using value_type = T;
  static T op(T x, T y) { return x > y ? x : y; }
  static T e() { return id; }
};
template <class T, T id>
struct MinMonoid {
  using value_type = T;
  static T op(T x, T y) { return x < y ? x : y; }
  static T e() { return id; }
};
#line 3 "algebraic-structure/monoid-action.hpp"

#ifdef __cpp_concepts
template <class A>
concept MonoidAction = Monoid<typename A::value_monoid> && Monoid<typename A::operator_monoid> && requires(typename A::value_monoid::value_type x, typename A::operator_monoid::value_type f) {
  typename A::value_monoid;
  typename A::operator_monoid;
  { A::mapping(f, x) } -> same_as<typename A::value_monoid::value_type>;
};
#endif
#line 3 "segment-tree/lazy-segment-tree.hpp"

template <class A>
REQUIRES(MonoidAction<A>)
struct LazySegmentTree {
  using VM = typename A::value_monoid;
  using OM = typename A::operator_monoid;
  using T = typename VM::value_type;
  using F = typename OM::value_type;

 protected:
  int _n, size, log;
  vector<T> d;
  vector<F> lz;

  void update(int k) { d[k] = VM::op(d[2 * k], d[2 * k + 1]); }
  virtual void all_apply(int k, F f) {
    d[k] = A::mapping(f, d[k]);
    if (k < size) lz[k] = OM::op(f, lz[k]);
  }
  void push(int k) {
    all_apply(2 * k, lz[k]);
    all_apply(2 * k + 1, lz[k]);
    lz[k] = OM::e();
  }

 public:
  LazySegmentTree() : LazySegmentTree(0) {}
  explicit LazySegmentTree(int n) : LazySegmentTree(vector<T>(n, VM::e())) {}
  explicit LazySegmentTree(const vector<T>& v) : _n(int(v.size())) {
    size = 1, log = 0;
    while (size < _n) size <<= 1, log++;
    d = vector<T>(2 * size, VM::e());
    lz = vector<F>(size, OM::e());
    for (int i = 0; i < _n; i++) d[size + i] = v[i];
    for (int i = size - 1; i > 0; i--) update(i);
  }
  virtual ~LazySegmentTree() = default;

  void set(int p, T x) {
    assert(0 <= p && p < _n);
    p += size;
    for (int i = log; i >= 1; i--) push(p >> i);
    d[p] = x;
    for (int i = 1; i <= log; i++) update(p >> i);
  }
  T get(int p) {
    assert(0 <= p && p < _n);
    p += size;
    for (int i = log; i >= 1; i--) push(p >> i);
    return d[p];
  }
  T prod(int l, int r) {
    assert(0 <= l && l <= r && r <= _n);
    if (l == r) return VM::e();
    l += size, r += size;
    for (int i = log; i >= 1; i--) {
      if (((l >> i) << i) != l) push(l >> i);
      if (((r >> i) << i) != r) push((r - 1) >> i);
    }
    T sml = VM::e(), smr = VM::e();
    while (l < r) {
      if (l & 1) sml = VM::op(sml, d[l++]);
      if (r & 1) smr = VM::op(d[--r], smr);
      l >>= 1, r >>= 1;
    }
    return VM::op(sml, smr);
  }
  T all_prod() { return d[1]; }
  void apply(int p, F f) {
    assert(0 <= p && p < _n);
    p += size;
    for (int i = log; i >= 1; i--) push(p >> i);
    d[p] = A::mapping(f, d[p]);
    for (int i = 1; i <= log; i++) update(p >> i);
  }
  void apply(int l, int r, F f) {
    assert(0 <= l && l <= r && r <= _n);
    if (l == r) return;
    l += size, r += size;
    for (int i = log; i >= 1; i--) {
      if (((l >> i) << i) != l) push(l >> i);
      if (((r >> i) << i) != r) push((r - 1) >> i);
    }
    {
      int l2 = l, r2 = r;
      while (l < r) {
        if (l & 1) all_apply(l++, f);
        if (r & 1) all_apply(--r, f);
        l >>= 1, r >>= 1;
      }
      l = l2, r = r2;
    }
    for (int i = 1; i <= log; i++) {
      if (((l >> i) << i) != l) update(l >> i);
      if (((r >> i) << i) != r) update((r - 1) >> i);
    }
  }
  template <bool (*g)(T)>
  int max_right(int l) {
    return max_right(l, [](T x) { return g(x); });
  }
  template <class G>
  int max_right(int l, G g) {
    assert(0 <= l && l <= _n);
    assert(g(VM::e()));
    if (l == _n) return _n;
    l += size;
    for (int i = log; i >= 1; i--) push(l >> i);
    T sm = VM::e();
    do {
      while (l % 2 == 0) l >>= 1;
      if (!g(VM::op(sm, d[l]))) {
        while (l < size) {
          push(l);
          l = (2 * l);
          if (g(VM::op(sm, d[l]))) sm = VM::op(sm, d[l++]);
        }
        return l - size;
      }
      sm = VM::op(sm, d[l++]);
    } while ((l & -l) != l);
    return _n;
  }

  template <bool (*g)(T)>
  int min_left(int r) {
    return min_left(r, [](T x) { return g(x); });
  }
  template <class G>
  int min_left(int r, G g) {
    assert(0 <= r && r <= _n);
    assert(g(VM::e()));
    if (r == 0) return 0;
    r += size;
    for (int i = log; i >= 1; i--) push((r - 1) >> i);
    T sm = VM::e();
    do {
      r--;
      while (r > 1 && (r % 2)) r >>= 1;
      if (!g(VM::op(d[r], sm))) {
        while (r < size) {
          push(r);
          r = (2 * r + 1);
          if (g(VM::op(d[r], sm))) sm = VM::op(d[r--], sm);
        }
        return r + 1 - size;
      }
      sm = VM::op(d[r], sm);
    } while ((r & -r) != r);
    return 0;
  }
};

/**
 * @brief Lazy Segment Tree
 * @docs docs/segment-tree/lazy-segment-tree.md
 */
#line 4 "data-structure/rectangle-union-area.hpp"

template <class I = long long>
struct RectangleUnionArea {
  void add_rectangle(I lx, I rx, I ly, I ry) {
    assert(lx < rx && ly < ry);
    rects.push_back({lx, rx, ly, ry});
  }
  I calc() const {
    if (rects.empty()) return I(0);
    struct Event {
      I x;
      int l, r, add;
      bool operator<(const Event& e) const { return x < e.x; }
    };
    vector<I> ys;
    ys.reserve(rects.size() * 2);
    for (auto [lx, rx, ly, ry] : rects) ys.push_back(ly), ys.push_back(ry);
    sort(ys.begin(), ys.end());
    ys.erase(unique(ys.begin(), ys.end()), ys.end());
    vector<Event> events;
    events.reserve(rects.size() * 2);
    for (auto [lx, rx, ly, ry] : rects) {
      int l = LB(ys, ly), r = LB(ys, ry);
      events.push_back({lx, l, r, 1});
      events.push_back({rx, l, r, -1});
    }
    sort(events.begin(), events.end());
    vector<T> data(ys.size() - 1);
    for (int i = 0; i + 1 < (int)ys.size(); i++) data[i] = {0, ys[i + 1] - ys[i]};
    LazySegmentTree<Action> seg(data);
    I ret = 0, covered = 0, prev = events[0].x;
    for (int i = 0; i < (int)events.size();) {
      I x = events[i].x;
      ret += (x - prev) * covered;
      while (i < (int)events.size() && events[i].x == x) {
        seg.apply(events[i].l, events[i].r, events[i].add);
        i++;
      }
      auto [mn, width] = seg.all_prod();
      covered = ys.back() - ys.front() - (mn == 0 ? width : I(0));
      prev = x;
    }
    return ret;
  }

 private:
  using T = pair<int, I>;
  struct ValueMonoid {
    using value_type = T;
    static T op(T x, T y) {
      if (x.first == y.first) return {x.first, x.second + y.second};
      return x.first < y.first ? x : y;
    }
    static T e() { return {1 << 30, I(0)}; }
  };
  struct OperatorMonoid {
    using value_type = int;
    static int op(int x, int y) { return x + y; }
    static int e() { return 0; }
  };
  struct Action {
    using value_monoid = ValueMonoid;
    using operator_monoid = OperatorMonoid;
    static T mapping(int f, T x) { return {x.first + f, x.second}; }
  };
  vector<array<I, 4>> rects;
};

/**
 * @brief Area of Union of Rectangles
 * @docs docs/data-structure/rectangle-union-area.md
 */

Back to top page