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: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**6)
INF = 10 ** 9 + 1  # sys.maxsize # float("inf")
MOD = 998244353


def set_depth(depth):
    global DEPTH, SEGTREE_SIZE, NONLEAF_SIZE
    DEPTH = depth
    SEGTREE_SIZE = 1 << DEPTH
    NONLEAF_SIZE = 1 << (DEPTH - 1)


def set_width(width):
    set_depth((width - 1).bit_length() + 1)


def get_size(pos):
    ret = pos.bit_length()
    return (1 << (DEPTH - ret))


def up(pos):
    pos += SEGTREE_SIZE // 2
    return pos // (pos & -pos)


def up_propagate(table, pos, binop):
    while pos > 1:
        pos >>= 1
        table[pos] = binop(
            table[pos * 2],
            table[pos * 2 + 1]
        )


def full_up(table, binop):
    for i in range(NONLEAF_SIZE - 1, 0, -1):
        table[i] = binop(
            table[2 * i],
            table[2 * i + 1])


def force_down_propagate(
    action_table, value_table, pos,
    action_composite, action_force, action_unity
):
    max_level = pos.bit_length() - 1
    size = NONLEAF_SIZE
    for level in range(max_level):
        size //= 2
        i = pos >> (max_level - level)
        action = action_table[i]
        if action != action_unity:
            # action_table[i * 2] = action_composite(
            #     action, action_table[i * 2])
            # action_table[i * 2 + 1] = action_composite(
            #     action, action_table[i * 2 + 1])
            old_action = action_table[i * 2]
            if old_action == action_unity:
                action_table[i * 2] = action
            else:
                b1, c1 = old_action
                b2, c2 = action
                action_table[i * 2] = (b1 * b2, b2 * c1 + c2)

            old_action = action_table[i * 2 + 1]
            if old_action == action_unity:
                action_table[i * 2 + 1] = action
            else:
                b1, c1 = old_action
                b2, c2 = action
                action_table[i * 2 + 1] = (b1 * b2, b2 * c1 + c2)

            action_table[i] = action_unity
            # value_table[i * 2] = action_force(
            #     action, value_table[i * 2], size)
            # value_table[i * 2 + 1] = action_force(
            #     action, value_table[i * 2 + 1], size)
            b, c = action
            value = value_table[i * 2]
            value_table[i * 2] = (value * b + c * size) % MOD
            value = value_table[i * 2 + 1]
            value_table[i * 2 + 1] = (value * b + c * size) % MOD


def force_range_update(
    value_table, action_table, left, right,
    action, action_force, action_composite, action_unity
):
    """
    action_force: action, value, cell_size => new_value
    action_composite: new_action, old_action => composite_action
    """
    left += NONLEAF_SIZE
    right += NONLEAF_SIZE
    while left < right:
        if left & 1:
            value_table[left] = action_force(
                action, value_table[left], get_size(left))
            action_table[left] = action_composite(action, action_table[left])
            left += 1
        if right & 1:
            right -= 1
            value_table[right] = action_force(
                action, value_table[right], get_size(right))
            action_table[right] = action_composite(action, action_table[right])

        left //= 2
        right //= 2


def range_reduce(table, left, right, binop, unity):
    ret_left = unity
    ret_right = unity
    left += NONLEAF_SIZE
    right += NONLEAF_SIZE
    while left < right:
        if left & 1:
            ret_left = binop(ret_left, table[left])
            left += 1
        if right & 1:
            right -= 1
            ret_right = binop(table[right], ret_right)

        left //= 2
        right //= 2
    return binop(ret_left, ret_right)


def lazy_range_update(
        action_table, value_table, start, end,
        action, action_composite, action_force, action_unity, value_binop):
    "update [start, end)"
    L = up(start)
    R = up(end)
    force_down_propagate(
        action_table, value_table, L,
        action_composite, action_force, action_unity)
    force_down_propagate(
        action_table, value_table, R,
        action_composite, action_force, action_unity)

    # print("action", file=sys.stderr)
    # debugprint(action_table)
    # print("value", file=sys.stderr)
    # debugprint(value_table)
    # print(file=sys.stderr)

    force_range_update(
        value_table, action_table, start, end,
        action, action_force, action_composite, action_unity)
    up_propagate(value_table, L, value_binop)
    up_propagate(value_table, R, value_binop)


