Problem:


Score : 100 points

Problem Statement

You are given an array a_0, a_1, ..., a_{N-1} of length N. Process Q queries of the following types.

0 l r b c: For each i = l, l+1, \dots, {r - 1}, set a_i \gets b \times a_i + c.

1 l r: Print \sum_{i = l}^{r - 1} a_i \bmod 998244353.

Constraints

1 \leq N, Q \leq 500000

0 \leq a_i, c < 998244353

1 \leq b < 998244353

0 \leq l < r \leq N

All values in Input are integer.

Input

Input is given from Standard Input in the following format:

N Q
a_0 a_1 ... a_{N - 1}
\textrm{Query}_0
\textrm{Query}_1
:
\textrm{Query}_{Q - 1}

Output

For each query of the latter type, print the answer.

Sample Input 1

5 7
1 2 3 4 5
1 0 5
0 2 4 100 101
1 0 3
0 1 3 102 103
1 2 5
0 2 5 104 105
1 0 5

Sample Output 1

15
404
41511
4317767



Sample input:
5 7
1 2 3 4 5
1 0 5
0 2 4 100 101
1 0 3
0 1 3 102 103
1 2 5
0 2 5 104 105
1 0 5


Sample output:
15
404
41511
4317767

Submission status: Accepted

Solution code:
from typing import Callable, List, TypeVar

S = TypeVar("S")  # モノイドの型
F = TypeVar("F")  # 写像の型


class LazySegmentTree:
    """
    Lazy Segment Tree from https://atcoder.jp/contests/practice2/submissions/16775176
    References:
        https://tumoiyorozu.github.io/single-file-ac-library/document_ja/lazysegtree.html
        https://github.com/atcoder/ac-library/blob/master/atcoder/lazysegtree.hpp
    """

    __slots__ = ["e", "op", "id", "mapping", "composition", "_n", "_log", "_size", "tree", "lazy"]

    def __init__(self,
                 a: List[S],
                 e: S,
                 op: Callable[[S, S], S],
                 id_: F,
                 mapping: Callable[[F, S], S],
                 composition: Callable[[F, F], F]) -> None:
        self.e = e
        self.op = op
        self.id = id_
        self.mapping = mapping
        self.composition = composition

        self._n = len(a)
        self._log = (self._n - 1).bit_length()
        self._size = 1 << self._log

        self.tree = [e] * self._size + a + [e] * (self._size - self._n)
        for i in range(self._size - 1, 0, -1):
            self._update(i)

        self.lazy = [id_] * self._size

    def _update(self, k: int) -> None:
        """Update the value of a[k]."""
        self.tree[k] = self.op(self.tree[2 * k], self.tree[2 * k + 1])

    def _apply_all(self, k: int, f: F) -> None:
        self.tree[k] = self.mapping(f, self.tree[k])
        if k < self._size:
            self.lazy[k] = self.composition(f, self.lazy[k])

    def _push(self, k: int) -> None:
        self._apply_all(2 * k, self.lazy[k])
        self._apply_all(2 * k + 1, self.lazy[k])
        self.lazy[k] = self.id

    def set(self, k: int, x: S) -> None:
        """Assign x to a[k] in O(log n)."""
        assert 0 <= k < self._n

        k += self._size
        for i in range(self._log, 0, -1):
            self._push(k >> i)
        self.tree[k] = x
        for i in range(1, self._log + 1):
            self._update(k >> i)

    def get(self, k: int) -> S:
        """Return a[k] in O(1)."""
        assert 0 <= k < self._n

        k += self._size
        for i in range(self._log, 0, -1):
            self._push(k >> i)
        return self.tree[k]

    def prod(self, l: int, r: int) -> S:
        """Return op(a[l], ..., a[r - 1]). Return e, if l == r.
        Complexity: O(log n)
        """
        assert 0 <= l <= r <= self._n

        if l == r:
            return self.e

        l += self._size
        r += self._size
        for i in range(self._log, 0, -1):
            if ((l >> i) << i) != l:
                self._push(l >> i)
            if ((r >> i) << i) != r:
                self._push(r >> i)

        sml, smr = self.e, self.e
        while l < r:
            if l & 1:
                sml = self.op(sml, self.tree[l])
                l += 1
            if r & 1:
                r -= 1
                smr = self.op(self.tree[r], smr)
            l >>= 1
            r >>= 1
        return self.op(sml, smr)

    def prod_all(self) -> S:
        """Return op(a[0], ..., a[n - 1]. Return e if n == 0.
        Complexity: O(1)
        """
        return self.tree[1]

    def apply(self, k: int, f: F) -> None:
        """Apply a[p] = op_st(a[p], x) in O(log n)."""
        assert 0 <= k < self._n

        k += self._size
        for i in range(self._log, 0, -1):
            self._push(k >> i)
        self.tree[k] = self.mapping(f, self.tree[k])
        for i in range(1, self._log + 1):
            self._update(k >> i)

    def apply_range(self, l: int, r: int, f: F) -> None:
        """Apply a[i] = op_st(a[i], x) for all i = l..r-1 in O(log n)."""
        assert 0 <= l <= r <= self._n

        if l == r:
            return

        l += self._size
        r += self._size
        for i in range(self._log, 0, -1):
            if ((l >> i) << i) != l:
                self._push(l >> i)
            if ((r >> i) << i) != r:
                self._push((r - 1) >> i)

        l_tmp, r_tmp = l, r
        while l < r:
            if l & 1:
                self._apply_all(l, f)
                l += 1
            if r & 1:
                r -= 1
                self._apply_all(r, f)
            l >>= 1
            r >>= 1
        l, r = l_tmp, r_tmp

        for i in range(1, self._log + 1):
            if ((l >> i) << i) != l:
                self._update(l >> i)
            if ((r >> i) << i) != r:
                self._update((r - 1) >> i)


