byslib
This documentation is automatically generated by online-judge-tools/verification-helper modified by bayashi_cl
test/yosupo/range_affine_range_sum.test.cpp
- View this file on GitHub
- Last update: 2022-12-02 17:23:25+09:00
- Problem: https://judge.yosupo.jp/problem/range_affine_range_sum
Depends on
- Mapping
(byslib/algebra/mapping.hpp)
- Modint
(byslib/algebra/modint.hpp)
- Monoid
(byslib/algebra/monoid.hpp)
- Const
(byslib/core/constant.hpp)
- byslib/core/int_alias.hpp
- Types
(byslib/core/traits.hpp)
- Lazy Segment Tree
(byslib/ds/lazy_segment_tree.hpp)
- chmin/chmax
(byslib/extension/change.hpp)
- Python::enumerate
(byslib/extension/enumerate.hpp)
- Python::range
(byslib/extension/irange.hpp)
- Macro
(byslib/extension/macro.hpp)
- byslib/extension/subrange.hpp
- I/O
(byslib/io/io.hpp)
- Output
(byslib/io/printer.hpp)
- Input
(byslib/io/scanner.hpp)
- Bit
(byslib/ntheory/bit.hpp)
- Numeric
(byslib/ntheory/numeric.hpp)
- Prime
(byslib/ntheory/prime.hpp)
- Solver
(byslib/procon/solver.hpp)
- STL Template
(byslib/procon/stdlib.hpp)
- byslib/template.hpp
Code
#define PROBLEM "https://judge.yosupo.jp/problem/range_affine_range_sum"
#include "../../byslib/algebra/modint.hpp"
#include "../../byslib/algebra/monoid.hpp"
#include "../../byslib/ds/lazy_segment_tree.hpp"
#include "../../byslib/template.hpp"
namespace bys {
void Solver::solve() {
auto [n, q] = scanner.read<i32, 2>();
auto a = scanner.readvec<Mint>(n);
LazySegmentTree<Add<Mint>, Affine<Mint>> seg(a);
for (UV : irange(q)) {
auto t = scanner.read<i32>();
if (t == 0) {
auto [l, r, b, c] = scanner.read<i32, 4>();
seg.effect(l, r, {b, c});
} else {
auto [l, r] = scanner.read<i32, 2>();
print(seg.fold(l, r));
}
}
}
} // namespace bys
int main() { return bys::Solver::main(/* bys::scanner.read<int>() */); }#define PROBLEM "https://judge.yosupo.jp/problem/range_affine_range_sum"
#include <cstddef>
#include <limits>
#include <tuple>
#include <utility>
#include <cstdint>
namespace bys {
using i8 = std::int8_t;
using i16 = std::int16_t;
using i32 = std::int32_t;
using i64 = std::int64_t;
using i128 = __int128_t;
using u8 = std::uint8_t;
using u16 = std::uint16_t;
using u32 = std::uint32_t;
using u64 = std::uint64_t;
using u128 = __uint128_t;
using f32 = float;
using f64 = double;
using f128 = long double;
using isize = std::ptrdiff_t;
using usize = std::size_t;
#define DEFINE_NUM_LITERAL(name, type) \
constexpr auto operator"" name(unsigned long long x) { return static_cast<type>(x); }
DEFINE_NUM_LITERAL(_i8, std::int8_t);
DEFINE_NUM_LITERAL(_i16, std::int16_t);
DEFINE_NUM_LITERAL(_i32, std::int32_t);
DEFINE_NUM_LITERAL(_i64, std::int64_t);
DEFINE_NUM_LITERAL(_i128, __int128_t);
DEFINE_NUM_LITERAL(_u8, std::uint8_t);
DEFINE_NUM_LITERAL(_u16, std::uint16_t);
DEFINE_NUM_LITERAL(_u32, std::uint32_t);
DEFINE_NUM_LITERAL(_u64, std::uint64_t);
DEFINE_NUM_LITERAL(_u128, __uint128_t);
DEFINE_NUM_LITERAL(_z, std::size_t);
#undef DEFINE_NUM_LITERAL
} // namespace bys
#include <array>
#include <iostream>
#include <type_traits>
/**
* @file traits.hpp
* @brief Types
*
* type_traits拡張
*/
namespace bys {
template <class, class = void> struct has_rshift_from_istream : std::false_type {};
template <class T>
struct has_rshift_from_istream<T, std::void_t<decltype(std::declval<std::istream&>() >> std::declval<T&>())>> : std::true_type {};
template <class T> constexpr bool has_rshift_from_istream_v = has_rshift_from_istream<T>::value;
template <class, class = void> struct has_lshift_to_ostream : std::false_type {};
template <class T>
struct has_lshift_to_ostream<T, std::void_t<decltype(std::declval<std::ostream&>() << std::declval<T&>())>> : std::true_type {};
template <class T> constexpr bool has_lshft_to_ostream_v = has_lshift_to_ostream<T>::value;
template <class, class = void> struct is_tuple_like : std::false_type {};
template <class T> struct is_tuple_like<T, std::void_t<decltype(std::tuple_size<T>())>> : std::true_type {};
template <class T> constexpr bool is_tuple_like_v = is_tuple_like<T>::value;
template <class, class = void> struct is_iterable : std::false_type {};
template <class T> struct is_iterable<T, std::void_t<decltype(std::begin(std::declval<T>()))>> : std::true_type {};
template <class T> constexpr bool is_iterable_v = is_iterable<T>::value;
template <class T> struct Indexed {
static_assert(std::is_integral_v<T>);
using resolve_to = T;
};
using i32_1 = Indexed<i32>;
using i64_1 = Indexed<i64>;
template <class, class = void> struct is_indexed : std::false_type {};
template <class T> struct is_indexed<Indexed<T>> : std::true_type {};
template <class T> constexpr bool is_indexed_v = is_indexed<T>::value;
template <class T, class = void> struct resolve_type { using type = T; };
template <class T> struct resolve_type<T, std::void_t<typename T::resolve_to>> { using type = typename T::resolve_to; };
template <class T, std::size_t N> struct resolve_type<std::array<T, N>> {
using type = std::array<typename resolve_type<T>::type, N>;
};
template <class T, class U> struct resolve_type<std::pair<T, U>> {
using type = std::pair<typename resolve_type<T>::type, typename resolve_type<U>::type>;
};
template <class... Args> struct resolve_type<std::tuple<Args...>> {
using type = std::tuple<typename resolve_type<Args>::type...>;
};
template <class T> using resolve_type_t = typename resolve_type<T>::type;
} // namespace bys
/**
* @file constant.hpp
* @brief Const
*/
namespace bys {
constexpr i32 MOD7 = 1000000007;
constexpr i32 MOD9 = 998244353;
constexpr i32 MOD = MOD9;
template <class T> constexpr T get_inf();
namespace impl {
template <class Tp, std::size_t... I> constexpr auto get_inf_tuple(std::index_sequence<I...>) {
return Tp{get_inf<typename std::tuple_element_t<I, Tp>>()...};
}
} // namespace impl
template <class T> constexpr T get_inf() {
if constexpr (std::is_integral_v<T>) {
return std::numeric_limits<T>::max() / (T)2;
} else if constexpr (std::is_floating_point_v<T>) {
return std::numeric_limits<T>::infinity();
} else if constexpr (is_tuple_like_v<T>) {
return impl::get_inf_tuple<T>(std::make_index_sequence<std::tuple_size_v<T>>());
} else {
static_assert([]() { return false; }, "Type Error");
}
}
template <class T> constexpr bool is_inf(T x) { return x == get_inf<T>(); }
constexpr auto INF = get_inf<i32>();
constexpr auto LINF = get_inf<i64>();
} // namespace bys
#include <vector>
#include <algorithm>
#include <cassert>
#include <string>
/**
* @file bit.hpp
* @brief Bit
* @note c++20で<bit>が追加される
*/
namespace bys {
/**
* @brief bit幅
*
* bit_width(x) - 1 < log2(x) <= bit_width(x)
*/
template <class T> constexpr i32 bit_width(T x) {
i32 bits = 0;
x = (x < 0) ? (-x) : x;
for (; x != 0; bits++) x >>= 1;
return bits;
}
//! @brief 2冪に切り下げ
template <class T> constexpr T bit_floor(T x) {
assert(x >= 0);
return x == 0 ? 0 : T(1) << (bit_width(x) - 1);
}
//! @brief 2冪に切り上げ
template <class T> constexpr T bit_ceil(T x) {
assert(x >= 0);
return x == 0 ? 1 : T(1) << bit_width(x - 1);
}
//! @brief 2進文字列に変換
template <class T> std::string bin(T n) {
assert(n >= 0);
if (n == 0) return "0";
std::string res;
while (n > 0) {
res.push_back(n & 1 ? '1' : '0');
n >>= 1;
}
std::reverse(res.begin(), res.end());
return res;
}
//! @brief d bit目が立っているか
template <class T> constexpr bool pop(T s, i32 d) { return s & (T(1) << d); }
} // namespace bys
/**
* @file numeric.hpp
* @brief Numeric
*
* 数値計算詰め合わせ
*/
namespace bys {
//! @brief 整数の累乗
constexpr i64 int_pow(i32 a, i32 b) {
i64 res = 1;
for (i32 i = 0; i < b; ++i) res *= a;
return res;
}
/**
* @brief 繰り返し二乗法
*
* O(log q)
*/
constexpr i64 mod_pow(i64 p, i64 q, i64 mod) {
if (mod == 1) return 0_i64;
i128 res = 1;
i128 b = p % mod;
while (q) {
if (q & 1) res = res * b % mod;
b = b * b % mod;
q >>= 1;
}
return (i64)res;
}
//! @brief ceil(x / y)
template <class T> constexpr T ceildiv(T x, T y) {
if ((x < T(0)) ^ (y < T(0))) {
return x / y;
} else {
return (x + y + (x < T(0) ? 1 : -1)) / y;
}
}
//! @brief floor(x / y)
template <class T> constexpr T floordiv(T x, T y) {
if ((x < T(0)) ^ (y < T(0))) {
return (x - y + (x < T(0) ? 1 : -1)) / y;
} else {
return x / y;
}
}
/**
* @brief Python::divmod
*
* See: https://docs.python.org/ja/3/library/functions.html#divmod
*/
template <class T> constexpr std::pair<T, T> divmod(T x, T y) {
auto q = floordiv(x, y);
return {q, x - q * y};
}
/**
* @brief Python::%
*
* See: https://docs.python.org/ja/3/reference/expressions.html#index-68
*/
template <class T, class S> constexpr T floormod(T x, S mod) {
x %= mod;
if (x < 0) x += mod;
return x;
}
namespace impl {
constexpr i64 isqrt_aux(i64 c, i64 n) {
if (c == 0) return 1;
i64 k = (c - 1) / 2;
i64 a = isqrt_aux(c / 2, n >> (2 * k + 2));
return (a << k) + (n >> (k + 2)) / a;
}
} // namespace impl
/**
* @brief Python::math.isqrt
*
* floor(sqrt(n))
* See: https://docs.python.org/ja/3/library/math.html#math.isqrt
*/
template <class T> constexpr T isqrt(T n) {
assert(n >= 0);
if (n == T(0)) return T(0);
i64 a = impl::isqrt_aux((bit_width(n) - 1) / 2, n);
return n < a * a ? a - 1 : a;
}
/**
* @brief Nim::math::almostEqual
*
* See: https://nim-lang.org/docs/math.html#almostEqual,T,T,Natural
*/
template <class T, typename std::enable_if_t<std::is_floating_point_v<T>, std::nullptr_t> = nullptr>
constexpr bool isclose(T x, T y, T coef = 4.0) {
if (x == y) return true;
auto diff = std::abs(x - y);
return diff <= std::numeric_limits<T>::epsilon() * std::abs(x + y) * coef || diff < std::numeric_limits<T>::min();
}
constexpr std::pair<i64, i64> inv_gcd(i64 a, i64 b) {
a = floormod(a, b);
if (a == 0) return {b, 0};
i64 s = b, t = a;
i64 m0 = 0, m1 = 1;
while (t) {
i64 u = s / t;
s -= t * u;
m0 -= m1 * u;
auto tmp = s;
s = t;
t = tmp;
tmp = m0;
m0 = m1;
m1 = tmp;
}
if (m0 < 0) m0 += b / s;
return {s, m0};
}
//! @brief Count multipules of k in the [left, right)
template <class T> constexpr T range_multiples(T left, T right, T k) { return (right - 1) / k - (left - 1) / k; }
template <class T> constexpr T multiple_floor(T x, T k) { return x / k * k; }
template <class T> constexpr T multiple_ceil(T x, T k) { return ceildiv(x, k) * k; }
} // namespace bys
/**
* @file prime.hpp
* @brief Prime
*/
namespace bys {
/**
* @brief 素因数分解
*
* 試し割り法
* O(√n)
*/
template <typename T> std::vector<T> prime_factorize(T n) {
std::vector<T> res;
while (n % 2 == 0) {
res.push_back(2);
n /= 2;
}
T f = 3;
while (f * f <= n) {
if (n % f == 0) {
res.push_back(f);
n /= f;
} else {
f += 2;
}
}
if (n != 1) res.push_back(n);
return res;
}
namespace impl {
template <std::size_t N> constexpr bool miller_rabin(i64 n, std::array<i64, N> bases) {
auto d = n - 1;
while (d % 2 == 0) d >>= 1;
for (auto b : bases) {
if (n <= b) break;
auto t = d;
i128 y = mod_pow(b, t, n);
while (t != n - 1 && y != 1 && y != n - 1) {
y = y * y % n;
t <<= 1;
}
if (y != n - 1 && t % 2 == 0) {
return false;
}
}
return true;
}
} // namespace impl
/**
* @brief Miller-Rabin素数判定
*
* 2^64以下なら正確に判定できる
* See: https://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test
* See: https://miller-rabin.appspot.com
*
* @note c++20でconstexpr関数内でもvectorが使えるように
*/
constexpr bool is_prime(i64 n) {
if (not(n & 1)) return n == 2;
if (n <= 1) return false;
if (n <= std::numeric_limits<i32>::max()) {
std::array<i64, 3> bases = {2, 7, 61};
return impl::miller_rabin(n, bases);
} else {
std::array<i64, 7> bases = {2, 325, 9375, 28178, 450775, 9780504, 1795265022};
return impl::miller_rabin(n, bases);
}
}
} // namespace bys
/**
* @file modint.hpp
* @brief Modint
*/
namespace bys {
/**
* @brief ModInt
*
* ac-libraryのmodintをconstexpr化したもの
* See: https://atcoder.github.io/ac-library/document_ja/modint.html
*
* @tparam Modulo 法
*/
template <u32 Modulo> class ModInt {
u32 _v;
public:
static constexpr u32 mod = Modulo;
// static_assert(is_prime(mod), "Modulo need to be prime.");
static_assert(mod < (std::numeric_limits<u32>::max() >> 1), "Modulo need to be <2^31.");
constexpr ModInt() noexcept : _v(0) {}
template <class T, std::enable_if_t<std::is_unsigned_v<T>, std::nullptr_t> = nullptr>
constexpr ModInt(T v) noexcept : _v(v % mod) {}
template <class T, std::enable_if_t<std::is_signed_v<T>, std::nullptr_t> = nullptr>
constexpr ModInt(T v) noexcept : _v(floormod(v, mod)) {}
constexpr ModInt pow(i64 n) const noexcept {
ModInt res = 1, p = *this;
while (n) {
if (n & 1) res *= p;
p *= p;
n >>= 1;
}
return res;
}
constexpr ModInt inv() const noexcept {
if constexpr (is_prime(mod)) {
return pow(mod - 2);
} else {
return inv_gcd(_v, mod).second;
}
}
constexpr ModInt& operator+=(const ModInt rhs) noexcept {
_v += rhs._v;
if (_v >= mod) _v -= mod;
return *this;
}
constexpr ModInt& operator-=(const ModInt rhs) noexcept {
if (rhs._v > _v) _v += mod;
_v -= rhs._v;
return *this;
}
constexpr ModInt& operator*=(const ModInt rhs) noexcept {
u64 z = _v;
z *= rhs._v;
_v = (u32)(z % mod);
return *this;
}
constexpr ModInt& operator/=(const ModInt rhs) noexcept { return *this = *this * rhs.inv(); }
constexpr ModInt operator+() const noexcept { return *this; }
constexpr ModInt operator-() const noexcept { return ModInt() - *this; }
constexpr ModInt& operator++() noexcept {
_v++;
if (_v == mod) _v = 0;
return *this;
}
constexpr ModInt& operator--() noexcept {
if (_v == 0) _v = mod;
--_v;
return *this;
}
constexpr ModInt operator++(i32) noexcept {
ModInt res = *this;
++*this;
return res;
}
constexpr ModInt operator--(i32) noexcept {
ModInt res = *this;
--*this;
return res;
}
friend constexpr ModInt operator+(const ModInt& lhs, const ModInt& rhs) noexcept { return ModInt(lhs) += rhs; }
friend constexpr ModInt operator-(const ModInt& lhs, const ModInt& rhs) noexcept { return ModInt(lhs) -= rhs; }
friend constexpr ModInt operator*(const ModInt& lhs, const ModInt& rhs) noexcept { return ModInt(lhs) *= rhs; }
friend constexpr ModInt operator/(const ModInt& lhs, const ModInt& rhs) noexcept { return ModInt(lhs) /= rhs; }
friend constexpr bool operator==(const ModInt& lhs, const ModInt& rhs) noexcept { return lhs._v == rhs._v; }
friend constexpr bool operator!=(const ModInt& lhs, const ModInt& rhs) noexcept { return lhs._v != rhs._v; }
friend std::istream& operator>>(std::istream& is, ModInt& m) noexcept { return is >> m._v; }
friend std::ostream& operator<<(std::ostream& os, const ModInt& m) noexcept { return os << m._v; }
};
using Mint = ModInt<MOD>;
using Mint7 = ModInt<MOD7>;
using Mint9 = ModInt<MOD9>;
} // namespace bys
#include <optional>
/**
* @file monoid.hpp
* @brief Monoid
*
* モノイド
*/
namespace bys {
struct Magma {
using set_type = std::nullptr_t;
static constexpr set_type operation(set_type, set_type);
static constexpr set_type inverse(set_type);
static constexpr set_type identity{nullptr};
static constexpr bool commutative{false};
};
template <class T> struct Add : Magma {
using set_type = T;
static constexpr set_type operation(set_type a, set_type b) { return a + b; }
static constexpr set_type inverse(set_type a) { return -a; }
static constexpr set_type identity{0};
static constexpr bool commutative{true};
};
template <class T> struct Min : Magma {
using set_type = T;
static constexpr set_type operation(set_type a, set_type b) { return std::min(a, b); }
static constexpr set_type identity{std::numeric_limits<set_type>::max()};
};
template <class T> struct Max : Magma {
using set_type = T;
static constexpr set_type operation(set_type a, set_type b) { return std::max(a, b); }
static constexpr set_type identity{std::numeric_limits<set_type>::min()};
};
template <class T> struct Update : Magma {
using set_type = std::optional<T>;
static constexpr set_type operation(set_type a, set_type b) { return b.has_value() ? b : a; }
static constexpr set_type identity{std::nullopt};
};
template <class T> struct Affine : Magma {
using set_type = std::pair<T, T>;
static constexpr set_type operation(set_type a, set_type b) { return {a.first * b.first, a.second * b.first + b.second}; }
static constexpr set_type identity{1, 0};
};
template <class Modint> struct ModMul : Magma {
using set_type = Modint;
static constexpr set_type operation(set_type a, set_type b) { return a * b; }
static constexpr set_type inverse(set_type a) { return a.inv(); }
static constexpr set_type identity{1};
static constexpr bool commutative{true};
};
template <class T> struct Xor : Magma {
using set_type = T;
static constexpr set_type operation(set_type a, set_type b) { return a ^ b; }
static constexpr set_type inverse(set_type a) { return a; }
static constexpr set_type identity{0};
static constexpr bool commutative{true};
};
template <std::size_t N> struct Perm : Magma {
using set_type = std::array<i32, N>;
static constexpr set_type operation(const set_type& a, const set_type& b) {
set_type res = {};
for (auto i = 0UL; i < N; ++i) res[i] = b[a[i]];
return res;
}
static constexpr set_type inverse(const set_type& a) {
set_type res = {};
for (auto i = 0UL; i < N; ++i) res[a[i]] = i;
return res;
}
static constexpr set_type identity = []() {
set_type res = {};
for (auto i = 0UL; i < N; ++i) res[i] = i;
return res;
}();
};
} // namespace bys
/**
* @file mapping.hpp
* @brief Mapping
*
* 遅延セグ木 作用素
*/
namespace bys {
template <class T, class ActMonoid> struct MappingToSet {
static constexpr void mapping(T&, typename ActMonoid::set_type) {
static_assert([] { return false; }(), "mapping function does not defined.");
}
};
template <class T, class S> struct MappingToSet<T, Add<S>> {
static constexpr void mapping(T& t, typename Add<S>::set_type u) { t += u; }
};
template <class T, class S> struct MappingToSet<T, Min<S>> {
static constexpr void mapping(T& t, typename Min<S>::set_type u) {
if (t > u) t = u;
}
};
template <class T, class S> struct MappingToSet<T, Update<S>> {
static constexpr void mapping(T& t, typename Update<S>::set_type u) {
if (u.has_value()) t = u.value();
}
};
template <class Monoid, class ActMonoid> struct Mapping {
static constexpr void mapping(typename Monoid::set_type&, typename ActMonoid::set_type, i32) {
static_assert([] { return false; }(), "mapping function does not defined.");
}
};
template <class T, class S> struct Mapping<Min<T>, Update<S>> {
static constexpr void mapping(typename Min<T>::set_type& t, typename Update<S>::set_type s, i32) {
if (s.has_value()) t = s.value();
}
};
template <class T, class S> struct Mapping<Add<T>, Add<S>> {
static constexpr void mapping(typename Add<T>::set_type& t, typename Add<S>::set_type s, i32 w) { t += s * w; }
};
template <class T, class S> struct Mapping<Min<T>, Add<S>> {
static constexpr void mapping(typename Min<T>::set_type& t, typename Add<S>::set_type s, i32) { t += s; }
};
template <class T, class S> struct Mapping<Add<T>, Update<S>> {
static constexpr void mapping(typename Add<T>::set_type& t, typename Update<S>::set_type s, i32 w) {
if (s.has_value()) t = s.value() * w;
}
};
template <class T, class S> struct Mapping<Add<T>, Affine<S>> {
static constexpr void mapping(typename Add<T>::set_type& t, typename Affine<S>::set_type s, i32 w) {
t = t * s.first + w * s.second;
}
};
template <class T, class S> struct Mapping<Max<T>, Update<S>> {
static constexpr void mapping(typename Max<T>::set_type& t, typename Update<S>::set_type s, i32) {
if (s.has_value()) t = s.value();
}
};
template <class T, class Modint> struct Mapping<Add<T>, ModMul<Modint>> {
static constexpr void mapping(typename Add<T>::set_type& t, typename ModMul<Modint>::set_type s, i32) { t *= s; }
};
} // namespace bys
/**
* @file lazy_segment_tree.hpp
* @brief Lazy Segment Tree
*/
namespace bys {
/**
* @brief 遅延伝播セグメント木
*
* 区間更新: O(logN)
* 区間クエリ: O(logN)
* 一点取得: O(logN)
* See:
* https://ikatakos.com/pot/programming_algorithm/data_structure/segment_tree/lazy_segment_tree
*
* @tparam Monoid モノイド
* @tparam ActMonoid 作用素モノイド
* @tparam Action 作用関数オブジェクト 区間の幅も渡される
* @todo 二分探索: O(logN)
*/
template <class Monoid, class ActMonoid, class Action = Mapping<Monoid, ActMonoid>> class LazySegmentTree {
using value_type = typename Monoid::set_type;
using act_type = typename ActMonoid::set_type;
i32 _n, n_leaf, logsize;
std::vector<act_type> lazy;
std::vector<value_type> data;
void reload(i32 p) { data[p] = Monoid::operation(data[p * 2], data[p * 2 + 1]); }
void push(const i32 p) {
i32 w = n_leaf >> bit_width(p);
effect_segment(p * 2, lazy[p], w);
effect_segment(p * 2 + 1, lazy[p], w);
lazy[p] = ActMonoid::identity;
}
void effect_segment(const i32 p, act_type f, i32 w) {
Action::mapping(data[p], f, w);
if (p < n_leaf) lazy[p] = ActMonoid::operation(lazy[p], f);
}
public:
LazySegmentTree(i32 n)
: _n(n),
n_leaf(bit_ceil(_n)),
logsize(bit_width(_n - 1)),
lazy(n_leaf, ActMonoid::identity),
data(n_leaf * 2, Monoid::identity) {}
LazySegmentTree(i32 n, value_type init)
: _n(n),
n_leaf(bit_ceil(_n)),
logsize(bit_width(_n - 1)),
lazy(n_leaf, ActMonoid::identity),
data(n_leaf * 2, Monoid::identity) {
std::fill_n(data.begin() + n_leaf, _n, init);
for (i32 i = n_leaf - 1; i > 0; --i) {
data[i] = Monoid::operation(data[i * 2], data[i * 2 + 1]);
}
}
LazySegmentTree(std::vector<value_type> v)
: _n(v.size()),
n_leaf(bit_ceil(_n)),
logsize(bit_width(_n - 1)),
lazy(n_leaf, ActMonoid::identity),
data(n_leaf * 2, Monoid::identity) {
std::copy(v.begin(), v.end(), data.begin() + n_leaf);
for (i32 i = n_leaf - 1; i > 0; --i) {
data[i] = Monoid::operation(data[i * 2], data[i * 2 + 1]);
}
}
value_type operator[](i32 p) {
assert(0 <= p && p < _n);
p += n_leaf;
for (i32 i = logsize; i > 0; --i) push(p >> i);
return data[p];
}
void update(i32 p, const value_type& x) {
assert(0 <= p && p < _n);
p += n_leaf;
for (i32 i = logsize; i > 0; --i) push(p >> i);
data[p] = x;
for (i32 i = 1; i <= logsize; ++i) reload(p >> i);
}
value_type fold(i32 l, i32 r) {
assert(0 <= l);
assert(l <= r);
assert(r <= _n);
if (l == r) return Monoid::identity;
l += n_leaf;
r += n_leaf;
for (i32 i = logsize; i > 0; i--) {
if (((l >> i) << i) != l) push(l >> i);
if (((r >> i) << i) != r) push((r - 1) >> i);
}
value_type left = Monoid::identity, right = Monoid::identity;
for (; l < r; l >>= 1, r >>= 1) {
if (l & 1) left = Monoid::operation(left, data[l++]);
if (r & 1) right = Monoid::operation(data[--r], right);
}
return Monoid::operation(left, right);
}
value_type fold_all() { return data[1]; }
void effect(i32 i, act_type f) { effect(i, i + 1, f); }
void effect(i32 l, i32 r, act_type f) {
assert(0 <= l);
assert(l <= r);
assert(r <= _n);
if (l == r) return;
l += n_leaf;
r += n_leaf;
for (i32 i = logsize; i > 0; i--) {
if (((l >> i) << i) != l) push(l >> i);
if (((r >> i) << i) != r) push((r - 1) >> i);
}
i32 l2 = l, r2 = r;
i32 w = 1;
while (l2 < r2) {
if (l2 & 1) effect_segment(l2++, f, w);
if (r2 & 1) effect_segment(--r2, f, w);
l2 >>= 1;
r2 >>= 1;
w <<= 1;
}
for (i32 i = 1; i <= logsize; i++) {
if (((l >> i) << i) != l) reload(l >> i);
if (((r >> i) << i) != r) reload((r - 1) >> i);
}
}
};
} // namespace bys
/**
* @file template.hpp
* @author bayashi_cl
*
* C++ library for competitive programming by bayashi_cl
* Repository: https://github.com/bayashi-cl/byslib
* Document : https://bayashi-cl.github.io/byslib/
*/
#ifndef LOCAL
#define NDEBUG
#endif
/**
* @file change.hpp
* @brief chmin/chmax
*/
namespace bys {
/**
* @brief 最大値で更新
* @return true 更新されたとき
*/
template <class T> constexpr bool chmax(T& a, T const& b) { return a < b ? a = b, true : false; }
/**
* @brief 最小値で更新
* @return true 更新されたとき
*/
template <class T> constexpr bool chmin(T& a, T const& b) { return a > b ? a = b, true : false; }
} // namespace bys
#include <iterator>
namespace bys {
template <class Iterator> class SubRange {
public:
using iterator = Iterator;
using reverse_iterator = std::reverse_iterator<iterator>;
using value_type = typename iterator::value_type;
SubRange() = default;
SubRange(const SubRange& s) : _begin(s._begin), _end(s._end) {}
SubRange(const iterator& begin, const iterator& end) : _begin(begin), _end(end) {}
iterator begin() const noexcept { return _begin; }
iterator end() const noexcept { return _end; }
reverse_iterator rbegin() const noexcept { return reverse_iterator{_end}; }
reverse_iterator rend() const { return reverse_iterator{_begin}; }
auto operator[](std::size_t i) const noexcept { return *(_begin + i); }
auto size() const noexcept { return _end - _begin; }
bool empty() const noexcept { return _begin == _end; }
auto to_vec() const { return std::vector(_begin, _end); }
private:
iterator _begin, _end;
};
template <class Iterable> auto reversed(Iterable&& iter) {
static_assert(is_iterable_v<Iterable>, "iter is not iterable");
return SubRange(std::rbegin(std::forward<Iterable>(iter)), std::rend(std::forward<Iterable>(iter)));
}
} // namespace bys
/**
* @file enumerate.hpp
* @brief Python::enumerate
*
* Python再現シリーズ enumerate編
* See: https://docs.python.org/ja/3/library/functions.html#enumerate
*/
namespace bys {
template <class Iterator> struct EnumerateIterator {
public:
using difference_type = typename Iterator::difference_type;
using value_type = std::tuple<i32, typename Iterator::value_type>;
// using pointer = value_type*;
using reference = value_type&;
using iterator_category = std::forward_iterator_tag;
EnumerateIterator(const Iterator& iterator, i32 idx) : index(idx), value(iterator) {}
auto& operator++() {
++value;
++index;
return *this;
}
bool operator!=(const EnumerateIterator& other) const { return value != other.value; }
auto operator*() const { return std::tie(index, *value); }
private:
i32 index;
Iterator value;
};
/**
* @brief enumerate
*
* @param iterable 対象
* @param start indexの初期値
*/
template <class Iterable> auto enumerate(Iterable& iterable, i32 start = 0) {
using iterator_t = EnumerateIterator<typename Iterable::iterator>;
i32 end = static_cast<i32>(iterable.size()) + start;
return SubRange(iterator_t(std::begin(iterable), start), iterator_t(std::end(iterable), end));
}
/**
* @brief const enumerate
*
* @param iterable 対象
* @param start indexの初期値
*/
template <class Iterable> auto cenumerate(Iterable& iterable, i32 start = 0) {
using iterator_t = EnumerateIterator<typename Iterable::const_iterator>;
i32 end = static_cast<i32>(iterable.size()) + start;
return SubRange(iterator_t(std::cbegin(iterable), start), iterator_t(std::cend(iterable), end));
}
} // namespace bys
/**
* @file irange.hpp
* @brief Python::range
*
* Python再現シリーズ range編
* See: https://docs.python.org/ja/3/library/stdtypes.html#range
*/
namespace bys {
template <class T> class IntegerIncrementIterator {
public:
using difference_type = std::ptrdiff_t;
using value_type = T;
using reference = T;
using pointer = T*;
using iterator_category = std::bidirectional_iterator_tag;
explicit IntegerIncrementIterator(T x) : value(x) {}
reference operator*() noexcept { return value; }
const reference operator*() const noexcept { return value; }
auto operator++() noexcept {
++value;
return *this;
}
auto operator++(int) noexcept {
auto temp = *this;
++*this;
return temp;
}
auto operator--() noexcept {
--value;
return *this;
}
auto operator--(int) {
auto temp = *this;
--*this;
return temp;
}
bool operator!=(IntegerIncrementIterator const& other) const { return value != other.value; }
bool operator==(IntegerIncrementIterator const& other) const { return value == other.value; }
private:
value_type value;
};
template <class T> class IntegerStepIterator {
public:
using difference_type = std::ptrdiff_t;
using value_type = T;
using reference = T;
using pointer = T*;
using iterator_category = std::bidirectional_iterator_tag;
explicit IntegerStepIterator(T f, T x, T s) : start(f), value(x), step(s) {}
reference operator*() noexcept { return start + value * step; }
const reference operator*() const noexcept { return start + value * step; }
auto operator++() {
++value;
return *this;
}
auto operator++(int) {
auto temp = *this;
++*this;
return temp;
}
auto operator--() {
--value;
return *this;
}
auto operator--(int) {
auto temp = *this;
--*this;
return temp;
}
bool operator!=(IntegerStepIterator const& other) const { return value != other.value; }
bool operator==(IntegerStepIterator const& other) const { return value == other.value; }
private:
value_type start, value, step;
};
template <class T> SubRange<IntegerIncrementIterator<T>> irange(T stop) {
static_assert(std::is_integral_v<T>, "T is not integer.");
using iterator_t = IntegerIncrementIterator<T>;
if (stop < static_cast<T>(0)) stop = static_cast<T>(0);
return SubRange(iterator_t(static_cast<T>(0)), iterator_t(stop));
}
template <class T> SubRange<IntegerIncrementIterator<T>> irange(T start, T stop) {
static_assert(std::is_integral_v<T>, "T is not integer.");
using iterator_t = IntegerIncrementIterator<T>;
if (stop < start) stop = start;
return SubRange(iterator_t(start), iterator_t(stop));
}
template <class T> SubRange<IntegerStepIterator<T>> irange(T start, T stop, T step) {
static_assert(std::is_integral_v<T>, "T is not integer.");
using iterator_t = IntegerStepIterator<T>;
assert(step != 0);
auto w = step >= 0 ? stop - start : start - stop;
auto s = step >= 0 ? step : -step;
if (w < 0) w = 0;
return SubRange(iterator_t(start, static_cast<T>(0), step), iterator_t(start, (w + s - 1) / s, step));
}
} // namespace bys
using std::literals::string_literals::operator""s;
/**
* @file macro.hpp
* @brief Macro
*/
// clang-format off
#define CONCAT_IMPL(a, b) a##b
#define CONCAT(a, b) CONCAT_IMPL(a, b)
//! @brief [[maybe_unused]]な変数を生成。
#define UV [[maybe_unused]] auto CONCAT(unused_val_, __LINE__)
#define RE std::runtime_error("file: "s + __FILE__ + ", line: "s + std::to_string(__LINE__) + ", func: "s + __func__)
#ifdef LOCAL
#define DEBUGBLOCK(block) block
#else
#define DEBUGBLOCK(block)
#endif
// clang-format on
#include <iomanip>
/**
* @file printer.hpp
* @brief Output
*/
namespace bys {
class Printer {
std::ostream& _os;
// sep1 "\n" : iterable<iterable>
// sep2 " " or "\n": iterable, args
// sep3 " " : tuple_like
std::string sep1 = "\n", sep2 = " ", sep3 = " ", end = "\n";
template <std::size_t I, class T> void print_tuple_element(T&& elem) {
if constexpr (I != 0) cat(sep3);
cat(std::forward<T>(elem));
}
template <class Tp, std::size_t... I> void print_tuple(Tp&& tp, std::index_sequence<I...>) {
(print_tuple_element<I>(std::forward<std::tuple_element_t<I, std::decay_t<Tp>>>(std::get<I>(tp))), ...);
}
public:
Printer() = delete;
Printer(std::ostream& os) : _os(os) { _os << std::fixed << std::setprecision(11) << std::boolalpha; }
~Printer() { _os << std::flush; }
template <class T> void cat(T&& v) {
if constexpr (has_lshft_to_ostream_v<std::decay_t<T>>) {
_os << v;
} else if constexpr (is_iterable_v<std::decay_t<T>>) {
std::string sep;
if constexpr (is_iterable_v<typename std::decay_t<T>::value_type>) {
sep = sep1;
} else {
sep = sep2;
}
bool top = true;
for (auto&& vi : v) {
top ? (void)(top = false) : cat(sep);
cat(vi);
}
} else if constexpr (is_tuple_like_v<std::decay_t<T>>) {
print_tuple(std::forward<T>(v), std::make_index_sequence<std::tuple_size_v<std::decay_t<T>>>());
} else {
static_assert([] { return false; }(), "type error");
}
}
void print() { cat(end); }
template <class T> void print(T&& v) {
cat(std::forward<T>(v));
cat(end);
}
template <class T, class... Ts> void print(T&& top, Ts&&... args) {
cat(std::forward<T>(top));
cat(sep2);
print(std::forward<Ts>(args)...);
}
template <class... Ts> void operator()(Ts&&... args) { print(std::forward<Ts>(args)...); }
void flush() { _os << std::flush; }
template <class... Ts> void send(Ts&&... args) {
print(std::forward<Ts>(args)...);
flush();
}
Printer set_sep(const std::string& sep_1, const std::string& sep_2, const std::string& sep_3) {
sep1 = sep_1;
sep2 = sep_2;
sep3 = sep_3;
return *this;
}
Printer set_sep(const std::string& sep_2) {
sep2 = sep_2;
return *this;
}
Printer set_end(const std::string& _end) {
end = _end;
return *this;
}
};
} // namespace bys
/**
* @file scanner.hpp
* @brief Input
*/
namespace bys {
class Scanner {
std::istream& _is;
template <class T, std::size_t... I> auto read_tuple(std::index_sequence<I...>) {
return resolve_type_t<T>{read<typename std::tuple_element_t<I, T>>()...};
}
public:
Scanner() = delete;
Scanner(std::istream& is) : _is(is) { _is.tie(nullptr); }
template <class T> auto read() {
if constexpr (has_rshift_from_istream_v<T>) {
T res;
_is >> res;
return res;
} else if constexpr (is_tuple_like_v<T>) {
return read_tuple<T>(std::make_index_sequence<std::tuple_size_v<T>>());
} else if constexpr (is_indexed_v<T>) {
typename T::resolve_to n;
_is >> n;
return --n;
} else {
static_assert([] { return false; }(), "TypeError");
}
}
template <class... Ts, std::enable_if_t<(sizeof...(Ts) >= 2), std::nullptr_t> = nullptr> auto read() {
return std::tuple{read<Ts>()...};
}
template <class T, std::size_t N> auto read() {
std::array<resolve_type_t<T>, N> res;
for (auto&& e : res) e = read<T>();
return res;
}
template <class T> auto readvec(i32 n) {
std::vector<resolve_type_t<T>> res(n);
for (auto&& e : res) e = read<T>();
return res;
}
template <class T> auto readvec(i32 n, i32 m) {
std::vector<std::vector<resolve_type_t<T>>> res(n);
for (auto&& e : res) e = readvec<T>(m);
return res;
}
};
} // namespace bys
/**
* @file io.hpp
* @brief I/O
*/
namespace bys {
template <class... Args> std::string debugfmt(i32 line, Args&&... args) {
std::stringstream ss;
Printer printer(ss);
ss << "📌 line" << std::setw(4) << line << ": ";
printer.set_sep("\n ", " ", " ");
printer.print(std::forward<Args>(args)...);
return ss.str();
}
Printer print(std::cout), debug(std::cerr);
Scanner scanner(std::cin);
#ifdef LOCAL
//! @brief デバッグ用出力 ジャッジ上では何もしない。
#define DEBUG(...) \
{ \
debug.cat(debugfmt(__LINE__, __VA_ARGS__)); \
debug.flush(); \
}
#else
#define DEBUG(...)
#endif
#define DEBUGCASE(casenum, ...) \
if (TESTCASE == casenum) DEBUG(__VA_ARGS__)
//! @brief printしてreturnする。
#define EXIT(...) \
{ \
print(__VA_ARGS__); \
return; \
}
} // namespace bys
#include <unistd.h>
/**
* @file solver.hpp
* @brief Solver
*/
namespace bys {
struct Solver {
static inline i32 TESTCASE = 1;
static void solve();
static i32 main(i32 t = 1) {
std::ios::sync_with_stdio(false);
for (; TESTCASE <= t; ++TESTCASE) solve();
#ifdef LOCAL
if (not std::cin.good()) std::cerr << "🟡 Input failed." << std::endl;
if (not isatty(STDIN_FILENO) and not std::ws(std::cin).eof()) std::cerr << "🟡 Unused input." << std::endl;
#endif
return 0;
}
};
} // namespace bys
/**
* @file stdlib.hpp
* @brief STL Template
*/
#include <bitset>
#include <cmath>
#include <complex>
#include <functional>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <unordered_map>
#include <unordered_set>
namespace bys {
using std::array, std::vector, std::string, std::set, std::map, std::pair;
using std::cin, std::cout, std::endl;
using std::min, std::max, std::sort, std::reverse, std::abs;
// alias
using Pa = std::pair<i32, i32>;
using Pa64 = std::pair<i64, i64>;
template <class T> using uset = std::unordered_set<T>;
template <class S, class T> using umap = std::unordered_map<S, T>;
} // namespace bys
namespace bys {
void Solver::solve() {
auto [n, q] = scanner.read<i32, 2>();
auto a = scanner.readvec<Mint>(n);
LazySegmentTree<Add<Mint>, Affine<Mint>> seg(a);
for (UV : irange(q)) {
auto t = scanner.read<i32>();
if (t == 0) {
auto [l, r, b, c] = scanner.read<i32, 4>();
seg.effect(l, r, {b, c});
} else {
auto [l, r] = scanner.read<i32, 2>();
print(seg.fold(l, r));
}
}
}
} // namespace bys
int main() { return bys::Solver::main(/* bys::scanner.read<int>() */); }