library
This documentation is automatically generated by online-judge-tools/verification-helper
ds/kdtree/kdtree_acted_monoid.hpp
- View this file on GitHub
- Last update: 2023-02-01 23:31:55+09:00
- Include:
#include "ds/kdtree/kdtree_acted_monoid.hpp" - Link: View error logs on GitHub Actions
Verified with
test/mytest/kdtree_am.test.cpp
test/yukicoder/2342.test.cpp
Code
template <class ActedMonoid, typename XY>
struct KDTree_ActedMonoid {
using AM = ActedMonoid;
using MX = typename AM::Monoid_X;
using MA = typename AM::Monoid_A;
using X = typename AM::X;
using A = typename AM::A;
static_assert(MX::commute);
// 小数も考慮すると、閉で持つ設計方針になる。ただし、クエリはいつもの半開を使う
vc<tuple<XY, XY, XY, XY>> closed_range;
vc<X> dat;
vc<A> lazy;
vc<int> size;
int n;
KDTree_ActedMonoid(vc<XY> xs, vc<XY> ys, vc<X> vs) : n(len(xs)) {
assert(n > 0);
int log = 0;
while ((1 << log) < n) ++log;
dat.resize(1 << (log + 1));
lazy.assign(1 << log, MA::unit());
closed_range.resize(1 << (log + 1));
size.resize(1 << (log + 1));
build(1, xs, ys, vs);
}
void multiply(XY x, XY y, const X& v) { multiply_rec(1, x, y, v); }
// [xl, xr) x [yl, yr)
X prod(XY xl, XY xr, XY yl, XY yr) {
assert(xl <= xr && yl <= yr);
return prod_rec(1, xl, xr, yl, yr);
}
X prod_all() { return dat[1]; }
// [xl, xr) x [yl, yr)
void apply(XY xl, XY xr, XY yl, XY yr, A a) {
assert(xl <= xr && yl <= yr);
return apply_rec(1, xl, xr, yl, yr, a);
}
private:
void build(int idx, vc<XY> xs, vc<XY> ys, vc<X> vs, bool divx = true) {
int n = len(xs);
size[idx] = n;
auto& [xmin, xmax, ymin, ymax] = closed_range[idx];
xmin = ymin = infty<XY>;
xmax = ymax = -infty<XY>;
FOR(i, n) {
auto x = xs[i], y = ys[i];
chmin(xmin, x), chmax(xmax, x), chmin(ymin, y), chmax(ymax, y);
}
if (xmin == xmax && ymin == ymax) {
X x = MX::unit();
for (auto&& v: vs) x = MX::op(x, v);
dat[idx] = x;
return;
}
int m = n / 2;
vc<int> I(n);
iota(all(I), 0);
if (divx) {
nth_element(I.begin(), I.begin() + m, I.end(),
[xs](int i, int j) { return xs[i] < xs[j]; });
} else {
nth_element(I.begin(), I.begin() + m, I.end(),
[ys](int i, int j) { return ys[i] < ys[j]; });
}
xs = rearrange(xs, I), ys = rearrange(ys, I), vs = rearrange(vs, I);
build(2 * idx + 0, {xs.begin(), xs.begin() + m},
{ys.begin(), ys.begin() + m}, {vs.begin(), vs.begin() + m}, !divx);
build(2 * idx + 1, {xs.begin() + m, xs.end()}, {ys.begin() + m, ys.end()},
{vs.begin() + m, vs.end()}, !divx);
dat[idx] = MX::op(dat[2 * idx + 0], dat[2 * idx + 1]);
}
inline bool is_leaf(int idx) {
auto& [xmin, xmax, ymin, ymax] = closed_range[idx];
return xmin == xmax && ymin == ymax;
}
inline bool isin(XY x, XY y, int idx) {
auto& [xmin, xmax, ymin, ymax] = closed_range[idx];
return (xmin <= x && x <= xmax && ymin <= y && y <= ymax);
}
void apply_at(int idx, A a) {
dat[idx] = AM::act(dat[idx], a, size[idx]);
if (!is_leaf(idx)) lazy[idx] = MA::op(lazy[idx], a);
}
void push(int idx) {
if (lazy[idx] == MA::unit()) return;
apply_at(2 * idx + 0, lazy[idx]), apply_at(2 * idx + 1, lazy[idx]);
lazy[idx] = MA::unit();
}
bool multiply_rec(int idx, XY x, XY y, X v) {
if (!isin(x, y, idx)) return false;
if (is_leaf(idx)) {
dat[idx] = MX::op(dat[idx], v);
size[idx] += 1;
return true;
}
push(idx);
bool done = 0;
if (multiply_rec(2 * idx + 0, x, y, v)) done = 1;
if (!done && multiply_rec(2 * idx + 1, x, y, v)) done = 1;
if (done) {
dat[idx] = MX::op(dat[2 * idx + 0], dat[2 * idx + 1]);
size[idx] = size[2 * idx + 0] + size[2 * idx + 1];
}
return done;
}
X prod_rec(int idx, XY x1, XY x2, XY y1, XY y2) {
auto& [xmin, xmax, ymin, ymax] = closed_range[idx];
if (x2 <= xmin || xmax < x1) return MX::unit();
if (y2 <= ymin || ymax < y1) return MX::unit();
if (x1 <= xmin && xmax < x2 && y1 <= ymin && ymax < y2) { return dat[idx]; }
push(idx);
return MX::op(prod_rec(2 * idx + 0, x1, x2, y1, y2),
prod_rec(2 * idx + 1, x1, x2, y1, y2));
}
void apply_rec(int idx, XY x1, XY x2, XY y1, XY y2, A a) {
auto& [xmin, xmax, ymin, ymax] = closed_range[idx];
if (x2 <= xmin || xmax < x1) return;
if (y2 <= ymin || ymax < y1) return;
if (x1 <= xmin && xmax < x2 && y1 <= ymin && ymax < y2) {
return apply_at(idx, a);
}
push(idx);
apply_rec(2 * idx + 0, x1, x2, y1, y2, a);
apply_rec(2 * idx + 1, x1, x2, y1, y2, a);
dat[idx] = MX::op(dat[2 * idx + 0], dat[2 * idx + 1]);
}
};#line 1 "ds/kdtree/kdtree_acted_monoid.hpp"
template <class ActedMonoid, typename XY>
struct KDTree_ActedMonoid {
using AM = ActedMonoid;
using MX = typename AM::Monoid_X;
using MA = typename AM::Monoid_A;
using X = typename AM::X;
using A = typename AM::A;
static_assert(MX::commute);
// 小数も考慮すると、閉で持つ設計方針になる。ただし、クエリはいつもの半開を使う
vc<tuple<XY, XY, XY, XY>> closed_range;
vc<X> dat;
vc<A> lazy;
vc<int> size;
int n;
KDTree_ActedMonoid(vc<XY> xs, vc<XY> ys, vc<X> vs) : n(len(xs)) {
assert(n > 0);
int log = 0;
while ((1 << log) < n) ++log;
dat.resize(1 << (log + 1));
lazy.assign(1 << log, MA::unit());
closed_range.resize(1 << (log + 1));
size.resize(1 << (log + 1));
build(1, xs, ys, vs);
}
void multiply(XY x, XY y, const X& v) { multiply_rec(1, x, y, v); }
// [xl, xr) x [yl, yr)
X prod(XY xl, XY xr, XY yl, XY yr) {
assert(xl <= xr && yl <= yr);
return prod_rec(1, xl, xr, yl, yr);
}
X prod_all() { return dat[1]; }
// [xl, xr) x [yl, yr)
void apply(XY xl, XY xr, XY yl, XY yr, A a) {
assert(xl <= xr && yl <= yr);
return apply_rec(1, xl, xr, yl, yr, a);
}
private:
void build(int idx, vc<XY> xs, vc<XY> ys, vc<X> vs, bool divx = true) {
int n = len(xs);
size[idx] = n;
auto& [xmin, xmax, ymin, ymax] = closed_range[idx];
xmin = ymin = infty<XY>;
xmax = ymax = -infty<XY>;
FOR(i, n) {
auto x = xs[i], y = ys[i];
chmin(xmin, x), chmax(xmax, x), chmin(ymin, y), chmax(ymax, y);
}
if (xmin == xmax && ymin == ymax) {
X x = MX::unit();
for (auto&& v: vs) x = MX::op(x, v);
dat[idx] = x;
return;
}
int m = n / 2;
vc<int> I(n);
iota(all(I), 0);
if (divx) {
nth_element(I.begin(), I.begin() + m, I.end(),
[xs](int i, int j) { return xs[i] < xs[j]; });
} else {
nth_element(I.begin(), I.begin() + m, I.end(),
[ys](int i, int j) { return ys[i] < ys[j]; });
}
xs = rearrange(xs, I), ys = rearrange(ys, I), vs = rearrange(vs, I);
build(2 * idx + 0, {xs.begin(), xs.begin() + m},
{ys.begin(), ys.begin() + m}, {vs.begin(), vs.begin() + m}, !divx);
build(2 * idx + 1, {xs.begin() + m, xs.end()}, {ys.begin() + m, ys.end()},
{vs.begin() + m, vs.end()}, !divx);
dat[idx] = MX::op(dat[2 * idx + 0], dat[2 * idx + 1]);
}
inline bool is_leaf(int idx) {
auto& [xmin, xmax, ymin, ymax] = closed_range[idx];
return xmin == xmax && ymin == ymax;
}
inline bool isin(XY x, XY y, int idx) {
auto& [xmin, xmax, ymin, ymax] = closed_range[idx];
return (xmin <= x && x <= xmax && ymin <= y && y <= ymax);
}
void apply_at(int idx, A a) {
dat[idx] = AM::act(dat[idx], a, size[idx]);
if (!is_leaf(idx)) lazy[idx] = MA::op(lazy[idx], a);
}
void push(int idx) {
if (lazy[idx] == MA::unit()) return;
apply_at(2 * idx + 0, lazy[idx]), apply_at(2 * idx + 1, lazy[idx]);
lazy[idx] = MA::unit();
}
bool multiply_rec(int idx, XY x, XY y, X v) {
if (!isin(x, y, idx)) return false;
if (is_leaf(idx)) {
dat[idx] = MX::op(dat[idx], v);
size[idx] += 1;
return true;
}
push(idx);
bool done = 0;
if (multiply_rec(2 * idx + 0, x, y, v)) done = 1;
if (!done && multiply_rec(2 * idx + 1, x, y, v)) done = 1;
if (done) {
dat[idx] = MX::op(dat[2 * idx + 0], dat[2 * idx + 1]);
size[idx] = size[2 * idx + 0] + size[2 * idx + 1];
}
return done;
}
X prod_rec(int idx, XY x1, XY x2, XY y1, XY y2) {
auto& [xmin, xmax, ymin, ymax] = closed_range[idx];
if (x2 <= xmin || xmax < x1) return MX::unit();
if (y2 <= ymin || ymax < y1) return MX::unit();
if (x1 <= xmin && xmax < x2 && y1 <= ymin && ymax < y2) { return dat[idx]; }
push(idx);
return MX::op(prod_rec(2 * idx + 0, x1, x2, y1, y2),
prod_rec(2 * idx + 1, x1, x2, y1, y2));
}
void apply_rec(int idx, XY x1, XY x2, XY y1, XY y2, A a) {
auto& [xmin, xmax, ymin, ymax] = closed_range[idx];
if (x2 <= xmin || xmax < x1) return;
if (y2 <= ymin || ymax < y1) return;
if (x1 <= xmin && xmax < x2 && y1 <= ymin && ymax < y2) {
return apply_at(idx, a);
}
push(idx);
apply_rec(2 * idx + 0, x1, x2, y1, y2, a);
apply_rec(2 * idx + 1, x1, x2, y1, y2, a);
dat[idx] = MX::op(dat[2 * idx + 0], dat[2 * idx + 1]);
}
};