algorithm-dev
This documentation is automatically generated by online-judge-tools/verification-helper
verify/aoj-DSL_2_G-lazy_segment_tree.test.cpp
- View this file on GitHub
- Last update: 2025-07-03 00:41:25+09:00
- Problem: https://onlinejudge.u-aizu.ac.jp/courses/library/3/DSL/2/DSL_2_G
Depends on
algorithm/DataStructure/SegmentTree/lazy_segment_tree.hpp
Code
#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/courses/library/3/DSL/2/DSL_2_G"
#include <iostream>
#include "../algorithm/DataStructure/SegmentTree/lazy_segment_tree.hpp"
int main() {
int n;
int q;
std::cin >> n >> q;
algorithm::lazy_segment_tree::range_sum_range_add_lazy_segment_tree<long long> segtree(n, {0, 1});
while(q--) {
int type;
std::cin >> type;
if(type == 0) {
int s, t;
long long x;
std::cin >> s >> t >> x;
--s;
segtree.apply(s, t, x);
} else {
int s, t;
std::cin >> s >> t;
--s;
auto &&ans = segtree.prod(s, t).val;
std::cout << ans << "\n";
}
}
}#line 1 "verify/aoj-DSL_2_G-lazy_segment_tree.test.cpp"
#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/courses/library/3/DSL/2/DSL_2_G"
#include <iostream>
#line 1 "algorithm/DataStructure/SegmentTree/lazy_segment_tree.hpp"
#include <algorithm>
#include <cassert>
#include <initializer_list>
#line 8 "algorithm/DataStructure/SegmentTree/lazy_segment_tree.hpp"
#include <iterator>
#include <type_traits>
#include <vector>
#line 1 "algorithm/Math/Algebra/algebra.hpp"
#line 6 "algorithm/Math/Algebra/algebra.hpp"
#include <limits>
#include <numeric>
#line 9 "algorithm/Math/Algebra/algebra.hpp"
#include <utility>
namespace algorithm {
namespace algebra {
template <typename S>
class Set {
public:
using value_type = S;
protected:
value_type val;
public:
constexpr Set() : val() {}
constexpr Set(const value_type &val) : val(val) {}
constexpr Set(value_type &&val) : val(std::move(val)) {}
friend constexpr bool operator==(const Set &lhs, const Set &rhs) { return lhs.val == rhs.val; }
friend std::istream &operator>>(std::istream &is, Set &rhs) { return is >> rhs.val; }
friend std::ostream &operator<<(std::ostream &os, const Set &rhs) { return os << rhs.val; }
constexpr value_type value() const { return val; }
};
template <typename S, auto op>
class Semigroup : public Set<S> {
static_assert(std::is_invocable_r<S, decltype(op), S, S>::value);
using base_type = Set<S>;
public:
using value_type = typename base_type::value_type;
constexpr Semigroup() : base_type() {}
constexpr Semigroup(const value_type &val) : base_type(val) {}
constexpr Semigroup(value_type &&val) : base_type(std::move(val)) {}
friend constexpr Semigroup operator*(const Semigroup &lhs, const Semigroup &rhs) { return Semigroup(op(lhs.val, rhs.val)); }
static constexpr auto get_op() { return op; }
};
template <typename S, auto op, auto e>
class Monoid : public Semigroup<S, op> {
static_assert(std::is_invocable_r<S, decltype(e)>::value);
using base_type = Semigroup<S, op>;
public:
using value_type = typename base_type::value_type;
constexpr Monoid() : base_type() {}
constexpr Monoid(const value_type &val) : base_type(val) {}
constexpr Monoid(value_type &&val) : base_type(std::move(val)) {}
friend constexpr Monoid operator*(const Monoid &lhs, const Monoid &rhs) { return Monoid(op(lhs.val, rhs.val)); }
static constexpr auto get_e() { return e; }
static constexpr Monoid one() { return Monoid(e()); } // return identity element.
};
template <typename S, auto op, auto e, auto inverse>
class Group : public Monoid<S, op, e> {
static_assert(std::is_invocable_r<S, decltype(inverse), S>::value);
using base_type = Monoid<S, op, e>;
public:
using value_type = typename base_type::value_type;
constexpr Group() : base_type() {}
constexpr Group(const value_type &val) : base_type(val) {}
constexpr Group(value_type &&val) : base_type(std::move(val)) {}
friend constexpr Group operator*(const Group &lhs, const Group &rhs) { return Group(op(lhs.val, rhs.val)); }
static constexpr auto get_inverse() { return inverse; }
static constexpr Group one() { return Group(e()); } // return identity element.
constexpr Group inv() const { return Group(inverse(this->val)); } // return inverse element.
};
template <typename F, auto compose, auto id, typename X, auto mapping>
class OperatorMonoid : public Monoid<F, compose, id> {
static_assert(std::is_invocable_r<X, decltype(mapping), F, X>::value);
using base_type = Monoid<F, compose, id>;
public:
using value_type = typename base_type::value_type;
using acted_value_type = X;
constexpr OperatorMonoid() : base_type() {}
constexpr OperatorMonoid(const value_type &val) : base_type(val) {}
constexpr OperatorMonoid(value_type &&val) : base_type(std::move(val)) {}
friend constexpr OperatorMonoid operator*(const OperatorMonoid &lhs, const OperatorMonoid &rhs) { return OperatorMonoid(compose(lhs.val, rhs.val)); }
static constexpr auto get_mapping() { return mapping; }
static constexpr OperatorMonoid one() { return OperatorMonoid(id()); } // return identity mapping.
constexpr acted_value_type act(const acted_value_type &x) const { return mapping(this->val, x); }
template <class S>
constexpr S act(const S &x) const {
static_assert(std::is_base_of<Set<acted_value_type>, S>::value);
return S(mapping(this->val, x.value()));
}
};
namespace element {
template <typename S>
constexpr auto zero = []() -> S { return S(); };
template <typename S>
constexpr auto one = []() -> S { return 1; };
template <typename S>
constexpr auto min = []() -> S { return std::numeric_limits<S>::min(); };
template <typename S>
constexpr auto max = []() -> S { return std::numeric_limits<S>::max(); };
template <typename S>
constexpr auto one_below_max = []() -> S { return std::numeric_limits<S>::max() - 1; };
template <typename S>
constexpr auto lowest = []() -> S { return std::numeric_limits<S>::lowest(); };
template <typename S>
constexpr auto one_above_lowest = []() -> S { return std::numeric_limits<S>::lowest() + 1; };
} // namespace element
namespace uoperator {
template <typename S>
constexpr auto identity = [](const S &val) -> S { return val; };
template <typename S>
constexpr auto negate = [](const S &val) -> S { return -val; };
} // namespace uoperator
namespace boperator {
template <typename T, typename S = T>
constexpr auto plus = [](const T &lhs, const S &rhs) -> S { return lhs + rhs; };
template <typename T, typename S = T>
constexpr auto mul = [](const T &lhs, const S &rhs) -> S { return lhs * rhs; };
template <typename T, typename S = T>
constexpr auto bit_and = [](const T &lhs, const S &rhs) -> S { return lhs & rhs; };
template <typename T, typename S = T>
constexpr auto bit_or = [](const T &lhs, const S &rhs) -> S { return lhs | rhs; };
template <typename T, typename S = T>
constexpr auto bit_xor = [](const T &lhs, const S &rhs) -> S { return lhs ^ rhs; };
template <typename T, typename S = T>
constexpr auto min = [](const T &lhs, const S &rhs) -> S { return std::min<S>(lhs, rhs); };
template <typename T, typename S = T>
constexpr auto max = [](const T &lhs, const S &rhs) -> S { return std::max<S>(lhs, rhs); };
template <typename T, typename S = T>
constexpr auto gcd = [](const T &lhs, const S &rhs) -> S { return std::gcd(lhs, rhs); };
template <typename T, typename S = T>
constexpr auto lcm = [](const T &lhs, const S &rhs) -> S { return std::lcm(lhs, rhs); };
template <typename F, auto id, typename X = F>
constexpr auto assign_if_not_id = [](const F &lhs, const X &rhs) -> X {
static_assert(std::is_invocable_r<F, decltype(id)>::value);
return (lhs == id() ? rhs : lhs);
};
} // namespace boperator
namespace monoid {
template <typename S>
using minimum = Monoid<S, boperator::min<S>, element::max<S>>;
template <typename S>
using minimum_safe = Monoid<S, boperator::min<S>, element::one_below_max<S>>;
template <typename S>
using maximum = Monoid<S, boperator::max<S>, element::lowest<S>>;
template <typename S>
using maximum_safe = Monoid<S, boperator::max<S>, element::one_above_lowest<S>>;
template <typename S>
using addition = Monoid<S, boperator::plus<S>, element::zero<S>>;
template <typename S>
using multiplication = Monoid<S, boperator::mul<S>, element::one<S>>;
template <typename S>
using bit_xor = Monoid<S, boperator::bit_xor<S>, element::zero<S>>;
} // namespace monoid
namespace group {
template <typename S>
using addition = Group<S, boperator::plus<S>, element::zero<S>, uoperator::negate<S>>;
template <typename S>
using bit_xor = Group<S, boperator::bit_xor<S>, element::zero<S>, uoperator::identity<S>>;
} // namespace group
namespace operator_monoid {
template <typename F, typename X = F>
using assign_for_minimum = OperatorMonoid<
F, boperator::assign_if_not_id<F, element::max<F>>, element::max<F>,
X, boperator::assign_if_not_id<F, element::max<F>, X>>;
template <typename F, typename X = F>
using assign_for_maximum = OperatorMonoid<
F, boperator::assign_if_not_id<F, element::lowest<F>>, element::lowest<F>,
X, boperator::assign_if_not_id<F, element::lowest<F>, X>>;
template <typename F, typename X = F>
using addition = OperatorMonoid<F, boperator::plus<F>, element::zero<F>, X, boperator::plus<F, X>>;
} // namespace operator_monoid
} // namespace algebra
} // namespace algorithm
#line 13 "algorithm/DataStructure/SegmentTree/lazy_segment_tree.hpp"
namespace algorithm {
namespace lazy_segment_tree {
template <class ActedMonoid, class OperatorMonoid>
class LazySegmentTree {
public:
using acted_monoid_type = ActedMonoid;
using operator_monoid_type = OperatorMonoid;
using acted_value_type = acted_monoid_type::value_type;
using operator_value_type = operator_monoid_type::value_type;
private:
int m_sz; // m_sz:=(要素数).
int m_n; // m_n:=(完全二分木の葉数).
int m_depth; // m_depth:=(完全二分木の深さ).
std::vector<acted_monoid_type> m_tree; // m_tree(2n)[]:=(完全二分木). 1-based index.
std::vector<operator_monoid_type> m_lazy; // m_lazy(n)[k]:=(m_tree[k]の子 (m_tree[2k], m_tree[2k+1]) に対する遅延評価).
void apply_with_lazy(int k, const operator_monoid_type &f) {
m_tree[k] = f.act(m_tree[k]);
if(k < m_n) m_lazy[k] = f * m_lazy[k];
}
void push(int k) {
apply_with_lazy(k << 1, m_lazy[k]);
apply_with_lazy(k << 1 | 1, m_lazy[k]);
m_lazy[k] = operator_monoid_type::one();
}
void update(int k) { m_tree[k] = m_tree[k << 1] * m_tree[k << 1 | 1]; }
void build() {
for(int i = 1; i <= m_depth; ++i) {
int l = m_n >> i, r = (m_n + m_sz - 1) >> i;
for(int j = r; j >= l; --j) update(j);
}
}
public:
// constructor. O(N).
LazySegmentTree() : LazySegmentTree(0) {}
explicit LazySegmentTree(int n) : m_sz(n), m_n(1), m_depth(0) {
assert(n >= 0);
while(m_n < m_sz) m_n <<= 1, ++m_depth;
m_tree.assign(2 * m_n, acted_monoid_type::one());
m_lazy.assign(m_n, operator_monoid_type::one());
}
explicit LazySegmentTree(int n, const acted_value_type &a) : LazySegmentTree(n, acted_monoid_type(a)) {}
explicit LazySegmentTree(int n, const acted_monoid_type &a) : LazySegmentTree(n) {
std::fill_n(m_tree.begin() + m_n, n, a);
build();
}
template <std::input_iterator InputIter>
explicit LazySegmentTree(InputIter first, InputIter last) : m_n(1), m_depth(0), m_tree(first, last) {
m_sz = m_tree.size();
while(m_n < m_sz) m_n <<= 1, ++m_depth;
m_tree.reserve(2 * m_n);
m_tree.insert(m_tree.begin(), m_n, acted_monoid_type::one());
m_tree.resize(2 * m_n, acted_monoid_type::one());
m_lazy.resize(m_n, operator_monoid_type::one());
build();
}
template <typename T>
explicit LazySegmentTree(std::initializer_list<T> il) : LazySegmentTree(il.begin(), il.end()) {}
// 要素数を取得する．
int size() const { return m_sz; }
// k番目の要素をaに置き換える．O(log N).
void set(int k, const acted_value_type &a) { set(k, acted_monoid_type(a)); }
void set(int k, const acted_monoid_type &a) {
assert(0 <= k and k < size());
k += m_n;
for(int i = m_depth; i >= 1; --i) push(k >> i);
m_tree[k] = a;
for(int i = 1; i <= m_depth; ++i) update(k >> i);
}
// k番目の要素を作用素fを用いて更新する．O(log N).
void apply(int k, const operator_value_type &f) { apply(k, operator_monoid_type(f)); }
void apply(int k, const operator_monoid_type &f) {
assert(0 <= k and k < size());
k += m_n;
for(int i = m_depth; i >= 1; --i) push(k >> i);
m_tree[k] = f.act(m_tree[k]);
for(int i = 1; i <= m_depth; ++i) update(k >> i);
}
// 区間[l,r)の要素を作用素fを用いて更新する．O(log N).
void apply(int l, int r, const operator_value_type &f) { apply(l, r, operator_monoid_type(f)); }
void apply(int l, int r, const operator_monoid_type &f) {
assert(0 <= l and l <= r and r <= size());
if(l == r) return;
l += m_n, r += m_n;
for(int i = m_depth; i >= 1; --i) {
if((l >> i) << i != l) push(l >> i);
if((r >> i) << i != r) push((r - 1) >> i);
}
for(int ll = l, rr = r; ll < rr; ll >>= 1, rr >>= 1) {
if(ll & 1) apply_with_lazy(ll++, f);
if(rr & 1) apply_with_lazy(--rr, f);
}
for(int i = 1; i <= m_depth; ++i) {
if((l >> i) << i != l) update(l >> i);
if((r >> i) << i != r) update((r - 1) >> i);
}
}
// k番目の要素を求める．O(log N).
acted_value_type prod(int k) {
assert(0 <= k and k < size());
k += m_n;
for(int i = m_depth; i >= 1; --i) push(k >> i);
return m_tree[k].value();
}
// 区間[l,r)の要素の総積を求める．O(log N).
acted_value_type prod(int l, int r) {
assert(0 <= l and l <= r and r <= size());
if(l == r) return acted_monoid_type::one().value();
l += m_n, r += m_n;
for(int i = m_depth; i >= 1; --i) {
if((l >> i) << i != l) push(l >> i);
if((r >> i) << i != r) push((r - 1) >> i);
}
acted_monoid_type &&val_l = acted_monoid_type::one(), &&val_r = acted_monoid_type::one();
for(; l < r; l >>= 1, r >>= 1) {
if(l & 1) val_l = val_l * m_tree[l++];
if(r & 1) val_r = m_tree[--r] * val_r;
}
return (val_l * val_r).value();
}
// 区間全体の要素の総積を取得する．O(1).
acted_value_type prod_all() const { return m_tree[1].value(); }
// pred(prod(l,r))==true となる区間の最右位値rを二分探索する．
// ただし，区間[l,n)の要素はpred(S)によって区分化されていること．また，pred(e)==true であること．O(log N).
template <bool (*pred)(acted_value_type)>
int most_right(int l) const {
return most_right(l, [](const acted_value_type &x) -> bool { return pred(x); });
}
template <class Pred>
int most_right(int l, Pred pred) const {
static_assert(std::is_invocable_r<bool, Pred, acted_value_type>::value);
assert(0 <= l and l <= size());
assert(pred(acted_monoid_type::one().value()));
if(l == m_sz) return m_sz;
l += m_n;
for(int i = m_depth; i >= 1; --i) push(l >> i);
acted_monoid_type &&val = acted_monoid_type::one();
do {
while(!(l & 1)) l >>= 1;
acted_monoid_type &&tmp = val * m_tree[l];
if(!pred(tmp.value())) {
while(l < m_n) {
push(l);
l <<= 1;
tmp = val * m_tree[l];
if(pred(tmp.value())) val = tmp, ++l;
}
return l - m_n;
}
val = tmp, ++l;
} while((l & -l) != l);
return m_sz;
}
// pred(prod(l,r))==true となる区間の最左位値lを二分探索する．
// ただし，区間[0,r)の要素はpred(S)によって区分化されていること．また，pred(e)==true であること．O(log N).
template <bool (*pred)(acted_value_type)>
int most_left(int r) const {
return most_left(r, [](const acted_value_type &x) -> bool { return pred(x); });
}
template <class Pred>
int most_left(int r, Pred pred) const {
static_assert(std::is_invocable_r<bool, Pred, acted_value_type>::value);
assert(0 <= r and r <= size());
assert(pred(acted_monoid_type::one().value()));
if(r == 0) return 0;
r += m_n;
for(int i = m_depth; i >= 1; --i) push((r - 1) >> i);
acted_monoid_type &&val = acted_monoid_type::one();
do {
--r;
while(r > 1 and (r & 1)) r >>= 1;
acted_monoid_type &&tmp = m_tree[r] * val;
if(!pred(tmp.value())) {
while(r < m_n) {
push(r);
r = r << 1 | 1;
tmp = m_tree[r] * val;
if(pred(tmp.value())) val = tmp, --r;
}
return r - m_n + 1;
}
val = tmp;
} while((r & -r) != r);
return 0;
}
void reset() {
std::fill(m_tree.begin() + 1, m_tree.end(), acted_monoid_type::one());
std::fill(m_lazy.begin() + 1, m_lazy.end(), operator_monoid_type::one());
}
friend std::ostream &operator<<(std::ostream &os, const LazySegmentTree &rhs) {
os << "{\n [\n";
for(int i = 0; i <= rhs.m_depth; ++i) {
int l = 1 << i, r = 2 << i;
for(int j = l; j < r; ++j) os << (j == l ? " [" : " ") << rhs.m_tree[j].value();
os << "]\n";
}
os << " ],\n [\n";
for(int i = 0; i < rhs.m_depth; ++i) {
int l = 1 << i, r = 2 << i;
for(int j = l; j < r; ++j) os << (j == l ? " [" : " ") << rhs.m_lazy[j].value();
os << "]\n";
}
return os << " ]\n}";
}
};
namespace internal {
namespace range_sum_range_update {
template <typename T>
struct S {
T val;
int size;
constexpr S() : S(T(), 0) {}
constexpr S(const T &val) : S(val, 1) {}
constexpr S(const T &val, int size) : val(val), size(size) {}
friend constexpr S operator+(const S &lhs, const S &rhs) { return {lhs.val + rhs.val, lhs.size + rhs.size}; }
friend std::ostream &operator<<(std::ostream &os, const S &rhs) { return os << "{" << rhs.val << ", " << rhs.size << "}"; }
};
template <typename T>
using acted_monoid = algebra::Monoid<S<T>, algebra::boperator::plus<S<T>>, algebra::element::zero<S<T>>>;
template <typename F>
constexpr auto id = algebra::element::max<F>;
template <typename F>
constexpr auto compose = algebra::boperator::assign_if_not_id<F, id<F>>;
template <typename F, typename T = F>
constexpr auto mapping = [](const F &f, const S<T> &x) -> S<T> {
static_assert(std::is_invocable_r<F, decltype(id<F>)>::value);
return {(f == id<F>() ? x.val : f * x.size), x.size};
};
template <typename F, typename T = F>
using operator_monoid = algebra::OperatorMonoid<F, compose<F>, id<F>, S<T>, mapping<F, T>>;
} // namespace range_sum_range_update
namespace range_sum_range_add {
template <typename T>
using S = range_sum_range_update::S<T>;
template <typename T>
using acted_monoid = range_sum_range_update::acted_monoid<T>;
template <typename F>
constexpr auto id = algebra::element::zero<F>;
template <typename F>
constexpr auto compose = algebra::boperator::plus<F>;
template <typename F, typename T = F>
constexpr auto mapping = [](const F &f, const S<T> &x) -> S<T> { return {x.val + f * x.size, x.size}; };
template <typename F, typename T = F>
using operator_monoid = algebra::OperatorMonoid<F, compose<F>, id<F>, S<T>, mapping<F, T>>;
} // namespace range_sum_range_add
namespace range_sum_range_affine {
template <typename T>
using S = range_sum_range_update::S<T>;
template <typename T>
using acted_monoid = range_sum_range_update::acted_monoid<T>;
template <typename U>
struct F {
U a;
U b;
constexpr F() : F(U(), U()) {}
constexpr F(const U &a, const U &b) : a(a), b(b) {}
friend constexpr F operator*(const F &lhs, const F &rhs) { return {lhs.a * rhs.a, lhs.a * rhs.b + lhs.b}; }
friend std::ostream &operator<<(std::ostream &os, const F &rhs) { return os << "{" << rhs.a << ", " << rhs.b << "}"; }
};
template <typename U>
constexpr auto id = []() -> F<U> { return {1, 0}; };
template <typename U>
constexpr auto compose = algebra::boperator::mul<F<U>>;
template <typename U, typename T = U>
constexpr auto mapping = [](const F<U> &f, const S<T> &x) -> S<T> { return {f.a * x.val + f.b * x.size, x.size}; };
template <typename U, typename T = U>
using operator_monoid = algebra::OperatorMonoid<F<U>, compose<U>, id<U>, S<T>, mapping<U, T>>;
} // namespace range_sum_range_affine
} // namespace internal
template <typename S, typename F = S>
using range_minimum_range_update_lazy_segment_tree = LazySegmentTree<algebra::monoid::minimum_safe<S>, algebra::operator_monoid::assign_for_minimum<F, S>>;
template <typename S, typename F = S>
using range_minimum_range_add_lazy_segment_tree = LazySegmentTree<algebra::monoid::minimum<S>, algebra::operator_monoid::addition<F, S>>;
template <typename S, typename F = S>
using range_maximum_range_update_lazy_segment_tree = LazySegmentTree<algebra::monoid::maximum_safe<S>, algebra::operator_monoid::assign_for_maximum<F, S>>;
template <typename S, typename F = S>
using range_maximum_range_add_lazy_segment_tree = LazySegmentTree<algebra::monoid::maximum<S>, algebra::operator_monoid::addition<F, S>>;
template <typename T, typename F = T>
using range_sum_range_update_lazy_segment_tree = LazySegmentTree<internal::range_sum_range_update::acted_monoid<T>, internal::range_sum_range_update::operator_monoid<F, T>>;
template <typename T, typename F = T>
using range_sum_range_add_lazy_segment_tree = LazySegmentTree<internal::range_sum_range_add::acted_monoid<T>, internal::range_sum_range_add::operator_monoid<F, T>>;
template <typename T, typename U = T>
using range_sum_range_affine_lazy_segment_tree = LazySegmentTree<internal::range_sum_range_affine::acted_monoid<T>, internal::range_sum_range_affine::operator_monoid<U, T>>;
} // namespace lazy_segment_tree
} // namespace algorithm
#line 6 "verify/aoj-DSL_2_G-lazy_segment_tree.test.cpp"
int main() {
int n;
int q;
std::cin >> n >> q;
algorithm::lazy_segment_tree::range_sum_range_add_lazy_segment_tree<long long> segtree(n, {0, 1});
while(q--) {
int type;
std::cin >> type;
if(type == 0) {
int s, t;
long long x;
std::cin >> s >> t >> x;
--s;
segtree.apply(s, t, x);
} else {
int s, t;
std::cin >> s >> t;
--s;
auto &&ans = segtree.prod(s, t).val;
std::cout << ans << "\n";
}
}
}