This documentation is automatically generated by online-judge-tools/verification-helper
#include "ds/rectangle_union.hpp"
#include "ds/segtree/lazy_segtree.hpp"
#include "alg/acted_monoid/minmincnt_add.hpp"
template <typename XY = int>
struct Rectangle_Union {
using RECT = tuple<XY, XY, XY, XY>;
vc<RECT> rectangles;
vc<XY> X, Y;
void add_rect(XY xl, XY xr, XY yl, XY yr) {
assert(xl < xr && yl < yr);
X.eb(xl), X.eb(xr), Y.eb(yl), Y.eb(yr);
rectangles.eb(xl, xr, yl, yr);
}
template <typename ANS_TYPE = ll>
ANS_TYPE calc() {
int N = len(X);
vc<int> ord_x = argsort(X);
vc<int> ord_y = argsort(Y);
vc<int> rk_y(N);
FOR(i, N) rk_y[ord_y[i]] = i;
X = rearrange(X, ord_x);
Y = rearrange(Y, ord_y);
using AM = ActedMonoid_MinMincnt_Add<XY>;
Lazy_SegTree<AM> seg(N - 1, [&](int i) -> pair<XY, XY> {
return {0, Y[i + 1] - Y[i]};
});
ANS_TYPE ANS = 0;
XY total = Y.back() - Y[0];
FOR(i, N - 1) {
int k = ord_x[i] / 2;
int a = (ord_x[i] & 1 ? -1 : 1);
seg.apply(rk_y[2 * k], rk_y[2 * k + 1], a);
auto [min, mincnt] = seg.prod_all();
ANS_TYPE dy = total - (min == 0 ? mincnt : 0);
ANS_TYPE dx = X[i + 1] - X[i];
ANS += dx * dy;
}
return ANS;
}
};
#line 2 "ds/segtree/lazy_segtree.hpp"
template <typename ActedMonoid>
struct Lazy_SegTree {
using AM = ActedMonoid;
using MX = typename AM::Monoid_X;
using MA = typename AM::Monoid_A;
using X = typename MX::value_type;
using A = typename MA::value_type;
int n, log, size;
vc<X> dat;
vc<A> laz;
Lazy_SegTree() {}
Lazy_SegTree(int n) { build(n); }
template <typename F>
Lazy_SegTree(int n, F f) {
build(n, f);
}
Lazy_SegTree(const vc<X>& v) { build(v); }
void build(int m) {
build(m, [](int i) -> X { return MX::unit(); });
}
void build(const vc<X>& v) {
build(len(v), [&](int i) -> X { return v[i]; });
}
template <typename F>
void build(int m, F f) {
n = m, log = 1;
while ((1 << log) < n) ++log;
size = 1 << log;
dat.assign(size << 1, MX::unit());
laz.assign(size, MA::unit());
FOR(i, n) dat[size + i] = f(i);
FOR_R(i, 1, size) update(i);
}
void update(int k) { dat[k] = MX::op(dat[2 * k], dat[2 * k + 1]); }
void set(int p, X x) {
assert(0 <= p && p < n);
p += size;
for (int i = log; i >= 1; i--) push(p >> i);
dat[p] = x;
for (int i = 1; i <= log; i++) update(p >> i);
}
void multiply(int p, const X& x) {
assert(0 <= p && p < n);
p += size;
for (int i = log; i >= 1; i--) push(p >> i);
dat[p] = MX::op(dat[p], x);
for (int i = 1; i <= log; i++) update(p >> i);
}
X get(int p) {
assert(0 <= p && p < n);
p += size;
for (int i = log; i >= 1; i--) push(p >> i);
return dat[p];
}
vc<X> get_all() {
FOR(k, 1, size) { push(k); }
return {dat.begin() + size, dat.begin() + size + n};
}
X prod(int l, int r) {
assert(0 <= l && l <= r && r <= n);
if (l == r) return MX::unit();
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);
}
X xl = MX::unit(), xr = MX::unit();
while (l < r) {
if (l & 1) xl = MX::op(xl, dat[l++]);
if (r & 1) xr = MX::op(dat[--r], xr);
l >>= 1, r >>= 1;
}
return MX::op(xl, xr);
}
X prod_all() { return dat[1]; }
void apply(int l, int r, A a) {
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) apply_at(l++, a);
if (r & 1) apply_at(--r, a);
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 <typename F>
int max_right(const F check, int l) {
assert(0 <= l && l <= n);
assert(check(MX::unit()));
if (l == n) return n;
l += size;
for (int i = log; i >= 1; i--) push(l >> i);
X sm = MX::unit();
do {
while (l % 2 == 0) l >>= 1;
if (!check(MX::op(sm, dat[l]))) {
while (l < size) {
push(l);
l = (2 * l);
if (check(MX::op(sm, dat[l]))) { sm = MX::op(sm, dat[l++]); }
}
return l - size;
}
sm = MX::op(sm, dat[l++]);
} while ((l & -l) != l);
return n;
}
template <typename F>
int min_left(const F check, int r) {
assert(0 <= r && r <= n);
assert(check(MX::unit()));
if (r == 0) return 0;
r += size;
for (int i = log; i >= 1; i--) push((r - 1) >> i);
X sm = MX::unit();
do {
r--;
while (r > 1 && (r % 2)) r >>= 1;
if (!check(MX::op(dat[r], sm))) {
while (r < size) {
push(r);
r = (2 * r + 1);
if (check(MX::op(dat[r], sm))) { sm = MX::op(dat[r--], sm); }
}
return r + 1 - size;
}
sm = MX::op(dat[r], sm);
} while ((r & -r) != r);
return 0;
}
private:
void apply_at(int k, A a) {
ll sz = 1 << (log - topbit(k));
dat[k] = AM::act(dat[k], a, sz);
if (k < size) laz[k] = MA::op(laz[k], a);
}
void push(int k) {
if (laz[k] == MA::unit()) return;
apply_at(2 * k, laz[k]), apply_at(2 * k + 1, laz[k]);
laz[k] = MA::unit();
}
};
#line 2 "alg/monoid/minmincnt.hpp"
// 最小値、最小値の個数
template <typename E>
struct Monoid_MinMincnt {
using value_type = pair<E, E>;
using X = value_type;
static X op(X x, X y) {
auto [xmin, xmincnt] = x;
auto [ymin, ymincnt] = y;
if (xmin > ymin) return y;
if (xmin < ymin) return x;
return {xmin, xmincnt + ymincnt};
}
static constexpr X unit() { return {infty<E>, 0}; }
static constexpr bool commute = true;
};
#line 2 "alg/monoid/add.hpp"
template <typename E>
struct Monoid_Add {
using X = E;
using value_type = X;
static constexpr X op(const X &x, const X &y) noexcept { return x + y; }
static constexpr X inverse(const X &x) noexcept { return -x; }
static constexpr X power(const X &x, ll n) noexcept { return X(n) * x; }
static constexpr X unit() { return X(0); }
static constexpr bool commute = true;
};
#line 3 "alg/acted_monoid/minmincnt_add.hpp"
template <typename E>
struct ActedMonoid_MinMincnt_Add {
using Monoid_X = Monoid_MinMincnt<E>;
using Monoid_A = Monoid_Add<E>;
using X = typename Monoid_X::value_type;
using A = typename Monoid_A::value_type;
static constexpr X act(const X &x, const A &a, const ll &size) {
auto [xmin, xmincnt] = x;
if (xmin == infty<E>) return x;
return {xmin + a, xmincnt};
}
};
#line 3 "ds/rectangle_union.hpp"
template <typename XY = int>
struct Rectangle_Union {
using RECT = tuple<XY, XY, XY, XY>;
vc<RECT> rectangles;
vc<XY> X, Y;
void add_rect(XY xl, XY xr, XY yl, XY yr) {
assert(xl < xr && yl < yr);
X.eb(xl), X.eb(xr), Y.eb(yl), Y.eb(yr);
rectangles.eb(xl, xr, yl, yr);
}
template <typename ANS_TYPE = ll>
ANS_TYPE calc() {
int N = len(X);
vc<int> ord_x = argsort(X);
vc<int> ord_y = argsort(Y);
vc<int> rk_y(N);
FOR(i, N) rk_y[ord_y[i]] = i;
X = rearrange(X, ord_x);
Y = rearrange(Y, ord_y);
using AM = ActedMonoid_MinMincnt_Add<XY>;
Lazy_SegTree<AM> seg(N - 1, [&](int i) -> pair<XY, XY> {
return {0, Y[i + 1] - Y[i]};
});
ANS_TYPE ANS = 0;
XY total = Y.back() - Y[0];
FOR(i, N - 1) {
int k = ord_x[i] / 2;
int a = (ord_x[i] & 1 ? -1 : 1);
seg.apply(rk_y[2 * k], rk_y[2 * k + 1], a);
auto [min, mincnt] = seg.prod_all();
ANS_TYPE dy = total - (min == 0 ? mincnt : 0);
ANS_TYPE dx = X[i + 1] - X[i];
ANS += dx * dy;
}
return ANS;
}
};