This documentation is automatically generated by online-judge-tools/verification-helper
#include "segment_tree/lazy_segment_tree.hpp"
#ifndef LAZY_SEGMENT_TREE_HPP
#define LAZY_SEGMENT_TREE_HPP
#include <cstdint>
#include <vector>
#include "../bit/ctz.hpp"
#include "../bit/msb.hpp"
//===
template <class MonoidwithOperator>
struct LazySegmentTree {
using M = MonoidwithOperator;
using V = typename M::value_structure;
using T = typename V::value_type;
using O = typename M::operator_structure;
using E = typename O::value_type;
// T + T V::operation
// E + E O::operation
// T + E -> T M::operation
struct Node {
T dat;
E lazy;
Node(T dat, E lazy) : dat(dat), lazy(lazy){};
};
std::vector<Node> tree;
LazySegmentTree() = default;
explicit LazySegmentTree(uint32_t n)
: tree(n * 2 + 2, Node(V::identity(), O::identity())){};
int size() {
return tree.size() >> 1;
};
void propagation(uint32_t k) {
const uint32_t l = (k << 1) | 0;
const uint32_t r = (k << 1) | 1;
tree[l].lazy = O::operation(tree[l].lazy, tree[k].lazy);
tree[r].lazy = O::operation(tree[r].lazy, tree[k].lazy);
tree[l].dat = M::operation(tree[l].dat, tree[k].lazy);
tree[r].dat = M::operation(tree[r].dat, tree[k].lazy);
tree[k].lazy = O::identity();
};
void push_down(uint32_t k) {
if (k == 0) return;
uint32_t w = ctz32(msb32(k));
for (int i = w; i > 0; i--) propagation(k >> i);
};
void recalc(uint32_t k) {
while (k > 1) {
k >>= 1;
tree[k].dat =
V::operation(tree[(k << 1) | 0].dat, tree[(k << 1) | 1].dat);
}
};
// [l, r) += op
void update(uint32_t l, uint32_t r, E op) {
l += size();
r += size();
uint32_t tmpl = l;
uint32_t tmpr = r;
push_down(l);
push_down(r - 1);
while (l < r) {
if (l & 1) {
tree[l].lazy = O::operation(tree[l].lazy, op);
tree[l].dat = M::operation(tree[l].dat, op);
l++;
}
if (r & 1) {
--r;
tree[r].lazy = O::operation(tree[r].lazy, op);
tree[r].dat = M::operation(tree[r].dat, op);
}
l >>= 1;
r >>= 1;
}
push_down(tmpl);
push_down(tmpr - 1);
recalc(tmpl);
recalc(tmpr - 1);
};
void update(uint32_t idx, T x) {
idx += size();
push_down(idx);
tree[idx].dat = x;
recalc(idx);
};
void set(uint32_t idx, T x) {
update(idx, x);
};
// foldl[l, r)
T fold(uint32_t l, uint32_t r) {
l += size();
r += size();
push_down(l);
push_down(r - 1);
T lv = V::identity();
T rv = V::identity();
while (l < r) {
if (l & 1) lv = V::operation(lv, tree[l].dat), l++;
if (r & 1) --r, rv = V::operation(tree[r].dat, rv);
l >>= 1;
r >>= 1;
}
return V::operation(lv, rv);
};
T operator[](const uint32_t &k) {
push_down(k + size());
return tree[k + size()].dat;
};
};
//===
#endif
#line 1 "segment_tree/lazy_segment_tree.hpp"
#include <cstdint>
#include <vector>
#line 1 "bit/ctz.hpp"
#line 5 "bit/ctz.hpp"
inline int ctz32_(uint32_t bit) {
static const int table[] = {
0, 1, 2, 6, 3, 11, 7, 16, 4, 14, 12, 21, 8, 23, 17, 26,
31, 5, 10, 15, 13, 20, 22, 25, 30, 9, 19, 24, 29, 18, 28, 27,
};
static const uint32_t de_bruijn = 0x04653adf;
bit &= ~bit + 1;
return table[(bit * de_bruijn) >> 27];
};
inline int ctz32(uint32_t bit) {
if (bit == 0) return 32;
#ifdef __has_builtin
return __builtin_ctz(bit);
#else
return ctz32_(bit);
#endif
};
inline int ctz64_(uint64_t bit) {
static const int table[] = {
0, 1, 2, 7, 3, 13, 8, 19, 4, 25, 14, 28, 9, 34, 20, 40,
5, 17, 26, 38, 15, 46, 29, 48, 10, 31, 35, 54, 21, 50, 41, 57,
63, 6, 12, 18, 24, 27, 33, 39, 16, 37, 45, 47, 30, 53, 49, 56,
62, 11, 23, 32, 36, 44, 52, 55, 61, 22, 43, 51, 60, 42, 59, 58,
};
static const uint64_t de_bruijn = 0x0218a392cd3d5dbfull;
bit &= ~bit + 1;
return table[(bit * de_bruijn) >> 58];
};
inline int ctz64(uint64_t bit) {
if (bit == 0) return 64;
#ifdef __has_builtin
return __builtin_ctzll(bit);
#else
return ctz64_(bit);
#endif
};
#line 1 "bit/msb.hpp"
#line 5 "bit/msb.hpp"
inline uint32_t msb32_(uint32_t bit) {
bit |= bit >> 1;
bit |= bit >> 2;
bit |= bit >> 4;
bit |= bit >> 8;
bit |= bit >> 16;
return bit ^ (bit >> 1);
};
inline uint32_t msb32(uint32_t x) {
if (x == 0) return 0;
#ifdef __has_builtin
return 1u << (31 - __builtin_clz(x));
#else
return msb32_(x);
#endif
};
inline uint64_t msb64_(uint64_t bit) {
bit |= bit >> 1;
bit |= bit >> 2;
bit |= bit >> 4;
bit |= bit >> 8;
bit |= bit >> 16;
bit |= bit >> 32;
return bit ^ (bit >> 1);
};
inline uint64_t msb64(uint64_t x) {
if (x == 0) return 0;
#ifdef __has_builtin
return 1ull << (63 - __builtin_clzll(x));
#else
return msb64_(x);
#endif
};
#line 9 "segment_tree/lazy_segment_tree.hpp"
//===
template <class MonoidwithOperator>
struct LazySegmentTree {
using M = MonoidwithOperator;
using V = typename M::value_structure;
using T = typename V::value_type;
using O = typename M::operator_structure;
using E = typename O::value_type;
// T + T V::operation
// E + E O::operation
// T + E -> T M::operation
struct Node {
T dat;
E lazy;
Node(T dat, E lazy) : dat(dat), lazy(lazy){};
};
std::vector<Node> tree;
LazySegmentTree() = default;
explicit LazySegmentTree(uint32_t n)
: tree(n * 2 + 2, Node(V::identity(), O::identity())){};
int size() {
return tree.size() >> 1;
};
void propagation(uint32_t k) {
const uint32_t l = (k << 1) | 0;
const uint32_t r = (k << 1) | 1;
tree[l].lazy = O::operation(tree[l].lazy, tree[k].lazy);
tree[r].lazy = O::operation(tree[r].lazy, tree[k].lazy);
tree[l].dat = M::operation(tree[l].dat, tree[k].lazy);
tree[r].dat = M::operation(tree[r].dat, tree[k].lazy);
tree[k].lazy = O::identity();
};
void push_down(uint32_t k) {
if (k == 0) return;
uint32_t w = ctz32(msb32(k));
for (int i = w; i > 0; i--) propagation(k >> i);
};
void recalc(uint32_t k) {
while (k > 1) {
k >>= 1;
tree[k].dat =
V::operation(tree[(k << 1) | 0].dat, tree[(k << 1) | 1].dat);
}
};
// [l, r) += op
void update(uint32_t l, uint32_t r, E op) {
l += size();
r += size();
uint32_t tmpl = l;
uint32_t tmpr = r;
push_down(l);
push_down(r - 1);
while (l < r) {
if (l & 1) {
tree[l].lazy = O::operation(tree[l].lazy, op);
tree[l].dat = M::operation(tree[l].dat, op);
l++;
}
if (r & 1) {
--r;
tree[r].lazy = O::operation(tree[r].lazy, op);
tree[r].dat = M::operation(tree[r].dat, op);
}
l >>= 1;
r >>= 1;
}
push_down(tmpl);
push_down(tmpr - 1);
recalc(tmpl);
recalc(tmpr - 1);
};
void update(uint32_t idx, T x) {
idx += size();
push_down(idx);
tree[idx].dat = x;
recalc(idx);
};
void set(uint32_t idx, T x) {
update(idx, x);
};
// foldl[l, r)
T fold(uint32_t l, uint32_t r) {
l += size();
r += size();
push_down(l);
push_down(r - 1);
T lv = V::identity();
T rv = V::identity();
while (l < r) {
if (l & 1) lv = V::operation(lv, tree[l].dat), l++;
if (r & 1) --r, rv = V::operation(tree[r].dat, rv);
l >>= 1;
r >>= 1;
}
return V::operation(lv, rv);
};
T operator[](const uint32_t &k) {
push_down(k + size());
return tree[k + size()].dat;
};
};
//===