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:
import os
import sys

import numpy as np


def solve(inp):
    SEGTREE_TABLES = []
    COMMON_STACK = np.zeros(10 ** 7, dtype=np.int64)
    MOD = 998244353
    DIV2 = 499122177

    def bit_length(n):
        ret = 0
        while n:
            n >>= 1
            ret += 1
        return ret

    def segtree_init(n):
        n2 = 1 << bit_length(n)
        table = np.zeros((n2 << 1, 3), dtype=np.int64)
        table[:, 1] = 1
        SEGTREE_TABLES.append(table)
        return len(SEGTREE_TABLES) - 1

    def segtree_build(ins, arr):
        table = SEGTREE_TABLES[ins]
        offset = table.shape[0] >> 1
        table[offset:offset + len(arr), 0] = arr
        for i in range(offset - 1, 0, -1):
            ch = i << 1
            table[i, 0] = (table[ch, 0] + table[ch + 1, 0]) % MOD

    def segtree_eval(table, offset, i):
        lazy_mul = table[i, 1]
        lazy_add = table[i, 2]
        if lazy_mul == 1 and lazy_add == 0:
            return
        if i < offset:
            ch = i << 1
            ch_add = lazy_add * DIV2 % MOD
            table[ch, 1] = table[ch, 1] * lazy_mul % MOD
            table[ch, 2] = (table[ch, 2] * lazy_mul + ch_add) % MOD
            table[ch + 1, 1] = table[ch + 1, 1] * lazy_mul % MOD
            table[ch + 1, 2] = (table[ch + 1, 2] * lazy_mul + ch_add) % MOD
        table[i, 0] = (table[i, 0] * lazy_mul + lazy_add) % MOD
        table[i, 1] = 1
        table[i, 2] = 0

    def segtree_bottomup(table, i):
        lch = i << 1
        rch = lch + 1
        l_dat = (table[lch, 0] * table[lch, 1] + table[lch, 2]) % MOD
        r_dat = (table[rch, 0] * table[rch, 1] + table[rch, 2]) % MOD
        table[i, 0] = (l_dat + r_dat) % MOD

    def segtree_range_update(ins, l, r, c, d):
        """ i for [l, r),  Ai ← Ai * c + d """
        table = SEGTREE_TABLES[ins]
        offset = table.shape[0] >> 1
        stack = COMMON_STACK
        stack[:5] = (1, 0, offset, c, d * offset % MOD)
        si = 5
        updated = []
        while si:
            i, a, b, mul, add = stack[si - 5:si]
            # print('affin', i, a, b, mul, add)

            segtree_eval(table, offset, i)

            if b <= l or r <= a:
                si -= 5
                continue

            if l <= a and b <= r:
                table[i, 1] = table[i, 1] * mul % MOD
                table[i, 2] = (table[i, 2] * mul + add) % MOD
                si -= 5
                continue

            updated.append(i)

            add = add * DIV2 % MOD
            m = (a + b) // 2
            stack[si - 5:si] = (i << 1, a, m, mul, add)
            stack[si:si + 5] = ((i << 1) + 1, m, b, mul, add)
            si += 5

        # print('update', updated)

        while updated:
            i = updated.pop()
            segtree_bottomup(table, i)

    def segtree_query(ins, l, r):
        """ sum [l, r) """
        table = SEGTREE_TABLES[ins]
        offset = table.shape[0] >> 1
        stack = COMMON_STACK
        stack[:3] = (1, 0, offset)
        si = 3
        res = 0
        updated = []

        while si:
            i, a, b = stack[si - 3:si]
            # print('query', i, a, b)

            segtree_eval(table, offset, i)

            if b <= l or r <= a:
                si -= 3
                continue

            if l <= a and b <= r:
                res = (res + table[i, 0]) % MOD
                si -= 3
                continue

            updated.append(i)

            m = (a + b) // 2
            stack[si - 3:si] = (i << 1, a, m)
            stack[si:si + 3] = ((i << 1) + 1, m, b)
            si += 3

        while updated:
            i = updated.pop()
            segtree_bottomup(table, i)

        return res

    def segtree_debug_print(ins):
        table = SEGTREE_TABLES[ins]
        offset = table.shape[0] >> 1
        for t in range(3):
            i = 1
            while i <= offset:
                print(table[i:2 * i, t])
                i <<= 1

    n = inp[0]
    aaa = inp[2:n + 2]

    ins = segtree_init(n)
    segtree_build(ins, aaa)

    qi = n + 2
    ans = []
    while qi < inp.size:
        t = inp[qi]
        if t == 0:
            # print(*inp[qi:qi + 5])
            l, r, b, c = inp[qi + 1:qi + 5]
            segtree_range_update(ins, l, r, b, c)
            qi += 5
        else:
            # print(*inp[qi:qi + 3])
            ans.append(segtree_query(ins, inp[qi + 1], inp[qi + 2]))
            qi += 3
        # segtree_debug_print(ins)
        # print()

    return ans