def lazy_range_reduce(
    action_table, value_table, start, end,
    action_composite, action_force, action_unity,
    value_binop, value_unity
):
    "reduce [start, end)"
    force_down_propagate(
        action_table, value_table, up(start),
        action_composite, action_force,  action_unity)
    force_down_propagate(
        action_table, value_table, up(end),
        action_composite, action_force, action_unity)

    return range_reduce(value_table, start, end, value_binop, value_unity)


def debug(*x):
    print(*x, file=sys.stderr)


def main():
    # parse input
    N, Q = map(int, input().split())
    AS = list(map(int, input().split()))
    set_width(N + 1)  # include N

    value_unity = 0
    value_table = [value_unity] * SEGTREE_SIZE
    value_table[NONLEAF_SIZE:NONLEAF_SIZE + len(AS)] = AS

    action_unity = None
    action_table = [action_unity] * SEGTREE_SIZE

    def action_force(action, value, size):
        if action == action_unity:
            return value
        b, c = action
        return (value * b + c * size) % MOD

    def action_composite(new_action, old_action):
        if new_action == action_unity:
            return old_action
        if old_action == action_unity:
            return new_action
        b1, c1 = old_action
        b2, c2 = new_action
        return (b1 * b2, b2 * c1 + c2)

    def value_binop(a, b):
        return (a + b) % MOD
    full_up(value_table, value_binop)

    for _q in range(Q):
        q, *args = map(int, input().split())
        if q == 0:
            l, r, b, c = args
            lazy_range_update(
                action_table, value_table, l, r, (b, c),
                action_composite, action_force, action_unity, value_binop)
        else:
            l, r = args
            print(lazy_range_reduce(
                action_table, value_table, l, r,
                action_composite, action_force, action_unity, value_binop, value_unity))


T1 = """
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
"""
TEST_T1 = """
>>> as_input(T1)
>>> main()
15
404
41511
4317767
"""


def _test():
    import doctest
    doctest.testmod()
    g = globals()
    for k in sorted(g):
        if k.startswith("TEST_"):
            doctest.run_docstring_examples(g[k], g, name=k)


def as_input(s):
    "use in test, use given string as input file"
    import io
    f = io.StringIO(s.strip())
    g = globals()
    g["input"] = lambda: bytes(f.readline(), "ascii")
    g["read"] = lambda: bytes(f.read(), "ascii")


input = sys.stdin.buffer.readline
read = sys.stdin.buffer.read

if sys.argv[-1] == "-t":
    print("testing")
    _test()
    sys.exit()

main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**6)
INF = 10 ** 9 + 1  # sys.maxsize # float("inf")
MOD = 998244353


def set_depth(depth):
    global DEPTH, SEGTREE_SIZE, NONLEAF_SIZE
    DEPTH = depth
    SEGTREE_SIZE = 1 << DEPTH
    NONLEAF_SIZE = 1 << (DEPTH - 1)


def set_width(width):
    set_depth((width - 1).bit_length() + 1)


def get_size(pos):
    ret = pos.bit_length()
    return (1 << (DEPTH - ret))


def up(pos):
    pos += SEGTREE_SIZE // 2
    return pos // (pos & -pos)


def up_propagate(table, pos, binop):
    while pos > 1:
        pos >>= 1
        table[pos] = binop(
            table[pos * 2],
            table[pos * 2 + 1]
        )


def full_up(table, binop):
    for i in range(NONLEAF_SIZE - 1, 0, -1):
        table[i] = binop(
            table[2 * i],
            table[2 * i + 1])


