This documentation is automatically generated by online-judge-tools/verification-helper
#include "datastructure/dual_segtree.hpp"
dual_segtree<F, composition, id>(n, is_commutative = false)
: 長さ n
の数列 a
を作る。F
は作用の型。composition
は $f \circ g$ を計算する関数。id
は $id$ を返す関数。$\cdot$ が可換である場合は commutative = true
にするとよい。apply(l, r, x)
: a_l, ..., a_r
に x
を作用させる。get(p)
: a_p
を求める。#include <vector>
template <class F, F (*composition)(F, F), F (*id)()>
struct dual_segtree {
public:
dual_segtree() {
}
dual_segtree(int n, bool is_commutative = false)
: is_commutative(is_commutative) {
size = 1;
height = 0;
while (size < n) size <<= 1, height++;
lz.assign(2 * size, id());
}
void apply(int l, int r, const F &f) {
l += size;
r += size - 1;
if (!is_commutative) thrust(l);
if (!is_commutative) thrust(r);
r++;
while (l < r) {
if (l & 1) lz[l] = composition(f, lz[l]), ++l;
if (r & 1) --r, lz[r] = composition(f, lz[r]);
l >>= 1, r >>= 1;
}
}
F get(int p) {
if (is_commutative) {
F ret = id();
p += size;
while (p > 0) {
ret = composition(lz[p], ret);
p >>= 1;
}
return ret;
} else {
thrust(p += size);
return lz[p];
}
}
private:
int size, height;
std::vector<F> lz;
bool is_commutative;
inline void propagate(int k) {
lz[2 * k + 0] = composition(lz[k], lz[2 * k + 0]);
lz[2 * k + 1] = composition(lz[k], lz[2 * k + 1]);
lz[k] = id();
}
inline void thrust(int k) {
for (int i = height; i > 0; i--) propagate(k >> i);
}
};
#line 1 "datastructure/dual_segtree.hpp"
#include <vector>
template <class F, F (*composition)(F, F), F (*id)()>
struct dual_segtree {
public:
dual_segtree() {
}
dual_segtree(int n, bool is_commutative = false)
: is_commutative(is_commutative) {
size = 1;
height = 0;
while (size < n) size <<= 1, height++;
lz.assign(2 * size, id());
}
void apply(int l, int r, const F &f) {
l += size;
r += size - 1;
if (!is_commutative) thrust(l);
if (!is_commutative) thrust(r);
r++;
while (l < r) {
if (l & 1) lz[l] = composition(f, lz[l]), ++l;
if (r & 1) --r, lz[r] = composition(f, lz[r]);
l >>= 1, r >>= 1;
}
}
F get(int p) {
if (is_commutative) {
F ret = id();
p += size;
while (p > 0) {
ret = composition(lz[p], ret);
p >>= 1;
}
return ret;
} else {
thrust(p += size);
return lz[p];
}
}
private:
int size, height;
std::vector<F> lz;
bool is_commutative;
inline void propagate(int k) {
lz[2 * k + 0] = composition(lz[k], lz[2 * k + 0]);
lz[2 * k + 1] = composition(lz[k], lz[2 * k + 1]);
lz[k] = id();
}
inline void thrust(int k) {
for (int i = height; i > 0; i--) propagate(k >> i);
}
};