if sys.argv[-1] == 'ONLINE_JUDGE':
    from numba.pycc import CC

    cc = CC('my_module')
    cc.export('solve', '(i8[:],)')(solve)
    cc.compile()
    exit()

if os.name == 'posix':
    # noinspection PyUnresolvedReferences
    from my_module import solve
else:
    from numba import njit

    solve = njit('(i8[:],)', cache=True)(solve)
    print('compiled', file=sys.stderr)

inp = np.fromstring(sys.stdin.read(), dtype=np.int64, sep=' ')
ans = solve(inp)
print('\n'.join(map(str, ans)))

Submission status: Accepted

Solution code:
import os
import sys

import numpy as np


def solve(inp):
    SEGTREE_TABLES = []
    COMMON_STACK = np.zeros(10 ** 7, dtype=np.int64)
    MOD = 998244353
    DIV2 = 499122177

    def bit_length(n):
        ret = 0
        while n:
            n >>= 1
            ret += 1
        return ret

    def segtree_init(n):
        n2 = 1 << bit_length(n)
        table = np.zeros((3, n2 << 1), dtype=np.int64)
        table[1] = 1
        SEGTREE_TABLES.append(table)
        return len(SEGTREE_TABLES) - 1

    def segtree_build(ins, arr):
        table = SEGTREE_TABLES[ins]
        offset = table.shape[1] >> 1
        table[0, offset:offset + len(arr)] = arr
        for i in range(offset - 1, 0, -1):
            ch = i << 1
            table[0, i] = (table[0, ch] + table[0, ch + 1]) % MOD

    def segtree_eval(table, offset, i):
        lazy_mul = table[1, i]
        lazy_add = table[2, i]
        if lazy_mul == 1 and lazy_add == 0:
            return
        if i < offset:
            ch = i << 1
            ch_add = lazy_add * DIV2 % MOD
            table[1, ch] = table[1, ch] * lazy_mul % MOD
            table[2, ch] = (table[2, ch] * lazy_mul + ch_add) % MOD
            table[1, ch + 1] = table[1, ch + 1] * lazy_mul % MOD
            table[2, ch + 1] = (table[2, ch + 1] * lazy_mul + ch_add) % MOD
        table[0, i] = (table[0, i] * lazy_mul + lazy_add) % MOD
        table[1, i] = 1
        table[2, i] = 0

    def segtree_bottomup(table, i):
        lch = i << 1
        rch = lch + 1
        l_dat = (table[0, lch] * table[1, lch] + table[2, lch]) % MOD
        r_dat = (table[0, rch] * table[1, rch] + table[2, rch]) % MOD
        table[0, i] = (l_dat + r_dat) % MOD

    def segtree_range_update(ins, l, r, c, d):
        """ i for [l, r),  Ai ← Ai * c + d """
        table = SEGTREE_TABLES[ins]
        offset = table.shape[1] >> 1
        stack = COMMON_STACK
        stack[:5] = (1, 0, offset, c, d * offset % MOD)
        si = 5
        updated = []
        while si:
            i, a, b, mul, add = stack[si - 5:si]
            # print('affin', i, a, b, mul, add)

            segtree_eval(table, offset, i)

            if b <= l or r <= a:
                si -= 5
                continue

            if l <= a and b <= r:
                table[1, i] = table[1, i] * mul % MOD
                table[2, i] = (table[2, i] * mul + add) % MOD
                si -= 5
                continue

            updated.append(i)

            add = add * DIV2 % MOD
            m = (a + b) // 2
            stack[si - 5:si] = (i << 1, a, m, mul, add)
            stack[si:si + 5] = ((i << 1) + 1, m, b, mul, add)
            si += 5

        # print('update', updated)

        while updated:
            i = updated.pop()
            segtree_bottomup(table, i)

    def segtree_query(ins, l, r):
        """ sum [l, r) """
        table = SEGTREE_TABLES[ins]
        offset = table.shape[1] >> 1
        stack = COMMON_STACK
        stack[:3] = (1, 0, offset)
        si = 3
        res = 0
        updated = []

        while si:
            i, a, b = stack[si - 3:si]
            # print('query', i, a, b)

            segtree_eval(table, offset, i)

            if b <= l or r <= a:
                si -= 3
                continue

            if l <= a and b <= r:
                res = (res + table[0, i]) % MOD
                si -= 3
                continue

            updated.append(i)

            m = (a + b) // 2
            stack[si - 3:si] = (i << 1, a, m)
            stack[si:si + 3] = ((i << 1) + 1, m, b)
            si += 3

        while updated:
            i = updated.pop()
            segtree_bottomup(table, i)

        return res

    def segtree_debug_print(ins):
        table = SEGTREE_TABLES[ins]
        offset = table.shape[1] >> 1
        for t in range(3):
            i = 1
            while i <= offset:
                print(table[t, i:2 * i])
                i <<= 1

    n = inp[0]
    aaa = inp[2:n + 2]

    ins = segtree_init(n)
    segtree_build(ins, aaa)

    qi = n + 2
    ans = []
    while qi < inp.size:
        t = inp[qi]
        if t == 0:
            # print(*inp[qi:qi + 5])
            l, r, b, c = inp[qi + 1:qi + 5]
            segtree_range_update(ins, l, r, b, c)
            qi += 5
        else:
            # print(*inp[qi:qi + 3])
            ans.append(segtree_query(ins, inp[qi + 1], inp[qi + 2]))
            qi += 3
        # segtree_debug_print(ins)
        # print()

    return ans


