This documentation is automatically generated by online-judge-tools/verification-helper
#define PROBLEM "https://judge.yosupo.jp/problem/range_affine_range_sum"
#include <iostream>
#include <utility>
#include "../../segment_tree/lazy_segment_tree.hpp"
using llong = long long;
using namespace std;
struct A {
struct M {
using value_type = pair<llong, llong>;
inline static value_type identity() {
return {0, 0};
};
inline static value_type operation(value_type a, value_type b) {
return {(a.first + b.first) % 998244353, a.second + b.second};
};
};
struct O {
using value_type = pair<llong, llong>;
inline static value_type identity() {
return {1ll, 0ll};
};
inline static value_type operation(value_type x, value_type y) {
auto ret = identity();
ret.first = (x.first * y.first) % 998244353;
ret.second = (y.first * x.second + y.second) % 998244353;
return ret;
};
};
using value_structure = M;
using operator_structure = O;
inline static M::value_type operation(M::value_type a, O::value_type b) {
return {(b.first * a.first + b.second * a.second) % 998244353,
a.second};
};
};
llong n, q;
llong a;
llong com, s, t, b, c;
int main() {
cin.tie(nullptr);
ios::sync_with_stdio(false);
cin >> n >> q;
LazySegmentTree<A> seg(n);
for (int i = 0; i < n; i++) {
cin >> a;
seg.set(i, {a, 1});
}
while (q--) {
cin >> com;
if (com == 0) {
cin >> s >> t >> b >> c;
seg.update(s, t, {b, c});
} else {
cin >> s >> t;
cout << seg.fold(s, t).first << '\n';
}
}
}
#line 1 "test/yosupo/range_affine_range_sum.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/range_affine_range_sum"
#include <iostream>
#include <utility>
#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;
};
};
//===
#line 6 "test/yosupo/range_affine_range_sum.test.cpp"
using llong = long long;
using namespace std;
struct A {
struct M {
using value_type = pair<llong, llong>;
inline static value_type identity() {
return {0, 0};
};
inline static value_type operation(value_type a, value_type b) {
return {(a.first + b.first) % 998244353, a.second + b.second};
};
};
struct O {
using value_type = pair<llong, llong>;
inline static value_type identity() {
return {1ll, 0ll};
};
inline static value_type operation(value_type x, value_type y) {
auto ret = identity();
ret.first = (x.first * y.first) % 998244353;
ret.second = (y.first * x.second + y.second) % 998244353;
return ret;
};
};
using value_structure = M;
using operator_structure = O;
inline static M::value_type operation(M::value_type a, O::value_type b) {
return {(b.first * a.first + b.second * a.second) % 998244353,
a.second};
};
};
llong n, q;
llong a;
llong com, s, t, b, c;
int main() {
cin.tie(nullptr);
ios::sync_with_stdio(false);
cin >> n >> q;
LazySegmentTree<A> seg(n);
for (int i = 0; i < n; i++) {
cin >> a;
seg.set(i, {a, 1});
}
while (q--) {
cin >> com;
if (com == 0) {
cin >> s >> t >> b >> c;
seg.update(s, t, {b, c});
} else {
cin >> s >> t;
cout << seg.fold(s, t).first << '\n';
}
}
}