def force_down_propagate(
    action_table, value_table, pos,
    action_composite, action_force, action_unity
):
    max_level = pos.bit_length() - 1
    size = NONLEAF_SIZE
    for level in range(max_level):
        size //= 2
        i = pos >> (max_level - level)
        action = action_table[i]
        if action != action_unity:
            action_table[i * 2] = action_composite(
                action, action_table[i * 2])
            action_table[i * 2 + 1] = action_composite(
                action, action_table[i * 2 + 1])
            action_table[i] = action_unity
            value_table[i * 2] = action_force(
                action, value_table[i * 2], size)
            value_table[i * 2 + 1] = action_force(
                action, value_table[i * 2 + 1], size)


def force_range_update(
    value_table, action_table, left, right,
    action, action_force, action_composite, action_unity
):
    """
    action_force: action, value, cell_size => new_value
    action_composite: new_action, old_action => composite_action
    """
    left += NONLEAF_SIZE
    right += NONLEAF_SIZE
    while left < right:
        if left & 1:
            value_table[left] = action_force(
                action, value_table[left], get_size(left))
            action_table[left] = action_composite(action, action_table[left])
            left += 1
        if right & 1:
            right -= 1
            value_table[right] = action_force(
                action, value_table[right], get_size(right))
            action_table[right] = action_composite(action, action_table[right])

        left //= 2
        right //= 2


def range_reduce(table, left, right, binop, unity):
    ret_left = unity
    ret_right = unity
    left += NONLEAF_SIZE
    right += NONLEAF_SIZE
    while left < right:
        if left & 1:
            ret_left = binop(ret_left, table[left])
            left += 1
        if right & 1:
            right -= 1
            ret_right = binop(table[right], ret_right)

        left //= 2
        right //= 2
    return binop(ret_left, ret_right)


def lazy_range_update(
        action_table, value_table, start, end,
        action, action_composite, action_force, action_unity, value_binop):
    "update [start, end)"
    L = up(start)
    R = up(end)
    force_down_propagate(
        action_table, value_table, L,
        action_composite, action_force, action_unity)
    force_down_propagate(
        action_table, value_table, R,
        action_composite, action_force, action_unity)

    # print("action", file=sys.stderr)
    # debugprint(action_table)
    # print("value", file=sys.stderr)
    # debugprint(value_table)
    # print(file=sys.stderr)

    force_range_update(
        value_table, action_table, start, end,
        action, action_force, action_composite, action_unity)
    up_propagate(value_table, L, value_binop)
    up_propagate(value_table, R, value_binop)


def lazy_range_reduce(
    action_table, value_table, start, end,
    action_composite, action_force, action_unity,
    value_binop, value_unity
):
    "reduce [start, end)"
    force_down_propagate(
        action_table, value_table, up(start),
        action_composite, action_force,  action_unity)
    force_down_propagate(
        action_table, value_table, up(end),
        action_composite, action_force, action_unity)

    return range_reduce(value_table, start, end, value_binop, value_unity)


def debug(*x):
    print(*x, file=sys.stderr)


def main():
    # parse input
    N, Q = map(int, input().split())
    AS = list(map(int, input().split()))
    set_width(N + 1)

    value_unity = 0
    value_table = [value_unity] * SEGTREE_SIZE
    value_table[NONLEAF_SIZE:NONLEAF_SIZE + len(AS)] = AS

    action_unity = None
    action_table = [action_unity] * SEGTREE_SIZE

    def action_force(action, value, size):
        if action == action_unity:
            return value
        b, c = action
        return (value * b + c * size) % MOD

    def action_composite(new_action, old_action):
        if new_action == action_unity:
            return old_action
        if old_action == action_unity:
            return new_action
        b1, c1 = old_action
        b2, c2 = new_action
        return (b1 * b2, b2 * c1 + c2)

    def value_binop(a, b):
        return (a + b) % MOD
    full_up(value_table, value_binop)

    for _q in range(Q):
        q, *args = map(int, input().split())
        if q == 0:
            l, r, b, c = args
            lazy_range_update(
                action_table, value_table, l, r, (b, c),
                action_composite, action_force, action_unity, value_binop)
        else:
            l, r = args
            print(lazy_range_reduce(
                action_table, value_table, l, r,
                action_composite, action_force, action_unity, value_binop, value_unity))


T1 = """
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
"""
TEST_T1 = """
>>> as_input(T1)
>>> main()
15
404
41511
4317767
"""