mod = 998244353


def op(l, r):
    l1, l2 = l >> 32, l % (1 << 32)
    r1, r2 = r >> 32, r % (1 << 32)
    return (((l1 + r1) % mod) << 32) + l2 + r2


def mapping(f, x):
    f1, f2 = f >> 32, f % (1 << 32)
    x1, x2 = x >> 32, x % (1 << 32)
    return (((f1 * x1 + f2 * x2) % mod) << 32) + x2


def composition(l, r):
    l1, l2 = l >> 32, l % (1 << 32)
    r1, r2 = r >> 32, r % (1 << 32)
    return (((l1 * r1) % mod) << 32) + ((r2 * l1 + l2) % mod)


N, Q = map(int, input().split())
a = list(map(int, input().split()))

lst = LazySegmentTree([(v << 32) + 1 for v in a], 0, op, 1 << 32, mapping, composition)

for i in range(Q):
    q, *p = map(int, input().split())
    if q == 0:
        lst.apply_range(p[0], p[1], (p[2] << 32) + p[3])
    else:
        print(lst.prod(*p) >> 32)

Submission status: Accepted

Solution code:
header_code = """













#include "/opt/atcoder-stl/atcoder/internal_bit.hpp"
#include "/opt/atcoder-stl/atcoder/lazysegtree.hpp"
#include "/opt/atcoder-stl/atcoder/modint.hpp"
#include <vector>
#include <algorithm>
#include <cassert>

namespace aclython {

template <class S, S (*op)(S, S), S (*e)()> struct segtree {
  public:
    segtree() : segtree(0) {}
    segtree(int n) : segtree(std::vector<S>(n, e())) {}
    segtree(const std::vector<S>& v) : _n(int(v.size())) {
        log = atcoder::internal::ceil_pow2(_n);
        size = 1 << log;
        d = std::vector<S>(2 * size, e());
        for (int i = 0; i < _n; i++) d[size + i] = v[i];
        for (int i = size - 1; i >= 1; i--) {
            update(i);
        }
    }

    void set(int p, S x) {
        assert(0 <= p && p < _n);
        p += size;
        d[p] = x;
        for (int i = 1; i <= log; i++) update(p >> i);
    }

    S get(int p) {
        assert(0 <= p && p < _n);
        return d[p + size];
    }

    S prod(int l, int r) {
        assert(0 <= l && l <= r && r <= _n);
        S sml = e(), smr = e();
        l += size;
        r += size;

        while (l < r) {
            if (l & 1) sml = op(sml, d[l++]);
            if (r & 1) smr = op(d[--r], smr);
            l >>= 1;
            r >>= 1;
        }
        return op(sml, smr);
    }

    S all_prod() { return d[1]; }

    template <bool (*f)(S)> int max_right(int l, S b) {
        return max_right(l, b, [](S x, S y) { return f(x, y); });
    }
    template <class F> int max_right(int l, S b, F f) {
        assert(0 <= l && l <= _n);
        assert(f(e()));
        if (l == _n) return _n;
        l += size;
        S sm = e();
        do {
            while (l % 2 == 0) l >>= 1;
            if (!f(op(sm, d[l]), b)) {
                while (l < size) {
                    l = (2 * l);
                    if (f(op(sm, d[l]), b)) {
                        sm = op(sm, d[l]);
                        l++;
                    }
                }
                return l - size;
            }
            sm = op(sm, d[l]);
            l++;
        } while ((l & -l) != l);
        return _n;
    }

    template <bool (*f)(S)> int min_left(int r, S b) {
        return min_left(r, b, [](S x, S y) { return f(x, y); });
    }
    template <class F> int min_left(int r, S b, F f) {
        assert(0 <= r && r <= _n);
        assert(f(e()));
        if (r == 0) return 0;
        r += size;
        S sm = e();
        do {
            r--;
            while (r > 1 && (r % 2)) r >>= 1;
            if (!f(op(d[r], sm), b)) {
                while (r < size) {
                    r = (2 * r + 1);
                    if (f(op(d[r], sm), b)) {
                        sm = op(d[r], sm);
                        r--;
                    }
                }
                return r + 1 - size;
            }
            sm = op(d[r], sm);
        } while ((r & -r) != r);
        return 0;
    }

  private:
    int _n, size, log;
    std::vector<S> d;

    void update(int k) { d[k] = op(d[2 * k], d[2 * k + 1]); }
};



int min_op(int n, int m){
    return std::min(n, m);
}

int min_e(){
    return (int)1e9;
}

struct segtree_min {
    public:
        segtree_min() : segtree_min(0) {}
        segtree_min(int n) : segtree_min(std::vector<int>(n, min_e())) {}
        segtree_min(const std::vector<int>& vec) : seg(vec) {}

        void set(int p, int x) {seg.set(p, x);}
        int get(int p) {return seg.get(p);}
        int prod(int l, int r) {return seg.prod(l, r);}
        int all_prod() {return seg.all_prod();}

        int max_right(int l, int v) {return seg.max_right(l, v, [](int x, int y) { return x<y; });}
        int min_left(int r, int v) {return seg.min_left(r, v, [](int x, int y) { return x<y; });}

    private:
        segtree<int, min_op, min_e> seg;
};

int max_op(int n, int m){
    return std::max(n, m);
}

int max_e(){
    return 0;
}

struct segtree_max {
    public:
        segtree_max() : segtree_max(0) {}
        segtree_max(int n) : segtree_max(std::vector<int>(n, max_e())) {}
        segtree_max(const std::vector<int>& vec) : seg(vec) {}

        void set(int p, int x) {seg.set(p, x);}
        int get(int p) {return seg.get(p);}
        int prod(int l, int r) {return seg.prod(l, r);}
        int all_prod() {return seg.all_prod();}

        int max_right(int l, int v) {return seg.max_right(l, v, [](int x, int y) { return x<y; });}
        int min_left(int r, int v) {return seg.min_left(r, v, [](int x, int y) { return x<y; });}

    private:
        segtree<int, max_op, max_e> seg;
};

using mint = atcoder::modint998244353;

struct S {
    mint a;
    int size;
    S(mint _a, int _size) : a(_a) ,size(_size) {}
    S(int _a, int _size) : a(_a) ,size(_size) {}
    S(const S &s) : a(s.a), size(s.size) {}
    int get_a() { return (int)a.val(); }
};

struct F {
    mint a, b;
    F(mint _a, mint _b) : a(_a), b(_b) {}
    F(int _a, int _b) : a(_a), b(_b) {}
    F(const F &f) : a(f.a), b(f.b) {}
    int get_a() { return (int)a.val(); }
    int get_b() { return (int)b.val(); }
};

S op(S l, S r) { return S{l.a + r.a, l.size + r.size}; }

S e() { return S{0, 0}; }

S mapping(F l, S r) { return S{r.a * l.a + r.size * l.b, r.size}; }

F composition(F l, F r) { return F{r.a * l.a, r.b * l.a + l.b}; }

F id() { return F{1, 0}; }

struct lazy_segtree{
    lazy_segtree() : lazy_segtree(0) {}
    lazy_segtree(int n) : lazy_segtree(std::vector<S>(n, e())) {}
    lazy_segtree(const std::vector<S>& vec) : seg(vec) {}
    void set(int p, S x) { seg.set(p, x); }
    S get(int p) { return seg.get(p); }
    S prod(int l, int r) { return seg.prod(l, r); }
    S all_prod() { return seg.all_prod(); }
    void apply(int p, F f) { seg.apply(p, f); }
    void apply(int l, int r, F f) { seg.apply(l, r, f); }
    private:
        atcoder::lazy_segtree<S, op, e, F, mapping, composition, id> seg;
};

}
"""

