structure/others/union-rectangle.hpp

• View this file on GitHub
• Last update: 2024-05-01 23:44:47+09:00
• Include: #include "structure/others/union-rectangle.hpp"

Code

template <typename T>
struct UnionRectangle {
  map<T, T> data;
  int64 sum;

  UnionRectangle() : sum(0) {
    const T INF = numeric_limits<T>::max();
    data[0] = INF;
    data[INF] = 0;
  }
  void add_point(T x, T y) {
    auto p = data.lower_bound(x);
    if (p->second >= y) return;
    const T nxtY = p->second;
    --p;
    while (p->second <= y) {
      auto it = *p;
      p = --data.erase(p);
      sum -= (it.first - p->first) * (it.second - nxtY);
    }
    sum += (x - p->first) * (y - nxtY);
    data[x] = y;
  }

  int64 get() { return sum; }
};

#line 1 "structure/others/union-rectangle.hpp"
template <typename T>
struct UnionRectangle {
  map<T, T> data;
  int64 sum;

  UnionRectangle() : sum(0) {
    const T INF = numeric_limits<T>::max();
    data[0] = INF;
    data[INF] = 0;
  }
  void add_point(T x, T y) {
    auto p = data.lower_bound(x);
    if (p->second >= y) return;
    const T nxtY = p->second;
    --p;
    while (p->second <= y) {
      auto it = *p;
      p = --data.erase(p);
      sum -= (it.first - p->first) * (it.second - nxtY);
    }
    sum += (x - p->first) * (y - nxtY);
    data[x] = y;
  }

  int64 get() { return sum; }
};

Back to top page