def _test():
    import doctest
    doctest.testmod()
    g = globals()
    for k in sorted(g):
        if k.startswith("TEST_"):
            doctest.run_docstring_examples(g[k], g, name=k)


def as_input(s):
    "use in test, use given string as input file"
    import io
    f = io.StringIO(s.strip())
    g = globals()
    g["input"] = lambda: bytes(f.readline(), "ascii")
    g["read"] = lambda: bytes(f.read(), "ascii")


input = sys.stdin.buffer.readline
read = sys.stdin.buffer.read

if sys.argv[-1] == "-t":
    print("testing")
    _test()
    sys.exit()

main()

Submission status: Time Limit Exceeded

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):
    return [(l[0] + r[0]) % mod, l[1] + r[1]]


def mapping(f, x):
    return [(x[0] * f[0] + x[1] * f[1]) % mod, x[1]]


def composition(l, r):
    return [(l[0] * r[0]) % mod, (r[1] * l[0] + l[1]) % mod]


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

lst = LazySegmentTree([[v, 1] for v in a], [0, 0], op, [1, 0], 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], p[3]])
    else:
        print(lst.prod(*p)[0])

Submission status: Time Limit Exceeded

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")



### 遅延評価セグメント木
class LazySegmentTree:
    def __init__(self, n, a=None):
        """初期化
        num : n以上の最小の2のべき乗
        """
        num = 1
        while num<=n:
            num *= 2
        self.num = num
        self.seg = [ninf] * (2*self.num-1)
        self.lazy = [f0] * (2*self.num-1)
        self.ls = [0]*(2*self.num-1)
        self.rs = [0]*(2*self.num-1)
        self.ls[0] = 0
        self.rs[0] = self.num
        for i in range(self.num-1):
            self.ls[2*i+1] = self.ls[i]
            self.rs[2*i+1] = (self.ls[i] + self.rs[i])//2
            self.ls[2*i+2] = (self.ls[i] + self.rs[i])//2
            self.rs[2*i+2] = self.rs[i]
        if a is not None:
            # O(n)で初期化
            assert len(a)==n
            for i in range(n):
                self.seg[num-1+i] = a[i]
            for k in range(num-2, -1, -1):
                self.seg[k] = op(self.seg[2*k+1], self.seg[2*k+2])
    def eval(self, k):
        if self.lazy[k]==f0:
            return 
        if k<self.num-1:
            self.lazy[k*2+1] = composition(self.lazy[k], self.lazy[k*2+1])
            self.lazy[k*2+2] = composition(self.lazy[k], self.lazy[k*2+2])
        self.seg[k] = mapping(self.lazy[k], self.seg[k])
        self.lazy[k] = f0
    def eval_all(self):
        for i in range(2*self.num-1):
            self.eval(i)
    def update(self,a,b,x=None,f=None):
        """A[a]...A[b-1]をxに更新する
        """
        if f is None:
            # 更新クエリ
            f = lambda y: x
        k = 0
        q = [k] # k>=0なら行きがけ順
        # 重なる区間を深さ優先探索
        while len(q):
            k = q.pop()
            l,r = self.ls[k], self.rs[k]
            if k>=0:
                self.eval(k)
                if r<=a or b<=l:
                    continue
                elif a<=l and r<=b:
                    self.lazy[k] = composition(f, self.lazy[k])
                    self.eval(k)
                else:
                    q.append(~k)
                    q.append(2*k+1)
                    q.append(2*k+2)
            else:
                k = ~k
                self.seg[k] = op(self.seg[2*k+1], self.seg[2*k+2])
    def query(self,a,b):
        k = 0
        l = 0
        r = self.num
        q = [k]
        ans = ninf
        # 重なる区間を深さ優先探索
        while len(q):
            k = q.pop()
            l,r = self.ls[k], self.rs[k]
            self.eval(k)
            if r<=a or b<=l:
                continue
            elif a<=l and r<=b:
                ans = op(ans, self.seg[k])
            else:
                q.append(2*k+1)
                q.append(2*k+2)
        return ans
