This documentation is automatically generated by online-judge-tools/verification-helper
#include "other/cuboid_union_volume.hpp"
#include "ds/incremental_rectangle_union.hpp"
// [0,a] x [0,b] x [0,c] の和集合の体積
// https://codeforces.com/contest/815/problem/D
template <typename XYZ, typename T, bool SMALL_X>
T cuboid_union_volume(vc<tuple<XYZ, XYZ, XYZ>> dat) {
if constexpr (SMALL_X) {
int mx_x = 0, mx_z = 0;
for (auto& [x, y, z]: dat) chmax(mx_x, x), chmax(mx_z, z);
vc<int> ptr(mx_z + 1);
for (auto& [x, y, z]: dat) ptr[z]++;
ptr = cumsum<int>(ptr);
vc<pair<int, int>> rect(len(dat));
for (auto& [x, y, z]: dat) { rect[ptr[z]++] = {x, y}; }
T vol = 0;
Incremental_Rectangle_Union<XYZ, T, true> I(mx_x);
FOR_R(z, 1, mx_z + 1) {
FOR(i, ptr[z - 1], ptr[z]) {
auto [a, b] = rect[i];
I.add(a, b);
}
vol += I.area;
}
return vol;
} else {
sort(all(dat),
[&](auto& a, auto& b) -> bool { return get<2>(a) > get<2>(b); });
XYZ z = infty<XYZ>;
T vol = 0, area = 0;
Incremental_Rectangle_Union<XYZ, T, false> I;
for (auto& [a, b, c]: dat) {
vol += T(z - c) * area, area = I.add(a, b), z = c;
}
vol += z * I.area;
return vol;
}
}
#line 1 "ds/incremental_rectangle_union.hpp"
#line 2 "ds/fastset.hpp"
// 64-ary tree
// space: (N/63) * u64
struct FastSet {
static constexpr u32 B = 64;
int n, log;
vvc<u64> seg;
FastSet() {}
FastSet(int n) { build(n); }
int size() { return n; }
template <typename F>
FastSet(int n, F f) {
build(n, f);
}
void build(int m) {
seg.clear();
n = m;
do {
seg.push_back(vc<u64>((m + B - 1) / B));
m = (m + B - 1) / B;
} while (m > 1);
log = len(seg);
}
template <typename F>
void build(int n, F f) {
build(n);
FOR(i, n) { seg[0][i / B] |= u64(f(i)) << (i % B); }
FOR(h, log - 1) {
FOR(i, len(seg[h])) {
seg[h + 1][i / B] |= u64(bool(seg[h][i])) << (i % B);
}
}
}
bool operator[](int i) const { return seg[0][i / B] >> (i % B) & 1; }
void insert(int i) {
for (int h = 0; h < log; h++) {
seg[h][i / B] |= u64(1) << (i % B), i /= B;
}
}
void add(int i) { insert(i); }
void erase(int i) {
u64 x = 0;
for (int h = 0; h < log; h++) {
seg[h][i / B] &= ~(u64(1) << (i % B));
seg[h][i / B] |= x << (i % B);
x = bool(seg[h][i / B]);
i /= B;
}
}
void remove(int i) { erase(i); }
// min[x,n) or n
int next(int i) {
assert(i <= n);
chmax(i, 0);
for (int h = 0; h < log; h++) {
if (i / B == seg[h].size()) break;
u64 d = seg[h][i / B] >> (i % B);
if (!d) {
i = i / B + 1;
continue;
}
i += lowbit(d);
for (int g = h - 1; g >= 0; g--) {
i *= B;
i += lowbit(seg[g][i / B]);
}
return i;
}
return n;
}
// max [0,x], or -1
int prev(int i) {
assert(i >= -1);
if (i >= n) i = n - 1;
for (int h = 0; h < log; h++) {
if (i == -1) break;
u64 d = seg[h][i / B] << (63 - i % B);
if (!d) {
i = i / B - 1;
continue;
}
i -= __builtin_clzll(d);
for (int g = h - 1; g >= 0; g--) {
i *= B;
i += topbit(seg[g][i / B]);
}
return i;
}
return -1;
}
bool any(int l, int r) { return next(l) < r; }
// [l, r)
template <typename F>
void enumerate(int l, int r, F f) {
for (int x = next(l); x < r; x = next(x + 1)) f(x);
}
string to_string() {
string s(n, '?');
for (int i = 0; i < n; ++i) s[i] = ((*this)[i] ? '1' : '0');
return s;
}
};
#line 3 "ds/incremental_rectangle_union.hpp"
// [0, x] x [0, y] を追加 -> 和集合面積を取得
template <typename XY, typename AREA, bool SMALL_XY>
struct Incremental_Rectangle_Union {
FastSet ss;
vc<XY> ht;
map<XY, XY> MP; // right end -> height
AREA area;
Incremental_Rectangle_Union() : area(AREA(0)) {
static_assert(!SMALL_XY);
MP[0] = infty<XY>, MP[infty<XY>] = 0;
}
Incremental_Rectangle_Union(int LIM)
: ss(LIM + 1), ht(LIM + 1), area(AREA(0)) {
static_assert(SMALL_XY);
ht[0] = infty<XY>, ht[LIM] = 0, ss.insert(0), ss.insert(LIM);
}
AREA add(XY x, XY y) {
if constexpr (SMALL_XY) add_fast(x, y);
if constexpr (!SMALL_XY) add_MP(x, y);
return area;
}
void reset() {
area = 0;
if constexpr (SMALL_XY) {
int LIM = len(ss) - 1;
ss.enumerate(0, LIM + 1, [&](int i) -> void { ss.erase(i); });
ht[0] = infty<XY>, ht[LIM] = 0, ss.insert(0), ss.insert(LIM);
} else {
MP.clear(), MP[0] = infty<XY>, MP[infty<XY>] = 0;
}
}
private:
void add_MP(XY x, XY y) {
if (x == 0 || y == 0) return;
auto it = MP.lower_bound(x);
auto [rx, ry] = *it;
if (ry >= y) return;
// split
if (x < rx) MP[x] = ry;
it = MP.find(x);
while (1) {
auto [x2, y2] = *it;
it = prev(MP.erase(it));
auto [x1, y1] = *it;
// [x1,x2]: y2 -> 0
area -= AREA(x2 - x1) * AREA(y2);
if (y1 >= y) break;
}
auto [x1, y1] = *it;
// [x1, x]: 0 -> y
MP[x] = y, area += AREA(x - x1) * AREA(y);
return;
}
void add_fast(XY x, XY y) {
if (x == 0 || y == 0) return;
int rx = ss.next(x);
int ry = ht[rx];
if (ry >= y) return;
// split
if (x < rx) ss.insert(x), ht[x] = ry;
int x2 = x;
while (1) {
XY y2 = ht[x2];
ss.erase(x2);
int x1 = ss.prev(x2);
XY y1 = ht[x1];
// [x1,x2]: y2 -> 0
area -= AREA(x2 - x1) * AREA(y2);
x2 = x1;
if (y1 >= y) break;
}
ss.insert(x), ht[x] = y, area += AREA(x - x2) * AREA(y);
return;
}
};
#line 2 "other/cuboid_union_volume.hpp"
// [0,a] x [0,b] x [0,c] の和集合の体積
// https://codeforces.com/contest/815/problem/D
template <typename XYZ, typename T, bool SMALL_X>
T cuboid_union_volume(vc<tuple<XYZ, XYZ, XYZ>> dat) {
if constexpr (SMALL_X) {
int mx_x = 0, mx_z = 0;
for (auto& [x, y, z]: dat) chmax(mx_x, x), chmax(mx_z, z);
vc<int> ptr(mx_z + 1);
for (auto& [x, y, z]: dat) ptr[z]++;
ptr = cumsum<int>(ptr);
vc<pair<int, int>> rect(len(dat));
for (auto& [x, y, z]: dat) { rect[ptr[z]++] = {x, y}; }
T vol = 0;
Incremental_Rectangle_Union<XYZ, T, true> I(mx_x);
FOR_R(z, 1, mx_z + 1) {
FOR(i, ptr[z - 1], ptr[z]) {
auto [a, b] = rect[i];
I.add(a, b);
}
vol += I.area;
}
return vol;
} else {
sort(all(dat),
[&](auto& a, auto& b) -> bool { return get<2>(a) > get<2>(b); });
XYZ z = infty<XYZ>;
T vol = 0, area = 0;
Incremental_Rectangle_Union<XYZ, T, false> I;
for (auto& [a, b, c]: dat) {
vol += T(z - c) * area, area = I.add(a, b), z = c;
}
vol += z * I.area;
return vol;
}
}