if sys.argv[-1] == 'ONLINE_JUDGE':
    from numba.pycc import CC

    cc = CC('my_module')
    cc.export('solve', '(i8[:],)')(solve)
    cc.compile()
    exit()

if os.name == 'posix':
    # noinspection PyUnresolvedReferences
    from my_module import solve
else:
    from numba import njit

    solve = njit('(i8[:],)', cache=True)(solve)
    print('compiled', file=sys.stderr)

inp = np.fromstring(sys.stdin.read(), dtype=np.int64, sep=' ')
ans = solve(inp)
print('\n'.join(map(str, ans)))

Submission status: Accepted

Solution code:
import os
import sys

import numpy as np


def solve(inp):
    SEGTREE_TABLES = []
    COMMON_STACK = np.zeros(10 ** 7, dtype=np.int64)
    MOD = 998244353
    DIV2 = 499122177

    def bit_length(n):
        ret = 0
        while n:
            n >>= 1
            ret += 1
        return ret

    def segtree_init(n):
        n2 = 1 << bit_length(n)
        table = np.zeros((3, n2 << 1), dtype=np.int64)
        table[1] = 1
        SEGTREE_TABLES.append(table)
        return len(SEGTREE_TABLES) - 1

    def segtree_build(ins, arr):
        table = SEGTREE_TABLES[ins]
        offset = table.shape[1] >> 1
        table[0, offset:offset + len(arr)] = arr
        for i in range(offset - 1, 0, -1):
            ch = i << 1
            table[0, i] = (table[0, ch] + table[0, ch + 1]) % MOD

    def segtree_eval(table, offset, i):
        lazy_mul = table[1, i]
        lazy_add = table[2, i]
        if i < offset:
            ch = i << 1
            ch_add = lazy_add * DIV2 % MOD
            table[1, ch] = table[1, ch] * lazy_mul % MOD
            table[2, ch] = (table[2, ch] * lazy_mul + ch_add) % MOD
            table[1, ch + 1] = table[1, ch + 1] * lazy_mul % MOD
            table[2, ch + 1] = (table[2, ch + 1] * lazy_mul + ch_add) % MOD
        table[0, i] = (table[0, i] * lazy_mul + lazy_add) % MOD
        table[1, i] = 1
        table[2, i] = 0

    def segtree_bottomup(table, i):
        lch = i << 1
        rch = lch + 1
        l_dat = (table[0, lch] * table[1, lch] + table[2, lch]) % MOD
        r_dat = (table[0, rch] * table[1, rch] + table[2, rch]) % MOD
        table[0, i] = (l_dat + r_dat) % MOD

    def segtree_range_update(ins, l, r, c, d):
        """ i for [l, r),  Ai ← Ai * c + d """
        table = SEGTREE_TABLES[ins]
        offset = table.shape[1] >> 1
        stack = COMMON_STACK
        stack[:5] = (1, 0, offset, c, d * offset % MOD)
        si = 5
        updated = []
        while si:
            i, a, b, mul, add = stack[si - 5:si]
            # print('affin', i, a, b, mul, add)

            segtree_eval(table, offset, i)

            if b <= l or r <= a:
                si -= 5
                continue

            if l <= a and b <= r:
                table[1, i] = table[1, i] * mul % MOD
                table[2, i] = (table[2, i] * mul + add) % MOD
                si -= 5
                continue

            updated.append(i)

            add = add * DIV2 % MOD
            m = (a + b) // 2
            stack[si - 5:si] = (i << 1, a, m, mul, add)
            stack[si:si + 5] = ((i << 1) + 1, m, b, mul, add)
            si += 5

        # print('update', updated)

        while updated:
            i = updated.pop()
            segtree_bottomup(table, i)

    def segtree_query(ins, l, r):
        """ sum [l, r) """
        table = SEGTREE_TABLES[ins]
        offset = table.shape[1] >> 1
        stack = COMMON_STACK
        stack[:3] = (1, 0, offset)
        si = 3
        res = 0
        updated = []

        while si:
            i, a, b = stack[si - 3:si]
            # print('query', i, a, b)

            segtree_eval(table, offset, i)

            if b <= l or r <= a:
                si -= 3
                continue

            if l <= a and b <= r:
                res = (res + table[0, i]) % MOD
                si -= 3
                continue

            updated.append(i)

            m = (a + b) // 2
            stack[si - 3:si] = (i << 1, a, m)
            stack[si:si + 3] = ((i << 1) + 1, m, b)
            si += 3

        while updated:
            i = updated.pop()
            segtree_bottomup(table, i)

        return res

    def segtree_debug_print(ins):
        table = SEGTREE_TABLES[ins]
        offset = table.shape[1] >> 1
        for t in range(3):
            i = 1
            while i <= offset:
                print(table[t, i:2 * i])
                i <<= 1

    n = inp[0]
    aaa = inp[2:n + 2]

    ins = segtree_init(n)
    segtree_build(ins, aaa)

    qi = n + 2
    ans = []
    while qi < inp.size:
        t = inp[qi]
        if t == 0:
            # print(*inp[qi:qi + 5])
            l, r, b, c = inp[qi + 1:qi + 5]
            segtree_range_update(ins, l, r, b, c)
            qi += 5
        else:
            # print(*inp[qi:qi + 3])
            ans.append(segtree_query(ins, inp[qi + 1], inp[qi + 2]))
            qi += 3
        # segtree_debug_print(ins)
        # print()

    return ans