n,q = list(map(int, input().split()))
a = list(map(int, input().split()))
# ninf = -10**9
# op = max
# mapping = lambda f,x: f(x)
# composition = lambda f1, f2: f1 if f1 is not None else f2
M = 998244353
ninf = (0,0)
op = lambda x,y: ((x[0]+y[0])%M, (x[1]+y[1]))
mapping = lambda f,x: ((f[0]*x[0] + f[1]*x[1])%M, x[1])
composition = lambda f1, f2: ((f1[0]*f2[0])%M, (f2[1]*f1[0]+f1[1])%M)
f0 = (1,0)
sg = LazySegmentTree(n, [(item,1) for item in a])
ans = []
for _ in range(q):
    t = tuple(map(int, input().split()))
    if t[0]==0:
        _, l,r,b,c = t
        sg.update(l,r,f=(b,c))
    else:
        _,s,t = t
        ans.append(sg.query(s,t)[0])
write("\n".join(map(str, ans)))

Submission status: Time Limit Exceeded

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")



### 遅延評価セグメント木
class LazySegmentTree:
    def __init__(self, n, a=None):
        """初期化
        num : n以上の最小の2のべき乗
        """
        num = 1
        while num<=n:
            num *= 2
        self.num = num
        self.seg = [ninf] * (2*self.num-1)
        self.lazy = [f0] * (2*self.num-1)
        self.ls = [0]*(2*self.num-1)
        self.rs = [0]*(2*self.num-1)
        self.ls[0] = 0
        self.rs[0] = self.num
        for i in range(self.num-1):
            self.ls[2*i+1] = self.ls[i]
            self.rs[2*i+1] = (self.ls[i] + self.rs[i])//2
            self.ls[2*i+2] = (self.ls[i] + self.rs[i])//2
            self.rs[2*i+2] = self.rs[i]
        if a is not None:
            # O(n)で初期化
            assert len(a)==n
            for i in range(n):
                self.seg[num-1+i] = a[i]
            for k in range(num-2, -1, -1):
                self.seg[k] = op(self.seg[2*k+1], self.seg[2*k+2])
    def eval(self, k):
        if self.lazy[k]==f0:
            return 
        if k<self.num-1:
            self.lazy[k*2+1] = composition(self.lazy[k], self.lazy[k*2+1])
            self.lazy[k*2+2] = composition(self.lazy[k], self.lazy[k*2+2])
        self.seg[k] = mapping(self.lazy[k], self.seg[k])
        self.lazy[k] = f0
    def eval_all(self):
        for i in range(2*self.num-1):
            self.eval(i)
    def update(self,a,b,x=None,f=None):
        """A[a]...A[b-1]をxに更新する
        """
        if f is None:
            # 更新クエリ
            f = lambda y: x
        k = 0
        q = [k] # k>=0なら行きがけ順
        # 重なる区間を深さ優先探索
        while q:
            k = q.pop()
            l,r = self.ls[k], self.rs[k]
            if k>=0:
                self.eval(k)
                if r<=a or b<=l:
                    continue
                elif a<=l and r<=b:
                    self.lazy[k] = composition(f, self.lazy[k])
                    self.eval(k)
                else:
                    q.append(~k)
                    q.append(2*k+1)
                    q.append(2*k+2)
            else:
                k = ~k
                self.seg[k] = op(self.seg[2*k+1], self.seg[2*k+2])
    def query(self,a,b):
        k = 0
        l = 0
        r = self.num
        q = [k]
        ans = ninf
        # 重なる区間を深さ優先探索
        while q:
            k = q.pop()
            l,r = self.ls[k], self.rs[k]
            self.eval(k)
            if r<=a or b<=l:
                continue
            elif a<=l and r<=b:
                ans = op(ans, self.seg[k])
            else:
                q.append(2*k+1)
                q.append(2*k+2)
        return ans
