proconlib

This documentation is automatically generated by competitive-verifier/competitive-verifier

View the Project on GitHub anqooqie/proconlib

:heavy_check_mark: Area of union of rectangles (tools/rectangle_union_area.hpp)

Given $N$ rectangles, it returns the area of the union set of the rectangles in $O(N \log N)$ time.

License

Author

Constructor

rectangle_union_area<T> rs();

It creates an empty list of rectangles.

Constraints

Time Complexity

size

std::size_t rs.size();

It returns the number of rectangles in the list.

Constraints

Time Complexity

add_rectangle

std::size_t rs.add_rectangle(T l, T r, T d, T u);

It adds a rectangle represented by $\{(x, y) \mid l \leq x \leq y \land d \leq y \leq u \}$. It returns an integer $k$ such that this is the $k$-th rectangle that is added.

Constraints

Time Complexity

get_rectangle

std::tuple<T, T, T, T> rs.get_rectangle(std::size_t k);

It returns $(l, r, d, u)$ such that the $k$-th rectangle is represented by $\{(x, y) \mid l \leq x \leq y \land d \leq y \leq u \}$.

Constraints

Time Complexity

rectangles

const std::vector<std::tuple<T, T, T, T>>& rs.rectangles();

It returns all the rectangles in the list. The rectangles are ordered in the same order as added by add_rectangle.

Constraints

Time Complexity

query

T rs.query();

It returns the area of the union set of the rectangles.

Constraints

Time Complexity

Depends on

Verified with

Code

#ifndef TOOLS_RECTNAGLE_UNION_AREA_HPP
#define TOOLS_RECTNAGLE_UNION_AREA_HPP

#include <utility>
#include <limits>
#include <vector>
#include <tuple>
#include <cstddef>
#include <cassert>
#include "atcoder/lazysegtree.hpp"
#include "tools/compressor.hpp"

namespace tools {
  template <typename T>
  class rectangle_union_area {
  private:
    using S = ::std::pair<int, T>;
    static S op(const S& x, const S& y) {
      return x.first < y.first ? x : x.first > y.first ? y : S(x.first, x.second + y.second);
    }
    static S e() {
      return S(::std::numeric_limits<int>::max(), 0);
    }
    using F = int;
    static S mapping(const F& f, const S& x) {
      return S(f + x.first, x.second);
    }
    static F composition(const F& f, const F& g) {
      return f + g;
    }
    static F id() {
      return 0;
    }

    ::std::vector<::std::tuple<T, T, T, T>> m_rectangles;

  public:
    rectangle_union_area() = default;
    rectangle_union_area(const ::tools::rectangle_union_area<T>&) = default;
    rectangle_union_area(::tools::rectangle_union_area<T>&&) = default;
    ~rectangle_union_area() = default;
    ::tools::rectangle_union_area<T>& operator=(const ::tools::rectangle_union_area<T>&) = default;
    ::tools::rectangle_union_area<T>& operator=(::tools::rectangle_union_area<T>&&) = default;

    ::std::size_t size() const {
      return this->m_rectangle.size();
    }

    ::std::size_t add_rectangle(const T l, const T r, const T d, const T u) {
      assert(l < r);
      assert(d < u);
      this->m_rectangles.emplace_back(l, r, d, u);
      return this->m_rectangles.size() - 1;
    }

    const ::std::tuple<T, T, T, T>& get_rectangle(const ::std::size_t k) const {
      assert(k < this->m_rectangles.size());
      return this->m_rectangles[k];
    }

    const ::std::vector<::std::tuple<T, T, T, T>>& rectangles() const {
      return this->m_rectangles;
    }