code = """

# distutils: language=c++
# distutils: include_dirs=[/home/USERNAME/.local/lib/python3.8/site-packages/numpy/core/include, /opt/atcoder-stl]
# cython: boundscheck=False
# cython: wraparound=False

from libcpp cimport bool
from libcpp.string cimport string
from libcpp.vector cimport vector
from libc.stdio cimport getchar, printf
cpdef inline vector[int] ReadInt(int n):
    cdef int b, c
    cdef vector[int] *v = new vector[int]()
    for i in range(n):
        c = 0
        while 1:
            b = getchar() - 48
            if b < 0: break
            c = c * 10 + b
        v.push_back(c)
    return v[0]

cpdef inline vector[string] Read(int n):
    cdef char c
    cdef vector[string] *vs = new vector[string]()
    cdef string *s
    for i in range(n):
        s = new string()
        while 1:
            c = getchar()
            if c<=32: break
            s.push_back(c)
        vs.push_back(s[0])
    return vs[0]

cpdef inline void PrintLongN(vector[long] l, int n):
    for i in range(n): printf("%ld\\n", l[i])

cpdef inline void PrintLong(vector[long] l, int n):
    for i in range(n): printf("%ld ", l[i])
cdef extern from "./intermediate.hpp" namespace "aclython" nogil:
    cdef cppclass segtree_min:
        segtree_min(vector[int] v)
        void set(int p, int x)
        int get(int p)
        int prod(int l, int r)
        int all_prod()
        int max_right(int l, int v)
        int min_left(int r, int v)

cdef class SegTreeMin:
    cdef segtree_min *_thisptr
    def __cinit__(self, vector[int] v):
        self._thisptr = new segtree_min(v)
    cpdef void set(self, int p, int x):
        self._thisptr.set(p, x)
    cpdef int get(self, int p):
        return self._thisptr.get(p)
    cpdef int prod(self, int l, int r):
        return self._thisptr.prod(l, r)
    cpdef int all_prod(self):
        return self._thisptr.all_prod()
    cpdef int max_right(self, int l, int v):
        return self._thisptr.max_right(l, v)
    cpdef int min_left(self, int r, int v):
        self._thisptr.min_left(r, v)

cdef extern from "./intermediate.hpp" namespace "aclython" nogil:
    cdef cppclass segtree_max:
        segtree_max(vector[int] v)
        void set(int p, int x)
        int get(int p)
        int prod(int l, int r)
        int all_prod()
        int max_right(int l, int v)
        int min_left(int r, int v)

cdef class SegTreeMax:
    cdef segtree_max *_thisptr
    def __cinit__(self, vector[int] v):
        self._thisptr = new segtree_max(v)
    cpdef void set(self, int p, int x):
        self._thisptr.set(p, x)
    cpdef int get(self, int p):
        return self._thisptr.get(p)
    cpdef int prod(self, int l, int r):
        return self._thisptr.prod(l, r)
    cpdef int all_prod(self):
        return self._thisptr.all_prod()
    cpdef int max_right(self, int l, int v):
        return self._thisptr.max_right(l, v)
    cpdef int min_left(self, int r, int v):
        self._thisptr.min_left(r, v)


def SegTree(v, op):
    if op=="min":
        return SegTreeMin(v)
    elif op=="max":
        return SegTreeMax(v)

cdef extern from *:
    ctypedef long long ll "long long"

cdef extern from "./intermediate.hpp" namespace "aclython" nogil:
    cdef cppclass S:
        S(int, int)
        S(S &)
        int get_a()
        int size
    cdef cppclass F:
        F(int, int)
        F(F &)
        int get_a()
        int get_b()
    cdef cppclass lazy_segtree:
        lazy_segtree(vector[S] v)
        void set(int p, S x)
        S get(int p)
        S prod(int l, int r)
        S all_prod()
        void apply(int p, F f)
        void apply(int l, int r, F f)

cdef class LazySegTree:
    cdef lazy_segtree *_thisptr
    def __cinit__(self, vector[vector[int]] v):
        cdef int n = v.size()
        cdef vector[S] *sv = new vector[S]()
        cdef S *s
        for i in range(n):
            s = new S(v.at(i).at(0), v.at(i).at(1))
            sv.push_back(s[0])
        self._thisptr = new lazy_segtree(sv[0])
    cpdef void set(self, int p, vector[int] v):
        cdef S *s = new S(v.at(0), v.at(1))
        self._thisptr.set(p, s[0])
    cpdef vector[int] get(self, int p):
        cdef S *s = new S(self._thisptr.get(p))
        cdef vector[int] *v = new vector[int]()
        v.push_back(s.get_a())
        v.push_back(s.size)
        return v[0]
    cpdef vector[int] prod(self, int l, int r):
        cdef S *s = new S(self._thisptr.prod(l, r))
        cdef vector[int] *v = new vector[int]()
        v.push_back(s.get_a())
        v.push_back(s.size)
        return v[0]
    cpdef vector[int] all_prod(self):
        cdef S *s = new S(self._thisptr.all_prod())
        cdef vector[int] *v = new vector[int]()
        v.push_back(s.get_a())
        v.push_back(s.size)
        return v[0]
    cpdef void apply(self, int p, vector[int] v):
        cdef F *f = new F(v.at(0), v.at(1))
        self._thisptr.apply(p, f[0])
    cpdef void apply_range(self, int l, int r, vector[int] v):
        cdef F *f = new F(v.at(0), v.at(1))
        self._thisptr.apply(l, r, f[0])
"""