n,q = list(map(int, input().split()))
a = list(map(int, input().split()))
# ninf = -10**9
# op = max
# mapping = lambda f,x: f(x)
# composition = lambda f1, f2: f1 if f1 is not None else f2
M = 998244353
ninf = (0,0)
op = lambda x,y: ((x[0]+y[0])%M, (x[1]+y[1]))
mapping = lambda f,x: ((f[0]*x[0] + f[1]*x[1])%M, x[1])
composition = lambda f1, f2: ((f1[0]*f2[0])%M, (f2[1]*f1[0]+f1[1])%M)
f0 = (1,0)
sg = LazySegmentTree(n, [(item,1) for item in a])
ans = []
for _ in range(q):
    t = tuple(map(int, input().split()))
    if t[0]==0:
        _, l,r,b,c = t
        sg.update(l,r,f=(b,c))
    else:
        _,s,t = t
        ans.append(sg.query(s,t)[0])
write("\n".join(map(str, ans)))

Submission status: Time Limit Exceeded

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")



### 遅延評価セグメント木
class LazySegmentTree:
    def __init__(self, n, a=None):
        """初期化
        num : n以上の最小の2のべき乗
        """
        num = 1
        while num<=n:
            num *= 2
        self.num = num
        self.seg = [ninf] * (2*self.num-1)
        self.lazy = [f0] * (2*self.num-1)
        if a is not None:
            # O(n)で初期化
            assert len(a)==n
            for i in range(n):
                self.seg[num-1+i] = a[i]
            for k in range(num-2, -1, -1):
                self.seg[k] = op(self.seg[2*k+1], self.seg[2*k+2])
    def eval(self, k):
        if self.lazy[k] is f0:
            return 
        if k<self.num-1:
            self.lazy[k*2+1] = composition(self.lazy[k], self.lazy[k*2+1])
            self.lazy[k*2+2] = composition(self.lazy[k], self.lazy[k*2+2])
        self.seg[k] = mapping(self.lazy[k], self.seg[k])
        self.lazy[k] = f0
    def eval_all(self):
        for i in range(2*self.num-1):
            self.eval(i)
    def update(self,a,b,x=None,f=None):
        """A[a]...A[b-1]をxに更新する
        """
        if f is None:
            # 更新クエリ
            f = lambda y: x
        k = 0
        l = 0
        r = self.num
        q = [(k,l,r)] # k>=0なら行きがけ順
        # 重なる区間を深さ優先探索
        while q:
            k,l,r = q.pop()
            if k>=0:
                self.eval(k)
                if r<=a or b<=l:
                    continue
                elif a<=l and r<=b:
                    self.lazy[k] = composition(f, self.lazy[k])
                    self.eval(k)
                else:
                    q.append((~k,l,r))
                    val = (l+r)//2
                    q.append((2*k+1,l,val))
                    q.append((2*k+2,val,r))
            else:
                k = ~k
                self.seg[k] = op(self.seg[2*k+1], self.seg[2*k+2])
    def query(self,a,b):
        k = 0
        l = 0
        r = self.num
        q = [(k,l,r)]
        ans = ninf
        # 重なる区間を深さ優先探索
        while q:
            k,l,r = q.pop()
            self.eval(k)
            if r<=a or b<=l:
                continue
            elif a<=l and r<=b:
                ans = op(ans, self.seg[k])
            else:
                val = (l+r)//2
                q.append((2*k+1,l,val))
                q.append((2*k+2,val,r))
        return ans
n,q = list(map(int, input().split()))
a = list(map(int, input().split()))
# ninf = -10**9
# op = max
# mapping = lambda f,x: f(x)
# composition = lambda f1, f2: f1 if f1 is not None else f2
M = 998244353
ninf = (0,0)
op = lambda x,y: ((x[0]+y[0])%M, (x[1]+y[1]))
mapping = lambda f,x: ((f[0]*x[0] + f[1]*x[1])%M, x[1])
composition = lambda f1, f2: ((f1[0]*f2[0])%M, (f2[1]*f1[0]+f1[1])%M)
f0 = (1,0)
sg = LazySegmentTree(n, [(item,1) for item in a])
ans = []
for _ in range(q):
    t = tuple(map(int, input().split()))
    if t[0]==0:
        _, l,r,b,c = t
        sg.update(l,r,f=(b,c))
    else:
        _,s,t = t
        ans.append(sg.query(s,t)[0])
write("\n".join(map(str, ans)))