if sys.argv[-1] == 'ONLINE_JUDGE':
    from numba.pycc import CC

    cc = CC('my_module')
    cc.export('solve', '(i8[:],)')(solve)
    cc.compile()
    exit()

if os.name == 'posix':
    # noinspection PyUnresolvedReferences
    from my_module import solve
else:
    from numba import njit

    solve = njit('(i8[:],)', cache=True)(solve)
    print('compiled', file=sys.stderr)

inp = np.fromstring(sys.stdin.read(), dtype=np.int64, sep=' ')
ans = solve(inp)
print('\n'.join(map(str, ans)))

Submission status: Accepted

Solution code:
class SegmentTreeLazy():
    def __init__(self, arr, ti, ei, func, op, merge):
        self.h = (len(arr) - 1).bit_length()
        self.n = 2**self.h
        self.func = func
        self.op = op
        self.merge = merge
        self.ti = ti
        self.ei = ei
        self.val = [ti for _ in range(2 * self.n)]
        for i in range(len(arr)):
            self.val[self.n + i] = arr[i]
        for i in range(1, self.n)[::-1]:
            self.val[i] = self.func(self.val[2 * i], self.val[2 * i + 1])
        self.laz = [ei for _ in range(2 * self.n)]

    def reflect(self, k):
        if self.laz[k] == self.ei:
            return self.val[k]
        return self.op(self.val[k], self.laz[k])

    def propagate(self, k):
        if self.laz[k] == self.ei: return
        self.laz[2 * k] = self.merge(self.laz[2 * k], self.laz[k])
        self.laz[2 * k + 1] = self.merge(self.laz[2 * k + 1], self.laz[k])
        self.val[k] = self.reflect(k)
        self.laz[k] = self.ei

    def thrust(self, k):
        for i in range(1, self.h + 1)[::-1]:
            self.propagate(k >> i)

    def recalc(self, k):
        while k:
            k >>= 1
            self.val[k] = self.func(self.reflect(2 * k), self.reflect(2 * k + 1))

    def update(self, lt, rt, x):
        lt += self.n
        rt += self.n
        vl = lt
        vr = rt
        self.thrust(lt)
        self.thrust(rt - 1)
        while rt - lt > 0:
            if lt & 1:
                self.laz[lt] = self.merge(self.laz[lt], x)
                lt += 1
            if rt & 1:
                rt -= 1
                self.laz[rt] = self.merge(self.laz[rt], x)
            lt >>= 1
            rt >>= 1
        self.recalc(vl)
        self.recalc(vr - 1)

    def query(self, lt, rt):
        lt += self.n
        rt += self.n
        self.thrust(lt)
        self.thrust(rt - 1)
        vl = vr = self.ti
        while rt - lt > 0:
            if lt & 1:
                vl = self.func(vl, self.reflect(lt))
                lt += 1
            if rt & 1:
                rt -= 1
                vr = self.func(self.reflect(rt), vr)
            lt >>= 1
            rt >>= 1
        return self.func(vl, vr)

