// competitive-verifier: PROBLEM https://judge.yosupo.jp/problem/dynamic_sequence_range_affine_range_sum
#include "../../../data-structure/lazy-splaytree.hpp"
#include <atcoder/modint>
using mint = atcoder::modint998244353;
struct S {
mint a, sz;
};
static S op(S s, S t) { return S(s.a + t.a, s.sz + t.sz); }
static S e() { return S(0, 0); }
struct F {
mint b, c;
bool operator==(const F &other) const {
return b == other.b && c == other.c;
}
};
static S mapping(F f, S s) { return S(f.b * s.a + f.c * s.sz, s.sz); }
static F composition(F f, F g) {
// composition(f,g)(s) = f(g(s))
return F(f.b * g.b, f.b * g.c + f.c);
}
static F id() { return F(1, 0); }
void solve() {
LL(n, q);
vector<S> v(n);
rep(i, n) {
LL(val);
v[i] = S(val, 1);
}
SplayTree<S, op, e, F, mapping, composition, id> st(v);
rep(t, q) {
LL(flag);
if(flag == 0) {
LL(i, x);
st.insert_at(i, S(x, 1));
} else if(flag == 1) {
LL(i);
st.remove_at(i);
} else if(flag == 2) {
LL(l, r);
st.reverse(l, r);
} else if(flag == 3) {
LL(l, r, b, c);
st.apply(l, r, F(b, c));
} else {
LL(l, r);
print(st.prod(l, r).a.val());
}
}
}
int main() {
ios::sync_with_stdio(false);
std::cin.tie(nullptr);
solve();
}
#line 1 "test/library_checker/data_structure/dynamic_sequence_range_affine_range_sum.test.cpp"
// competitive-verifier: PROBLEM https://judge.yosupo.jp/problem/dynamic_sequence_range_affine_range_sum
#line 2 "other/fastio.hpp"
// ref: https://maspypy.com/library-checker-many-a-b , NyaanуБХуВУ
#line 2 "other/type-utils.hpp"
#include <bits/stdc++.h>
using ll = long long;
using u32 = unsigned int;
using u64 = unsigned long long;
using i128 = __int128;
using u128 = unsigned __int128;
using vi = std::vector<int>;
using vii = std::vector<std::vector<int>>;
using pii = std::pair<int, int>;
using vl = std::vector<ll>;
using vll = std::vector<vl>;
using pll = std::pair<ll, ll>;
template <class T>
concept extended_integral =
std::integral<T> || std::same_as<std::remove_cv_t<T>, i128> ||
std::same_as<std::remove_cv_t<T>, u128>;
template <class T>
concept extended_signed_integral =
std::signed_integral<T> || std::same_as<std::remove_cv_t<T>, i128>;
template <class T>
concept extended_unsigned_integral =
std::unsigned_integral<T> || std::same_as<std::remove_cv_t<T>, u128>;
template <class T>
concept Streamable =
requires(std::ostream &os, T &x) { os << x; } || extended_integral<T>;
template <class mint>
concept is_modint = requires(mint &x) {
{ x.val() } -> std::convertible_to<int>;
};
#line 4 "other/fastio.hpp"
namespace fastio {
constexpr int SZ = 1 << 17;
constexpr int offset = 64;
constexpr int mod = 10000;
char in_buf[SZ];
int in_left{}, in_right{};
char out_buf[SZ];
char out_tmp[offset];
int out_right{};
struct Pre {
char num[4 * mod]{};
constexpr Pre() {
for(int i = 0; i < mod; ++i) {
for(int n = i, j = 3; j >= 0; --j, n /= 10)
num[4 * i + j] = '0' + n % 10;
}
}
constexpr const char *operator[](int i) const { return &num[4 * i]; }
} constexpr pre;
void load() {
memmove(in_buf, in_buf + in_left, in_right - in_left);
in_right += -in_left + std::fread(in_buf + in_right - in_left, 1,
SZ - (in_right - in_left), stdin);
in_left = 0;
if(in_right < SZ)
in_buf[in_right++] = '\n';
}
void read(char &c) {
do {
if(in_left == in_right)
load();
c = in_buf[in_left++];
} while(isspace(c));
}
void read(std::string &s) {
s.clear();
char c;
do {
if(in_left == in_right)
load();
c = in_buf[in_left++];
} while(isspace(c));
do {
s += c;
if(in_left == in_right)
load();
c = in_buf[in_left++];
} while(!isspace(c));
}
template <extended_integral T> void read(T &x) {
if(in_right - in_left < offset)
load();
char c;
do
c = in_buf[in_left++];
while(c < '-'); // \n:10 space:32 -:45 '0':48
bool minus{};
if constexpr(extended_signed_integral<T>) {
if(c == '-') {
c = in_buf[in_left++];
minus = true;
}
}
x = 0;
while(c >= '0') {
x = 10 * x + (c & 15);
c = in_buf[in_left++];
}
if constexpr(extended_signed_integral<T>) {
if(minus)
x = -x;
}
}
void flush() { fwrite(out_buf, 1, std::exchange(out_right, 0), stdout); }
void write_range(const char *c, int n) {
int pos{};
while(pos < n) {
if(out_right == SZ)
flush();
int len = std::min(n - pos, SZ - out_right);
memcpy(out_buf + out_right, c + pos, len);
out_right += len;
pos += len;
}
}
void write(char c) {
if(SZ == out_right)
flush();
out_buf[out_right++] = c;
}
void write(const char *c) { write_range(c, strlen(c)); }
void write(const std::string &s) { write_range(s.data(), s.size()); }
template <std::floating_point T> void write(T x) {
int n = std::snprintf(out_tmp, sizeof(out_tmp), "%.16g", x);
write_range(out_tmp, n);
}
void write(bool x) { write(x ? '1' : '0'); }
template <extended_integral T> void write(T x) {
if(x == 0) {
write('0');
}
if constexpr(extended_signed_integral<T>) {
if(x < 0) {
write('-');
x = -x;
}
}
if(SZ - out_right < offset)
flush();
int cur = offset;
for(; x >= 1000; x /= mod) {
cur -= 4;
memcpy(out_tmp + cur, pre[x % mod], 4);
}
if(x >= 100) {
cur -= 3;
memcpy(out_tmp + cur, pre[x % mod] + 1, 3);
} else if(x >= 10) {
cur -= 2;
memcpy(out_tmp + cur, pre[x % mod] + 2, 2);
} else if(x >= 1) {
cur -= 1;
memcpy(out_tmp + cur, pre[x % mod] + 3, 1);
}
write_range(out_tmp + cur, offset - cur);
}
struct Dummy {
// уГЧуГнуВ░уГйуГач╡Вф║ЖцЩВуБлхЗ║хКЫ
~Dummy() { flush(); }
} dummy;
} // namespace fastio
using fastio::write;
#line 4 "template.hpp"
// #pragma GCC target("avx2")
// #pragma GCC optimize("O3")
// #pragma GCC optimize("unroll-loops")
#line 8 "template.hpp"
using namespace std;
#ifdef LOCAL
#include <debug.hpp>
#else
#define debug(...)
#endif
template <Streamable T> void print_one(const T &value) { fastio::write(value); }
template <is_modint T> void print_one(const T &value) {
print_one(value.val());
}
void print() { print_one('\n'); }
template <class T, class... Ts> void print(const T &a, const Ts &...b) {
print_one(a);
((print_one(' '), print_one(b)), ...);
print();
}
template <ranges::range Iterable>
requires(!Streamable<Iterable>)
void print(const Iterable &v) {
for(auto it = v.begin(); it != v.end(); ++it) {
if(it != v.begin())
print_one(' ');
print_one(*it);
}
print();
}
#define all(v) begin(v), end(v)
template <class T> void UNIQUE(T &v) {
ranges::sort(v);
v.erase(unique(all(v)), end(v));
}
template <typename T> inline bool chmax(T &a, T b) {
return ((a < b) ? (a = b, true) : (false));
}
template <typename T> inline bool chmin(T &a, T b) {
return ((a > b) ? (a = b, true) : (false));
}
// https://trap.jp/post/1224/
template <class... T> constexpr auto min(T... a) {
return min(initializer_list<common_type_t<T...>>{a...});
}
template <class... T> constexpr auto max(T... a) {
return max(initializer_list<common_type_t<T...>>{a...});
}
void input() {}
template <class Head, class... Tail> void input(Head &head, Tail &...tail) {
#ifdef LOCAL
cin >> head;
#else
fastio::read(head);
#endif
input(tail...);
}
template <class T> void input(vector<T> &a) {
for(T &x : a)
input(x);
}
#define INT(...) \
int __VA_ARGS__; \
input(__VA_ARGS__)
#define LL(...) \
long long __VA_ARGS__; \
input(__VA_ARGS__)
#define STR(...) \
string __VA_ARGS__; \
input(__VA_ARGS__)
#define REP1_0(n, c) REP1_1(n, c)
#define REP1_1(n, c) \
for(ll REP_COUNTER_##c = 0; REP_COUNTER_##c < (ll)(n); REP_COUNTER_##c++)
#define REP1(n) REP1_0(n, __COUNTER__)
#define REP2(i, a) for(ll i = 0; i < (ll)(a); i++)
#define REP3(i, a, b) for(ll i = (ll)(a); i < (ll)(b); i++)
#define REP4(i, a, b, c) for(ll i = (ll)(a); i < (ll)(b); i += (ll)(c))
#define overload4(a, b, c, d, e, ...) e
#define rep(...) overload4(__VA_ARGS__, REP4, REP3, REP2, REP1)(__VA_ARGS__)
ll inf = 3e18;
vl dx = {1, -1, 0, 0};
vl dy = {0, 0, 1, -1};
template <class T> constexpr T floor(T x, T y) noexcept {
return x / y - ((x ^ y) < 0 and x % y);
}
template <class T> constexpr T ceil(T x, T y) noexcept {
return x / y + ((x ^ y) >= 0 and x % y);
}
// yуБочмжхП╖уБлщЦвуВПуВЙуБЪщЭЮш▓ауБзхоЪч╛й \bmod:texуВ│уГЮуГ│уГЙ
template <class T> constexpr T bmod(T x, T y) noexcept {
T m = x % y;
return (m < 0) ? m + (y > 0 ? y : -y) : m;
}
template <std::signed_integral T> constexpr int bit_width(T x) noexcept {
return std::bit_width((uint64_t)x);
}
template <std::signed_integral T> constexpr int popcount(T x) noexcept {
return std::popcount((uint64_t)x);
}
constexpr bool kth_bit(auto n, auto k) { return (n >> k) & 1; }
#line 3 "data-structure/lazy-splaytree.hpp"
template <class S, S (*op)(S, S), S (*e)(), class F, S (*mapping)(F, S),
F (*composition)(F, F), F (*id)()>
// composition(f,g)(x) = fтИШg(x) = f(g(x))
struct SplayTree {
private:
struct Node;
using pNode = unique_ptr<Node>;
struct Node {
Node *left, *right, *parent;
int size;
S a, prod;
F lazy;
bool rev;
Node()
: left(nullptr), right(nullptr), parent(nullptr), size(1), a(e()),
prod(e()), lazy(id()), rev(false) {}
Node(const S &s)
: left(nullptr), right(nullptr), parent(nullptr), size(1), a(s),
prod(s), lazy(id()), rev(false) {}
int state() {
if(!this->parent)
return 0;
if(this->parent->left == this)
return 1;
if(this->parent->right == this)
return 2;
return 0;
}
void apply(const F &f) {
a = mapping(f, a);
prod = mapping(f, prod);
lazy = composition(f, lazy);
}
void reverse() {
swap(left, right);
rev = !rev;
}
void push() {
if(lazy != id()) {
if(left)
left->apply(lazy);
if(right)
right->apply(lazy);
lazy = id();
}
if(rev) {
if(left)
left->reverse();
if(right)
right->reverse();
rev = false;
}
}
void update() {
size = 1;
prod = a;
if(left) {
size += left->size;
prod = op(left->prod, prod);
}
if(right) {
size += right->size;
prod = op(prod, right->prod);
}
}
};
void rotate(Node *me) {
Node *pp, *p, *c;
p = me->parent;
pp = p->parent;
if(p->left == me) {
c = me->right;
me->right = p;
p->left = c;
} else {
c = me->left;
me->left = p;
p->right = c;
}
if(pp) {
if(pp->right == p) {
pp->right = me;
} else {
pp->left = me;
}
}
me->parent = pp;
p->parent = me;
if(c) {
c->parent = p;
}
}
void push_from_root(Node *node) {
// ца╣уБЛуВЙуГИуГГуГЧуГАуВжуГ│уБлpush
// https://qiita.com/ngtkana/items/4d0b84d45210771aa074#32-%E3%81%99%E3%81%B9%E3%81%A6%E3%83%88%E3%83%83%E3%83%97%E3%83%80%E3%82%A6%E3%83%B3%E3%83%95%E3%82%A7%E3%83%BC%E3%82%BA%E3%81%AB-push
if(!node)
return;
if(node->parent)
push_from_root(node->parent);
node->push();
}
void splay(Node *me, bool push_from_root_done = false) {
if(push_from_root_done)
me->push();
else
push_from_root(me);
while(me->parent) {
Node *p = me->parent, *pp = p->parent;
if(me->parent->state() == 0) {
rotate(me);
p->update();
break;
} else if(me->state() == me->parent->state()) {
rotate(me->parent), rotate(me);
} else {
rotate(me), rotate(me);
}
pp->update(), p->update();
}
me->update();
}
Node *splay_kth(int k, Node *node) {
assert(0 <= k and k < node->size);
while(1) {
node->push();
int l_size = node->left ? node->left->size : 0;
if(k < l_size) {
node = node->left;
} else if(k == l_size) {
splay(node, true);
return node;
} else {
k -= l_size + 1;
node = node->right;
}
}
}
Node *merge(Node *l_root, Node *r_root) {
if(!l_root)
return r_root;
if(!r_root)
return l_root;
l_root = splay_kth(l_root->size - 1, l_root);
l_root->update();
l_root->right = r_root;
r_root->parent = l_root;
l_root->update();
return l_root;
}
pair<Node *, Node *> split(int l_size, Node *node) {
if(l_size == 0)
return {nullptr, node};
if(l_size == node->size)
return {node, nullptr};
node = splay_kth(l_size, node);
Node *l, *r;
l = node->left, r = node;
r->left = l->parent = nullptr;
r->update();
return {l, r};
}
Node *insert(int k, Node *node, Node *root) {
Node *l, *r;
tie(l, r) = split(k, root);
return merge(merge(l, node), r);
}
pair<Node *, Node *> remove(int k, Node *node) {
node = splay_kth(k, node);
Node *l = node->left, *r = node->right;
if(l)
l->parent = nullptr;
if(r)
r->parent = nullptr;
node->left = node->right = nullptr;
node->update();
return {merge(l, r), node};
}
vector<pNode> pool;
Node *root;
void between(Node *&l_root, Node *&c_root, Node *&r_root, int l, int r) {
// c_rootуВТ[l,r)уБощГихИЖцЬиуБоца╣уБиуБЧуБжsplitуАБl,r_rootуБпх╖жхП│уБоцЬиуБоца╣
// хС╝уБ│хЗ║уБЧуБЯуБВуБиmergeуБЧуБжrootуВТуБНуБбуВУуБицЫ┤цЦ░уБЩуВЛ
tie(c_root, r_root) = split(r, root);
tie(l_root, c_root) = split(l, c_root);
return;
}
public:
void insert_at(int k, const S &s) {
pool.push_back(move(make_unique<Node>(s)));
// тЖСmoveуБДуВЛя╝Я
Node *node = pool.back().get();
root = insert(k, node, root);
}
void remove_at(int k) {
root = remove(k, root).first;
// .secondуБпцФ╛ч╜оуБХуВМуБжуБ╛уБЩуБМ...
}
void set(int k, const S &s) {
root = splay_kth(k, root);
root->a = s;
root->update();
}
int size() { return root ? root->size : 0; }
S get(int k) {
root = splay_kth(k, root);
return root->a;
}
S prod(int l, int r) {
if(l == r)
return e();
Node *l_root, *c_root, *r_root;
between(l_root, c_root, r_root, l, r);
S res = c_root->prod;
root = merge(merge(l_root, c_root), r_root);
return res;
}
void reverse(int l, int r) {
if(l == r)
return;
Node *l_root, *c_root, *r_root;
between(l_root, c_root, r_root, l, r);
c_root->reverse();
root = merge(merge(l_root, c_root), r_root);
}
void apply(int l, int r, F f) {
if(l == r)
return;
Node *l_root, *c_root, *r_root;
between(l_root, c_root, r_root, l, r);
c_root->apply(f);
root = merge(merge(l_root, c_root), r_root);
}
SplayTree() : root(nullptr) {}
SplayTree(const vector<S> &v) : root(nullptr) {
Node *prev = nullptr;
for(const auto &s : v) {
pool.push_back(move(make_unique<Node>(s)));
Node *node = pool.back().get();
if(prev)
prev->parent = node;
node->left = prev;
node->update();
root = prev = node;
}
}
};
#line 3 "test/library_checker/data_structure/dynamic_sequence_range_affine_range_sum.test.cpp"
#include <atcoder/modint>
using mint = atcoder::modint998244353;
struct S {
mint a, sz;
};
static S op(S s, S t) { return S(s.a + t.a, s.sz + t.sz); }
static S e() { return S(0, 0); }
struct F {
mint b, c;
bool operator==(const F &other) const {
return b == other.b && c == other.c;
}
};
static S mapping(F f, S s) { return S(f.b * s.a + f.c * s.sz, s.sz); }
static F composition(F f, F g) {
// composition(f,g)(s) = f(g(s))
return F(f.b * g.b, f.b * g.c + f.c);
}
static F id() { return F(1, 0); }
void solve() {
LL(n, q);
vector<S> v(n);
rep(i, n) {
LL(val);
v[i] = S(val, 1);
}
SplayTree<S, op, e, F, mapping, composition, id> st(v);
rep(t, q) {
LL(flag);
if(flag == 0) {
LL(i, x);
st.insert_at(i, S(x, 1));
} else if(flag == 1) {
LL(i);
st.remove_at(i);
} else if(flag == 2) {
LL(l, r);
st.reverse(l, r);
} else if(flag == 3) {
LL(l, r, b, c);
st.apply(l, r, F(b, c));
} else {
LL(l, r);
print(st.prod(l, r).a.val());
}
}
}
int main() {
ios::sync_with_stdio(false);
std::cin.tie(nullptr);
solve();
}
test/library_checker/data_structure/dynamic_sequence_range_affine_range_sum.test.cpp