import os, sys, getpass

if sys.argv[-1] == 'ONLINE_JUDGE':
    code = code.replace("USERNAME", getpass.getuser())
    open('intermediate.hpp','w').write(header_code)
    open('atcoder.pyx','w').write(code)
    os.system('cythonize -i -3 -b atcoder.pyx')
    sys.exit(0)


from atcoder import ReadInt, LazySegTree, PrintLongN

def main():
    N,Q = ReadInt(2)

    A = ReadInt(N)
    ans = []
    AS = [[a,1] for a in A]
    ST = LazySegTree(AS)
    for i in range(Q):
        t = ReadInt(1)[0]
        if t==0:
            l,r,c,d = ReadInt(4)
            ST.apply_range(l,r,[c,d])
        else:
            l,r = ReadInt(2)
            ans.append(ST.prod(l,r)[0])
    PrintLongN(ans,len(ans))


if __name__=="__main__":
    main()

Submission status: Accepted

Solution code:
mod = 998244353


class lazy_segtree(object):

    def __init__(self, n_or_vec):
        if isinstance(n_or_vec, int):
            self.n = n_or_vec
            v = [self.e()] * n_or_vec
        elif isinstance(n_or_vec, list) or isinstance(n_or_vec, tuple):
            self.n = len(n_or_vec)
            v = n_or_vec
        self.log = (self.n - 1).bit_length()
        self.size = 1 << self.log
        self.d = [self.e()] * (2 * self.size)
        self.lz = [self.identity()] * self.size
        for i, vi in enumerate(v):
            self.d[self.size + i] = vi
        for i in reversed(range(1, self.size)):
            self.update(i)

    def update(self, k):
        self.d[k] = self.op(self.d[2*k], self.d[2*k+1])

    def all_apply(self, k, f):
        self.d[k] = self.mapping(f, self.d[k])
        if k < self.size:
            self.lz[k] = self.composition(f, self.lz[k])

    def push(self, k):
        self.all_apply(2*k, self.lz[k])
        self.all_apply(2*k+1, self.lz[k])
        self.lz[k] = self.identity()

    def set_x(self, p, x):
        p += self.size
        for i in reversed(range(1, self.log + 1)):
            self.push(p >> i)
        self.d[p] = x
        for i in range(1, self.log + 1):
            self.update(p >> i)

    def get(self, p):
        p += self.size
        for i in reversed(range(1, self.log + 1)):
            self.push(p >> i)
        return self.d[p]

    def show(self):
        print("show array")
        for i in range(self.n):
            print(self.get(i), end=" ")
        print("\n")

    def prod(self, l, r):
        if l == r:
            return self.e()
        l += self.size
        r += self.size
        for i in reversed(range(1, self.log + 1)):
            if ((l >> i) << i) != l:
                self.push(l >> i)
            if ((r >> i) << i) != r:
                self.push(r >> i)
        sml = self.e()
        smr = self.e()
        while l < r:
            if l & 1:
                sml = self.op(sml, self.d[l])
                l += 1
            if r & 1:
                r -= 1
                smr = self.op(self.d[r], smr)
            l >>= 1
            r >>= 1
        return self.op(sml, smr)

    def all_prod(self):
        return self.d[1]

    def apply(self, p, f):
        p += self.size
        for i in reversed(range(1, self.log + 1)):
            self.push(p >> i)
        self.d[p] = self.mapping(f, self.d[p])
        for i in range(1, self.log + 1):
            self.update(p >> i)

    def range_apply(self, l, r, f):
        if l == r:
            return
        l += self.size
        r += self.size
        for i in reversed(range(1, self.log + 1)):
            if ((l >> i) << i) != l:
                self.push(l >> i)
            if ((r >> i) << i) != r:
                self.push((r - 1) >> i)

        l2, r2 = l, r
        while l < r:
            if l & 1:
                self.all_apply(l, f)
                l += 1
            if r & 1:
                r -= 1
                self.all_apply(r, f)
            l >>= 1
            r >>= 1
        l, r = l2, r2

        for i in range(1, self.log + 1):
            if ((l >> i) << i) != l:
                self.update(l >> i)
            if ((r >> i) << i) != r:
                self.update((r - 1) >> i)

    def max_right(self, l, g, target):
        if l == self.n:
            return self.n
        l += self.size
        for i in reversed(range(1, self.log + 1)):
            self.push(l >> i)
        sm = self.e()
        while True:
            while l % 2 == 0:
                l >>= 1
            if not g(self.op(sm, self.d[l]), target):
                while l < self.size:
                    self.push(l)
                    l = (2 * l)
                    if g(self.op(sm, self.d[l]), target):
                        sm = self.op(sm, self.d[l])
                        l += 1
                return l - self.size
            sm = self.op(sm, self.d[l])
            l += 1
            if l & -l == l:
                break
        return self.n

    def min_left(self, r, g, target):
        if r == 0:
            return 0
        r += self.size
        for i in reversed(range(1, self.log + 1)):
            self.push((r - 1) >> i)
        sm = self.e()
        while True:
            r -= 1
            while r > 1 and (r % 2):
                r >>= 1
            if not g(self.op(self.d[r], sm), target):
                while r < self.size:
                    self.push(r)
                    r = (2 * r + 1)
                    if g(self.op(self.d[r], sm), target):
                        sm = self.op(self.d[r], sm)
                        r -= 1
                return r + 1 - self.size
            sm = self.op(self.d[r], sm)
            if r & -r == r:
                break
        return 0

    def op(self, L, R):
        La, Lsize = L
        Ra, Rsize = R
        return (La + Ra) % mod, Lsize + Rsize

    def e(self):
        return (0, 0)

    def identity(self):
        return (1, 0)

    def mapping(self, L, R):
        La, Lb = L
        Ra, Rsize = R
        return (La * Ra + Lb * Rsize) % mod, Rsize

    def composition(self, L, R):
        La, Lb = L
        Ra, Rb = R
        return (La * Ra) % mod, (Rb * La + Lb) % mod