    T query() const {
      ::std::vector<T> x_list, y_list;
      for (const auto& [l, r, d, u] : this->m_rectangles) {
        x_list.push_back(l);
        x_list.push_back(r);
        y_list.push_back(d);
        y_list.push_back(u);
      }
      ::tools::compressor<T> x_comp(x_list), y_comp(y_list);

      ::std::vector<::std::pair<::std::vector<::std::size_t>, ::std::vector<::std::size_t>>> sorted_rectangles(x_comp.size() + 1);
      for (::std::size_t i = 0; i < this->m_rectangles.size(); ++i) {
        const auto& [l, r, d, u] = this->m_rectangles[i];
        sorted_rectangles[x_comp.compress(l)].first.push_back(i);
        sorted_rectangles[x_comp.compress(r)].second.push_back(i);
      }

      ::std::vector<S> v;
      for (decltype(y_comp.size()) i = 0; i + 1 < y_comp.size(); ++i) {
        v.emplace_back(0, y_comp.decompress(i + 1) - y_comp.decompress(i));
      }
      ::atcoder::lazy_segtree<S, op, e, F, mapping, composition, id> lazy_segtree(v);
      const T H = lazy_segtree.all_prod().second;

      T answer = 0;
      for (decltype(x_comp.size()) i = 0; i + 1 < x_comp.size(); ++i) {
        for (const auto k : sorted_rectangles[i].first) {
          const auto& [l, r, d, u] = this->m_rectangles[k];
          lazy_segtree.apply(y_comp.compress(d), y_comp.compress(u), 1);
        }
        for (const auto k : sorted_rectangles[i].second) {
          const auto& [l, r, d, u] = this->m_rectangles[k];
          lazy_segtree.apply(y_comp.compress(d), y_comp.compress(u), -1);
        }
        answer += (x_comp.decompress(i + 1) - x_comp.decompress(i)) * (H - (lazy_segtree.all_prod().first > 0 ? 0 : lazy_segtree.all_prod().second));
      }

      return answer;
    }
  };
}

#endif

#line 1 "tools/rectangle_union_area.hpp"



#include <utility>
#include <limits>
#include <vector>
#include <tuple>
#include <cstddef>
#include <cassert>
#line 1 "lib/ac-library/atcoder/lazysegtree.hpp"



#include <algorithm>
#line 6 "lib/ac-library/atcoder/lazysegtree.hpp"
#include <functional>
#line 8 "lib/ac-library/atcoder/lazysegtree.hpp"

#line 1 "lib/ac-library/atcoder/internal_bit.hpp"



#ifdef _MSC_VER
#include <intrin.h>
#endif

#if __cplusplus >= 202002L
#include <bit>
#endif

namespace atcoder {

namespace internal {

#if __cplusplus >= 202002L

using std::bit_ceil;

#else

// @return same with std::bit::bit_ceil
unsigned int bit_ceil(unsigned int n) {
    unsigned int x = 1;
    while (x < (unsigned int)(n)) x *= 2;
    return x;
}

#endif

// @param n `1 <= n`
// @return same with std::bit::countr_zero
int countr_zero(unsigned int n) {
#ifdef _MSC_VER
    unsigned long index;
    _BitScanForward(&index, n);
    return index;
#else
    return __builtin_ctz(n);
#endif
}

// @param n `1 <= n`
// @return same with std::bit::countr_zero
constexpr int countr_zero_constexpr(unsigned int n) {
    int x = 0;
    while (!(n & (1 << x))) x++;
    return x;
}

}  // namespace internal

}  // namespace atcoder


#line 10 "lib/ac-library/atcoder/lazysegtree.hpp"

namespace atcoder {

#if __cplusplus >= 201703L

template <class S,
          auto op,
          auto e,
          class F,
          auto mapping,
          auto composition,
          auto id>
struct lazy_segtree {
    static_assert(std::is_convertible_v<decltype(op), std::function<S(S, S)>>,
                  "op must work as S(S, S)");
    static_assert(std::is_convertible_v<decltype(e), std::function<S()>>,
                  "e must work as S()");
    static_assert(
        std::is_convertible_v<decltype(mapping), std::function<S(F, S)>>,
        "mapping must work as F(F, S)");
    static_assert(
        std::is_convertible_v<decltype(composition), std::function<F(F, F)>>,
        "compostiion must work as F(F, F)");
    static_assert(std::is_convertible_v<decltype(id), std::function<F()>>,
                  "id must work as F()");

#else

template <class S,
          S (*op)(S, S),
          S (*e)(),
          class F,
          S (*mapping)(F, S),
          F (*composition)(F, F),
          F (*id)()>
struct lazy_segtree {

#endif

