lazy_segtree.hpp¶
维护区间作用、区间聚合以及懒标记下传；题目同时出现区间修改和区间查询时使用。
Complexity: Time: O(n) build and O(log n) point/range operation. Space: O(n).
AC 记录：range_affine_point_get, range_affine_range_sum。
Implementation¶
当前头文件，省略 include guard；依赖见 #include。
/// @complexity Time: O(n) build and O(log n) point/range operation.
/// Space: O(n).
#include <cassert>
#include <vector>
namespace noya {
/// @brief Lazy segment tree for a monoid acted on by a mapping monoid.
/// Monoid provides `value_type`, `unit()`, and `op(l, r)`.
/// Action provides `value_type`, `unit()`, `composition(newer, older)`, and
/// `apply(tag, monoid_value)`.
template <class Monoid, class Action> struct lazy_segtree {
using S = typename Monoid::value_type;
using F = typename Action::value_type;
int n = 0;
int sz = 1;
int log = 0;
std::vector<S> dat;
std::vector<F> lz;
lazy_segtree() : lazy_segtree(0) {}
explicit lazy_segtree(int n_) { build(n_); }
explicit lazy_segtree(const std::vector<S> &a) { build(a); }
void build(int n_) { build(std::vector<S>(n_, Monoid::unit())); }
void build(const std::vector<S> &a) {
n = int(a.size());
sz = 1;
log = 0;
while (sz < n) {
sz <<= 1;
log++;
}
dat.assign(sz << 1, Monoid::unit());
lz.assign(sz, Action::unit());
for (int i = 0; i < n; i++) {
dat[sz + i] = a[i];
}
for (int u = sz - 1; u >= 1; u--) {
pull(u);
}
}
void set(int pos, const S &val) {
assert(0 <= pos && pos < n);
pos += sz;
for (int h = log; h >= 1; h--) {
push(pos >> h);
}
dat[pos] = val;
for (int h = 1; h <= log; h++) {
pull(pos >> h);
}
}
S get(int pos) {
assert(0 <= pos && pos < n);
pos += sz;
for (int h = log; h >= 1; h--) {
push(pos >> h);
}
return dat[pos];
}
S prod(int l, int r) {
assert(0 <= l && l <= r && r <= n);
if (l == r) {
return Monoid::unit();
}
l += sz;
r += sz;
for (int h = log; h >= 1; h--) {
if (((l >> h) << h) != l) {
push(l >> h);
}
if (((r >> h) << h) != r) {
push((r - 1) >> h);
}
}
S arr = Monoid::unit();
S b = Monoid::unit();
while (l < r) {
if (l & 1) {
arr = Monoid::op(arr, dat[l++]);
}
if (r & 1) {
b = Monoid::op(dat[--r], b);
}
l >>= 1;
r >>= 1;
}
return Monoid::op(arr, b);
}
S all_prod() const { return dat[1]; }
/// @brief Apply an action to every element in [l, r).
void apply(int l, int r, const F &tag) {
assert(0 <= l && l <= r && r <= n);
if (l == r) {
return;
}
l += sz;
r += sz;
for (int h = log; h >= 1; h--) {
if (((l >> h) << h) != l) {
push(l >> h);
}
if (((r >> h) << h) != r) {
push((r - 1) >> h);
}
}
int l0 = l;
int r0 = r;
while (l < r) {
if (l & 1) {
all_apply(l++, tag);
}
if (r & 1) {
all_apply(--r, tag);
}
l >>= 1;
r >>= 1;
}
l = l0;
r = r0;
for (int h = 1; h <= log; h++) {
if (((l >> h) << h) != l) {
pull(l >> h);
}
if (((r >> h) << h) != r) {
pull((r - 1) >> h);
}
}
}
private:
void pull(int u) {
dat[u] = Monoid::op(dat[u << 1], dat[u << 1 | 1]);
}
void all_apply(int u, const F &tag) {
dat[u] = Action::apply(tag, dat[u]);
if (u < sz) {
lz[u] = Action::composition(tag, lz[u]);
}
}
void push(int u) {
all_apply(u << 1, lz[u]);
all_apply(u << 1 | 1, lz[u]);
lz[u] = Action::unit();
}
};
} // namespace noya
#ifndef NOYA_LAZY_SEGTREE_HPP
#define NOYA_LAZY_SEGTREE_HPP 1
/// @complexity Time: O(n) build and O(log n) point/range operation.
/// Space: O(n).
#include <cassert>
#include <vector>
namespace noya {
/// @brief Lazy segment tree for a monoid acted on by a mapping monoid.
/// Monoid provides `value_type`, `unit()`, and `op(l, r)`.
/// Action provides `value_type`, `unit()`, `composition(newer, older)`, and
/// `apply(tag, monoid_value)`.
template <class Monoid, class Action> struct lazy_segtree {
using S = typename Monoid::value_type;
using F = typename Action::value_type;
int n = 0;
int sz = 1;
int log = 0;
std::vector<S> dat;
std::vector<F> lz;
lazy_segtree() : lazy_segtree(0) {}
explicit lazy_segtree(int n_) { build(n_); }
explicit lazy_segtree(const std::vector<S> &a) { build(a); }
void build(int n_) { build(std::vector<S>(n_, Monoid::unit())); }
void build(const std::vector<S> &a) {
n = int(a.size());
sz = 1;
log = 0;
while (sz < n) {
sz <<= 1;
log++;
}
dat.assign(sz << 1, Monoid::unit());
lz.assign(sz, Action::unit());
for (int i = 0; i < n; i++) {
dat[sz + i] = a[i];
}
for (int u = sz - 1; u >= 1; u--) {
pull(u);
}
}
void set(int pos, const S &val) {
assert(0 <= pos && pos < n);
pos += sz;
for (int h = log; h >= 1; h--) {
push(pos >> h);
}
dat[pos] = val;
for (int h = 1; h <= log; h++) {
pull(pos >> h);
}
}
S get(int pos) {
assert(0 <= pos && pos < n);
pos += sz;
for (int h = log; h >= 1; h--) {
push(pos >> h);
}
return dat[pos];
}
S prod(int l, int r) {
assert(0 <= l && l <= r && r <= n);
if (l == r) {
return Monoid::unit();
}
l += sz;
r += sz;
for (int h = log; h >= 1; h--) {
if (((l >> h) << h) != l) {
push(l >> h);
}
if (((r >> h) << h) != r) {
push((r - 1) >> h);
}
}
S arr = Monoid::unit();
S b = Monoid::unit();
while (l < r) {
if (l & 1) {
arr = Monoid::op(arr, dat[l++]);
}
if (r & 1) {
b = Monoid::op(dat[--r], b);
}
l >>= 1;
r >>= 1;
}
return Monoid::op(arr, b);
}
S all_prod() const { return dat[1]; }
/// @brief Apply an action to every element in [l, r).
void apply(int l, int r, const F &tag) {
assert(0 <= l && l <= r && r <= n);
if (l == r) {
return;
}
l += sz;
r += sz;
for (int h = log; h >= 1; h--) {
if (((l >> h) << h) != l) {
push(l >> h);
}
if (((r >> h) << h) != r) {
push((r - 1) >> h);
}
}
int l0 = l;
int r0 = r;
while (l < r) {
if (l & 1) {
all_apply(l++, tag);
}
if (r & 1) {
all_apply(--r, tag);
}
l >>= 1;
r >>= 1;
}
l = l0;
r = r0;
for (int h = 1; h <= log; h++) {
if (((l >> h) << h) != l) {
pull(l >> h);
}
if (((r >> h) << h) != r) {
pull((r - 1) >> h);
}
}
}
private:
void pull(int u) {
dat[u] = Monoid::op(dat[u << 1], dat[u << 1 | 1]);
}
void all_apply(int u, const F &tag) {
dat[u] = Action::apply(tag, dat[u]);
if (u < sz) {
lz[u] = Action::composition(tag, lz[u]);
}
}
void push(int u) {
all_apply(u << 1, lz[u]);
all_apply(u << 1 | 1, lz[u]);
lz[u] = Action::unit();
}
};
} // namespace noya
#endif // NOYA_LAZY_SEGTREE_HPP
#include <cassert>
#include <vector>
/// @complexity Time: O(n) build and O(log n) point/range operation.
/// Space: O(n).
namespace noya {
/// @brief Lazy segment tree for a monoid acted on by a mapping monoid.
/// Monoid provides `value_type`, `unit()`, and `op(l, r)`.
/// Action provides `value_type`, `unit()`, `composition(newer, older)`, and
/// `apply(tag, monoid_value)`.
template <class Monoid, class Action> struct lazy_segtree {
using S = typename Monoid::value_type;
using F = typename Action::value_type;
int n = 0;
int sz = 1;
int log = 0;
std::vector<S> dat;
std::vector<F> lz;
lazy_segtree() : lazy_segtree(0) {}
explicit lazy_segtree(int n_) { build(n_); }
explicit lazy_segtree(const std::vector<S> &a) { build(a); }
void build(int n_) { build(std::vector<S>(n_, Monoid::unit())); }
void build(const std::vector<S> &a) {
n = int(a.size());
sz = 1;
log = 0;
while (sz < n) {
sz <<= 1;
log++;
}
dat.assign(sz << 1, Monoid::unit());
lz.assign(sz, Action::unit());
for (int i = 0; i < n; i++) {
dat[sz + i] = a[i];
}
for (int u = sz - 1; u >= 1; u--) {
pull(u);
}
}
void set(int pos, const S &val) {
assert(0 <= pos && pos < n);
pos += sz;
for (int h = log; h >= 1; h--) {
push(pos >> h);
}
dat[pos] = val;
for (int h = 1; h <= log; h++) {
pull(pos >> h);
}
}
S get(int pos) {
assert(0 <= pos && pos < n);
pos += sz;
for (int h = log; h >= 1; h--) {
push(pos >> h);
}
return dat[pos];
}
S prod(int l, int r) {
assert(0 <= l && l <= r && r <= n);
if (l == r) {
return Monoid::unit();
}
l += sz;
r += sz;
for (int h = log; h >= 1; h--) {
if (((l >> h) << h) != l) {
push(l >> h);
}
if (((r >> h) << h) != r) {
push((r - 1) >> h);
}
}
S arr = Monoid::unit();
S b = Monoid::unit();
while (l < r) {
if (l & 1) {
arr = Monoid::op(arr, dat[l++]);
}
if (r & 1) {
b = Monoid::op(dat[--r], b);
}
l >>= 1;
r >>= 1;
}
return Monoid::op(arr, b);
}
S all_prod() const { return dat[1]; }
/// @brief Apply an action to every element in [l, r).
void apply(int l, int r, const F &tag) {
assert(0 <= l && l <= r && r <= n);
if (l == r) {
return;
}
l += sz;
r += sz;
for (int h = log; h >= 1; h--) {
if (((l >> h) << h) != l) {
push(l >> h);
}
if (((r >> h) << h) != r) {
push((r - 1) >> h);
}
}
int l0 = l;
int r0 = r;
while (l < r) {
if (l & 1) {
all_apply(l++, tag);
}
if (r & 1) {
all_apply(--r, tag);
}
l >>= 1;
r >>= 1;
}
l = l0;
r = r0;
for (int h = 1; h <= log; h++) {
if (((l >> h) << h) != l) {
pull(l >> h);
}
if (((r >> h) << h) != r) {
pull((r - 1) >> h);
}
}
}
private:
void pull(int u) {
dat[u] = Monoid::op(dat[u << 1], dat[u << 1 | 1]);
}
void all_apply(int u, const F &tag) {
dat[u] = Action::apply(tag, dat[u]);
if (u < sz) {
lz[u] = Action::composition(tag, lz[u]);
}
}
void push(int u) {
all_apply(u << 1, lz[u]);
all_apply(u << 1 | 1, lz[u]);
lz[u] = Action::unit();
}
};
} // namespace noya