import sys
input = sys.stdin.buffer.readline

MOD = 998244353

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

arr = [a * MOD + 1 for a in map(int, input().split())]
ti = 0
ei = MOD

def func(a, b):
    a1, a2 = divmod(a, MOD)
    b1, b2 = divmod(b, MOD)
    c1 = (a1 + b1) % MOD
    c2 = (a2 + b2) % MOD
    return c1 * MOD + c2

def op(a, x):
    a1, a2 = divmod(a, MOD)
    x1, x2 = divmod(x, MOD)
    c1 = (a1 * x1 + a2 * x2) % MOD
    c2 = a2
    return c1 * MOD + c2

def merge(x, y):
    x1, x2 = divmod(x, MOD)
    y1, y2 = divmod(y, MOD)
    z1 = (x1 * y1) % MOD
    z2 = (x2 * y1 + y2) % MOD
    return z1 * MOD + z2

st = SegmentTreeLazy(arr, ti, ei, func, op, merge)

res = list()

for _ in range(Q):
    q, *p = map(int, input().split())
    if q == 0:
        l, r, b, c = p
        st.update(l, r, (b * MOD + c))
    else:
        l, r = p
        res.append(st.query(l, r) // MOD)

print('\n'.join(map(str, res)))

Submission status: Accepted

Solution code:
# AtCoderのPyPy3環境だとこれが一番速い。

MOD = 998244353
mask32 = (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 replace(self, index, value):
        index += self.n

        # propagation
        for shift in range(index.bit_length()-1, 0, -1):
            i = index >> 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

        # update
        self.data[index] = value
        self.lazy[index] = self.oe

        # recalculation
        i = index
        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 effect(self, l, r, operator):
        l += self.n
        r += self.n
        l0 = l
        r0 = r - 1
        while l0 % 2 == 0:
            l0 //= 2
        while r0 % 2 == 1:
            r0 //= 2

        # propagation
        for shift in range(l0.bit_length()-1, 0, -1):
            i = l0 >> 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
        for shift in range(r0.bit_length()-1, 0, -1):
            i = r0 >> 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

        # effect
        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

        # recalculation
        while l0 > 1:
            l0 //= 2
            self.data[l0] = self.fmm( self.fmo(self.data[2*l0], self.lazy[2*l0]), self.fmo(self.data[2*l0+1], self.lazy[2*l0+1]) )
            self.lazy[l0] = self.oe
        while r0 > 1:
            r0 //= 2
            self.data[r0] = self.fmm( self.fmo(self.data[2*r0], self.lazy[2*r0]), self.fmo(self.data[2*r0+1], self.lazy[2*r0+1]) )
            self.lazy[r0] = self.oe
            
        
    def folded(self, l, r):
        l += self.n
        r += self.n
        l0 = l
        r0 = r - 1
        while l0 % 2 == 0:
            l0 //= 2
        while r0 % 2 == 1:
            r0 //= 2

        # propagation
        for shift in range(l0.bit_length()-1, 0, -1):
            i = l0 >> 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
        for shift in range(r0.bit_length()-1, 0, -1):
            i = r0 >> 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

        # fold
        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)



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

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

    def foo(o1, o2):
        b1 = o1 >> 32
        c1 = o1 & mask32
        b2 = o2 >> 32
        c2 = o2 & mask32
        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__":
    yosupo()

Submission status: Accepted

Solution code:
# AtCoderのPyPy3環境だとこれが一番速い。

MOD = 998244353
mask32 = (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

        assert monoid_data
        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 replace(self, index, value):
        assert 0 <= index < self.n
        index += self.n

        # propagation
        for shift in range(index.bit_length()-1, 0, -1):
            i = index >> 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

        # update
        self.data[index] = value
        self.lazy[index] = self.oe

        # recalculation
        i = index
        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 effect(self, l, r, operator):
        assert 0 <= l < r <= self.n
        l += self.n
        r += self.n
        l0 = l
        r0 = r - 1
        while l0 % 2 == 0:
            l0 //= 2
        while r0 % 2 == 1:
            r0 //= 2

        # propagation
        for shift in range(l0.bit_length()-1, 0, -1):
            i = l0 >> 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
        for shift in range(r0.bit_length()-1, 0, -1):
            i = r0 >> 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

        # effect
        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

        # recalculation
        i = l0
        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
        i = r0
        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 folded(self, l, r):
        assert 0 <= l < r <= self.n
        l += self.n
        r += self.n
        l0 = l
        r0 = r - 1
        while l0 % 2 == 0:
            l0 //= 2
        while r0 % 2 == 1:
            r0 //= 2

        # propagation
        for shift in range(l0.bit_length()-1, 0, -1):
            i = l0 >> 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
        for shift in range(r0.bit_length()-1, 0, -1):
            i = r0 >> 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

        # fold
        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)



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

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

    def foo(o1, o2):
        b1 = o1 >> 32
        c1 = o1 & mask32
        b2 = o2 >> 32
        c2 = o2 & mask32
        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__":
    yosupo()