Luzhiled's Library
This documentation is automatically generated by online-judge-tools/verification-helper
structure/segment-tree/segment-tree-beats.hpp
- View this file on GitHub
- Last update: 2024-04-24 02:34:04+09:00
- Include:
#include "structure/segment-tree/segment-tree-beats.hpp"
Code
template< typename Monoid, typename OperatorMonoid = Monoid >
struct SegmentTreeBeats {
using F = function< Monoid(Monoid, Monoid) >;
using G = function< Monoid(Monoid, OperatorMonoid) >;
using H = function< OperatorMonoid(OperatorMonoid, OperatorMonoid) >;
int sz, height;
vector< Monoid > data;
vector< OperatorMonoid > lazy;
const F f;
const G g;
const H h;
const Monoid M1;
const OperatorMonoid OM0;
SegmentTreeBeats(int n, const F f, const G g, const H h,
const Monoid &M1, const OperatorMonoid OM0)
: f(f), g(g), h(h), M1(M1), OM0(OM0) {
sz = 1;
height = 0;
while(sz < n) sz <<= 1, height++;
data.assign(2 * sz, M1);
lazy.assign(2 * sz, OM0);
}
void set(int k, const Monoid &x) {
data[k + sz] = x;
}
void build() {
for(int k = sz - 1; k > 0; k--) {
data[k] = f(data[2 * k + 0], data[2 * k + 1]);
}
}
inline void propagate(int k) {
if(lazy[k] != OM0) {
lazy[2 * k + 0] = h(lazy[2 * k + 0], lazy[k]);
lazy[2 * k + 1] = h(lazy[2 * k + 1], lazy[k]);
data[k] = reflect(k);
lazy[k] = OM0;
}
}
inline Monoid reflect(int k) {
return lazy[k] == OM0 ? data[k] : g(data[k], lazy[k]);
}
inline void recalc(int k) {
while(k >>= 1) data[k] = f(reflect(2 * k + 0), reflect(2 * k + 1));
}
inline void thrust(int k) {
for(int i = height; i > 0; i--) propagate(k >> i);
}
void update(int a, int b, const OperatorMonoid &x) {
thrust(a += sz);
thrust(b += sz - 1);
for(int l = a, r = b + 1; l < r; l >>= 1, r >>= 1) {
if(l & 1) lazy[l] = h(lazy[l], x), ++l;
if(r & 1) --r, lazy[r] = h(lazy[r], x);
}
recalc(a);
recalc(b);
}
Monoid query(int a, int b) {
thrust(a += sz);
thrust(b += sz - 1);
Monoid L = M1, R = M1;
for(int l = a, r = b + 1; l < r; l >>= 1, r >>= 1) {
if(l & 1) L = f(L, reflect(l++));
if(r & 1) R = f(reflect(--r), R);
}
return f(L, R);
}
Monoid operator[](const int &k) {
return query(k, k + 1);
}
template< typename Uku, typename Check, typename Func, typename X >
void update_beats_subtree(int k, const X &x, const Uku &uku, const Check &check, const Func &func) {
if(k >= sz) {
auto v = reflect(k);
if(uku(v, x)) return;
if(check(v)) lazy[k] = func(v, x);
return;
}
propagate(k);
if(uku(data[k], x)) return;
if(check(data[k])) {
lazy[k] = func(data[k], x);
return;
}
update_beats_subtree(k * 2 + 0, x, uku, check, func);
update_beats_subtree(k * 2 + 1, x, uku, check, func);
data[k] = f(reflect(2 * k + 0), reflect(2 * k + 1));
}
template< typename Uku, typename Check, typename Func, typename X >
void update_beats(int a, int b, const X &x, const Uku &uku, const Check &check, const Func &func) {
thrust(a += sz);
thrust(b += sz - 1);
for(int l = a, r = b + 1; l < r; l >>= 1, r >>= 1) {
if(l & 1) update_beats_subtree(l++, x, uku, check, func);
if(r & 1) update_beats_subtree(--r, x, uku, check, func);
}
recalc(a);
recalc(b);
}
};
#line 1 "structure/segment-tree/segment-tree-beats.hpp"
template< typename Monoid, typename OperatorMonoid = Monoid >
struct SegmentTreeBeats {
using F = function< Monoid(Monoid, Monoid) >;
using G = function< Monoid(Monoid, OperatorMonoid) >;
using H = function< OperatorMonoid(OperatorMonoid, OperatorMonoid) >;
int sz, height;
vector< Monoid > data;
vector< OperatorMonoid > lazy;
const F f;
const G g;
const H h;
const Monoid M1;
const OperatorMonoid OM0;
SegmentTreeBeats(int n, const F f, const G g, const H h,
const Monoid &M1, const OperatorMonoid OM0)
: f(f), g(g), h(h), M1(M1), OM0(OM0) {
sz = 1;
height = 0;
while(sz < n) sz <<= 1, height++;
data.assign(2 * sz, M1);
lazy.assign(2 * sz, OM0);
}
void set(int k, const Monoid &x) {
data[k + sz] = x;
}
void build() {
for(int k = sz - 1; k > 0; k--) {
data[k] = f(data[2 * k + 0], data[2 * k + 1]);
}
}
inline void propagate(int k) {
if(lazy[k] != OM0) {
lazy[2 * k + 0] = h(lazy[2 * k + 0], lazy[k]);
lazy[2 * k + 1] = h(lazy[2 * k + 1], lazy[k]);
data[k] = reflect(k);
lazy[k] = OM0;
}
}
inline Monoid reflect(int k) {
return lazy[k] == OM0 ? data[k] : g(data[k], lazy[k]);
}
inline void recalc(int k) {
while(k >>= 1) data[k] = f(reflect(2 * k + 0), reflect(2 * k + 1));
}
inline void thrust(int k) {
for(int i = height; i > 0; i--) propagate(k >> i);
}
void update(int a, int b, const OperatorMonoid &x) {
thrust(a += sz);
thrust(b += sz - 1);
for(int l = a, r = b + 1; l < r; l >>= 1, r >>= 1) {
if(l & 1) lazy[l] = h(lazy[l], x), ++l;
if(r & 1) --r, lazy[r] = h(lazy[r], x);
}
recalc(a);
recalc(b);
}
Monoid query(int a, int b) {
thrust(a += sz);
thrust(b += sz - 1);
Monoid L = M1, R = M1;
for(int l = a, r = b + 1; l < r; l >>= 1, r >>= 1) {
if(l & 1) L = f(L, reflect(l++));
if(r & 1) R = f(reflect(--r), R);
}
return f(L, R);
}
Monoid operator[](const int &k) {
return query(k, k + 1);
}
template< typename Uku, typename Check, typename Func, typename X >
void update_beats_subtree(int k, const X &x, const Uku &uku, const Check &check, const Func &func) {
if(k >= sz) {
auto v = reflect(k);
if(uku(v, x)) return;
if(check(v)) lazy[k] = func(v, x);
return;
}
propagate(k);
if(uku(data[k], x)) return;
if(check(data[k])) {
lazy[k] = func(data[k], x);
return;
}
update_beats_subtree(k * 2 + 0, x, uku, check, func);
update_beats_subtree(k * 2 + 1, x, uku, check, func);
data[k] = f(reflect(2 * k + 0), reflect(2 * k + 1));
}
template< typename Uku, typename Check, typename Func, typename X >
void update_beats(int a, int b, const X &x, const Uku &uku, const Check &check, const Func &func) {
thrust(a += sz);
thrust(b += sz - 1);
for(int l = a, r = b + 1; l < r; l >>= 1, r >>= 1) {
if(l & 1) update_beats_subtree(l++, x, uku, check, func);
if(r & 1) update_beats_subtree(--r, x, uku, check, func);
}
recalc(a);
recalc(b);
}
};