if __name__ == "__main__":
    import sys
    input = sys.stdin.buffer.readline
    sys.setrecursionlimit(10 ** 7)

    N, Q = map(int, input().split())
    A = [(a, 1) for a in map(int, input().split())]

    lazyseg = lazy_segtree(A)
    #lazyseg = lazy_segtree(A, op, e, mapping, composition, identity)

    for _ in range(Q):
        t, *arg = map(int, input().split())
        if t == 0:
            l, r, c, d = arg
            lazyseg.range_apply(l, r, (c, d))
        else:
            l, r = arg
            print(lazyseg.prod(l, r)[0])

Submission status: Accepted

Solution code:
# オリジナル。読みやすいはず。


MOD = 998244353
mask = (1 << 32) - 1


class LazySegmentTree:

    __slots__ = ["n", "data", "lazy", "me", "oe", "fmm", "fmo", "foo"]

    def __init__(self, monoid_data, monoid_identity, operator_identity, func_monoid_monoid, func_monoid_operator, func_operator_operator):
        self.me = monoid_identity
        self.oe = operator_identity
        self.fmm = func_monoid_monoid
        self.fmo = func_monoid_operator
        self.foo = func_operator_operator

        self.n = len(monoid_data)
        self.data = monoid_data * 2
        for i in range(self.n-1, 0, -1):
            self.data[i] = self.fmm(self.data[2*i], self.data[2*i+1])
        self.lazy = [self.oe] * (self.n * 2)


    def _propagate(self, index_of_tree):
        for shift in range(index_of_tree.bit_length()-1, 0, -1):
            i = index_of_tree >> shift
            self.lazy[2*i]   = self.foo(self.lazy[2*i],   self.lazy[i])
            self.lazy[2*i+1] = self.foo(self.lazy[2*i+1], self.lazy[i])
            self.data[i] = self.fmo(self.data[i], self.lazy[i])
            self.lazy[i] = self.oe


    def _recalc(self, i):
        while i > 1:
            i //= 2
            self.data[i] = self.fmm( self.fmo(self.data[2*i], self.lazy[2*i]), self.fmo(self.data[2*i+1], self.lazy[2*i+1]) )
            self.lazy[i] = self.oe


    def replace(self, index, value):
        index += self.n
        self._propagate(index)
        self.data[index] = value
        self.lazy[index] = self.oe
        self._recalc(index)


    def effect(self, l, r, operator):
        l += self.n
        r += self.n
        l0 = l // (l & -l)
        r0 = r // (r & -r) - 1
        self._propagate(l0)
        self._propagate(r0)
        while l < r:
            if l % 2:
                self.lazy[l] = self.foo(self.lazy[l], operator)
                l += 1
            if r % 2:
                r -= 1
                self.lazy[r] = self.foo(self.lazy[r], operator)
            l //= 2
            r //= 2
        self._recalc(l0)
        self._recalc(r0)
        
        
    def folded(self, l, r):
        l += self.n
        r += self.n
        self._propagate(l // (l & -l))
        self._propagate(r // (r & -r) - 1)
        left_folded = self.me
        right_folded = self.me
        while l < r:
            if l % 2:
                left_folded = self.fmm(left_folded, self.fmo(self.data[l], self.lazy[l]))
                l += 1
            if r % 2:
                r -= 1
                right_folded = self.fmm(self.fmo(self.data[r], self.lazy[r]), right_folded)
            l //= 2
            r //= 2
        return self.fmm(left_folded, right_folded)


# Monoid は (値 << 32) + 要素数 にする。
# Operator も (b << 32) + c
def main():
    import sys
    input = sys.stdin.buffer.readline

    def fmm(m1, m2):
        m = m1 + m2
        return (((m >> 32) % MOD) << 32) + (m & mask)
    
    def fmo(m1, o1):
        val = m1 >> 32
        cnt = m1 & mask
        b = o1 >> 32
        c = o1 & mask
        return (((b * val + c * cnt) % MOD) << 32) + cnt

    def foo(o1, o2):
        b1 = o1 >> 32
        c1 = o1 & mask
        b2 = o2 >> 32
        c2 = o2 & mask
        b = b1 * b2 % MOD
        c = (c1 * b2 + c2) % MOD
        return (b << 32) + c

    N, Q = map(int, input().split())
    monoid_data = [(A << 32) + 1 for A in map(int, input().split())]
    lst = LazySegmentTree(monoid_data, 1, 1 << 32, fmm, fmo, foo)
    for _ in range(Q):
        q, *k = map(int, input().split())
        if q == 0:
            o = (k[2] << 32) + k[3]
            lst.effect(k[0], k[1], o)
        else:
            print(lst.folded(k[0], k[1]) >> 32)
            

if __name__ == "__main__":
    main()