  public:
    lazy_segtree() : lazy_segtree(0) {}
    explicit lazy_segtree(int n) : lazy_segtree(std::vector<S>(n, e())) {}
    explicit lazy_segtree(const std::vector<S>& v) : _n(int(v.size())) {
        size = (int)internal::bit_ceil((unsigned int)(_n));
        log = internal::countr_zero((unsigned int)size);
        d = std::vector<S>(2 * size, e());
        lz = std::vector<F>(size, id());
        for (int i = 0; i < _n; i++) d[size + i] = v[i];
        for (int i = size - 1; i >= 1; i--) {
            update(i);
        }
    }

    void set(int p, S 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);
    }

    S get(int p) {
        assert(0 <= p && p < _n);
        p += size;
        for (int i = log; i >= 1; i--) push(p >> i);
        return d[p];
    }

    S prod(int l, int r) {
        assert(0 <= l && l <= r && r <= _n);
        if (l == r) return 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);
        }

        S sml = e(), smr = e();
        while (l < r) {
            if (l & 1) sml = op(sml, d[l++]);
            if (r & 1) smr = op(d[--r], smr);
            l >>= 1;
            r >>= 1;
        }

        return op(sml, smr);
    }

    S 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] = 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)(S)> int max_right(int l) {
        return max_right(l, [](S x) { return g(x); });
    }
    template <class G> int max_right(int l, G g) {
        assert(0 <= l && l <= _n);
        assert(g(e()));
        if (l == _n) return _n;
        l += size;
        for (int i = log; i >= 1; i--) push(l >> i);
        S sm = e();
        do {
            while (l % 2 == 0) l >>= 1;
            if (!g(op(sm, d[l]))) {
                while (l < size) {
                    push(l);
                    l = (2 * l);
                    if (g(op(sm, d[l]))) {
                        sm = op(sm, d[l]);
                        l++;
                    }
                }
                return l - size;
            }
            sm = op(sm, d[l]);
            l++;
        } while ((l & -l) != l);
        return _n;
    }

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

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

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

}  // namespace atcoder


#line 1 "tools/compressor.hpp"



#line 1 "tools/lower_bound.hpp"



#include <iterator>
#line 6 "tools/lower_bound.hpp"

namespace tools {

  template <class ForwardIterator, class T>
  auto lower_bound(ForwardIterator first, ForwardIterator last, const T& value) {
    return ::std::distance(first, ::std::lower_bound(first, last, value));
  }

  template <class ForwardIterator, class T, class Compare>
  auto lower_bound(ForwardIterator first, ForwardIterator last, const T& value, Compare comp) {
    return ::std::distance(first, ::std::lower_bound(first, last, value, comp));
  }
}


#line 8 "tools/compressor.hpp"

namespace tools {
  template <typename T>
  class compressor {
  private:
    ::std::vector<T> m_sorted;

  public:
    compressor() = default;
    compressor(const ::tools::compressor<T>&) = default;
    compressor(::tools::compressor<T>&&) = default;
    ~compressor() = default;
    ::tools::compressor<T>& operator=(const ::tools::compressor<T>&) = default;
    ::tools::compressor<T>& operator=(::tools::compressor<T>&&) = default;

    template <typename InputIterator>
    compressor(InputIterator begin, InputIterator end) : m_sorted(begin, end) {
      ::std::sort(this->m_sorted.begin(), this->m_sorted.end());
      this->m_sorted.erase(::std::unique(this->m_sorted.begin(), this->m_sorted.end()), this->m_sorted.end());
    }
    explicit compressor(const ::std::vector<T>& v) : compressor(v.begin(), v.end()) {
    }

    T size() const {
      return this->m_sorted.size();
    }
    T compress(const T& x) const {
      const T i = ::tools::lower_bound(this->m_sorted.begin(), this->m_sorted.end(), x);
      assert(i < this->size());
      assert(this->m_sorted[i] == x);
      return i;
    }
    T decompress(const T& i) const {
      assert(0 <= i && i < this->size());
      return this->m_sorted[i];
    }

    auto begin() {
      return this->m_sorted.cbegin();
    }
    auto begin() const {
      return this->m_sorted.cbegin();
    }
    auto end() {
      return this->m_sorted.cend();
    }
    auto end() const {
      return this->m_sorted.cend();
    }
  };
}


#line 12 "tools/rectangle_union_area.hpp"

namespace tools {
  template <typename T>
  class rectangle_union_area {
  private:
    using S = ::std::pair<int, T>;
    static S op(const S& x, const S& y) {
      return x.first < y.first ? x : x.first > y.first ? y : S(x.first, x.second + y.second);
    }
    static S e() {
      return S(::std::numeric_limits<int>::max(), 0);
    }
    using F = int;
    static S mapping(const F& f, const S& x) {
      return S(f + x.first, x.second);
    }
    static F composition(const F& f, const F& g) {
      return f + g;
    }
    static F id() {
      return 0;
    }

    ::std::vector<::std::tuple<T, T, T, T>> m_rectangles;

  public:
    rectangle_union_area() = default;
    rectangle_union_area(const ::tools::rectangle_union_area<T>&) = default;
    rectangle_union_area(::tools::rectangle_union_area<T>&&) = default;
    ~rectangle_union_area() = default;
    ::tools::rectangle_union_area<T>& operator=(const ::tools::rectangle_union_area<T>&) = default;
    ::tools::rectangle_union_area<T>& operator=(::tools::rectangle_union_area<T>&&) = default;

    ::std::size_t size() const {
      return this->m_rectangle.size();
    }

    ::std::size_t add_rectangle(const T l, const T r, const T d, const T u) {
      assert(l < r);
      assert(d < u);
      this->m_rectangles.emplace_back(l, r, d, u);
      return this->m_rectangles.size() - 1;
    }

    const ::std::tuple<T, T, T, T>& get_rectangle(const ::std::size_t k) const {
      assert(k < this->m_rectangles.size());
      return this->m_rectangles[k];
    }

    const ::std::vector<::std::tuple<T, T, T, T>>& rectangles() const {
      return this->m_rectangles;
    }

    T query() const {
      ::std::vector<T> x_list, y_list;
      for (const auto& [l, r, d, u] : this->m_rectangles) {
        x_list.push_back(l);
        x_list.push_back(r);
        y_list.push_back(d);
        y_list.push_back(u);
      }
      ::tools::compressor<T> x_comp(x_list), y_comp(y_list);

      ::std::vector<::std::pair<::std::vector<::std::size_t>, ::std::vector<::std::size_t>>> sorted_rectangles(x_comp.size() + 1);
      for (::std::size_t i = 0; i < this->m_rectangles.size(); ++i) {
        const auto& [l, r, d, u] = this->m_rectangles[i];
        sorted_rectangles[x_comp.compress(l)].first.push_back(i);
        sorted_rectangles[x_comp.compress(r)].second.push_back(i);
      }

      ::std::vector<S> v;
      for (decltype(y_comp.size()) i = 0; i + 1 < y_comp.size(); ++i) {
        v.emplace_back(0, y_comp.decompress(i + 1) - y_comp.decompress(i));
      }
      ::atcoder::lazy_segtree<S, op, e, F, mapping, composition, id> lazy_segtree(v);
      const T H = lazy_segtree.all_prod().second;

      T answer = 0;
      for (decltype(x_comp.size()) i = 0; i + 1 < x_comp.size(); ++i) {
        for (const auto k : sorted_rectangles[i].first) {
          const auto& [l, r, d, u] = this->m_rectangles[k];
          lazy_segtree.apply(y_comp.compress(d), y_comp.compress(u), 1);
        }
        for (const auto k : sorted_rectangles[i].second) {
          const auto& [l, r, d, u] = this->m_rectangles[k];
          lazy_segtree.apply(y_comp.compress(d), y_comp.compress(u), -1);
        }
        answer += (x_comp.decompress(i + 1) - x_comp.decompress(i)) * (H - (lazy_segtree.all_prod().first > 0 ? 0 : lazy_segtree.all_prod().second));
      }

      return answer;
    }
  };
}
Back to top page