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:
class lazy_segtree(object):

    def __init__(self, n_or_vec, op, e, mapping, composition, identity):
        self.op = op
        self.e = e
        self.mapping = mapping
        self.composition = composition
        self.identity = identity
        if isinstance(n_or_vec, int):
            self.n = n_or_vec
            v = [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 = [e()] * (2 * self.size)
        self.lz = [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


class mint:
    def __init__(self, x, MOD=998244353):
        """ 引用 https://qiita.com/wotsushi/items/c936838df992b706084c """
        self.x = x % MOD
        self.mod = MOD

    def __str__(self):
        return str(self.x)

    __repr__ = __str__

    def __add__(self, other):
        if isinstance(other, mint):
            return mint(self.x + other.x)
        return mint(self.x + other)

    def __sub__(self, other):
        if isinstance(other, mint):
            return mint(self.x - other.x)
        return mint(self.x - other)

    def __mul__(self, other):
        if isinstance(other, mint):
            return mint(self.x * other.x)
        return mint(self.x * other)

    def __truediv__(self, other):
        """python3.8以降しかpow(a, -1, mod)を使えないので注意"""
        if isinstance(other, mint):
            return self.x * pow(other.x, -1, self.mod)
        return mint(self.x * pow(other, -1, self.mod))

    def __pow__(self, other):
        if isinstance(other, mint):
            return mint(pow(self.x, other.x, self.mod))
        return mint(pow(self.x, other, self.mod))

    __radd__ = __add__

    def __rsub__(self, other):
        if isinstance(other, mint):
            return mint(other.x - self.x)
        return mint(other - self.x)

    __rmul__ = __mul__

    def __rtruediv__(self, other):
        if isinstance(other, mint):
            return mint(other.x * pow(self.x, -1, self.mod))
        return mint(other * pow(self.x, -1, self.mod))

    def __rpow__(self, other):
        if isinstance(other, mint):
            return mint(pow(other.x, self.x, self.mod))
        return mint(pow(other, self.x, self.mod))


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


def e():
    return (0, 0)


def identity():
    return (1, 0)


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


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


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

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

    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
            c = mint(c)
            d = mint(d)
            lazyseg.range_apply(l, r, (c, d))
        else:
            l, r = arg
            print(lazyseg.prod(l, r)[0])

Submission status: Time Limit Exceeded

Solution code:
#!usr/bin/env python3
from collections import defaultdict, deque, Counter, OrderedDict
from bisect import bisect_left, bisect_right
from functools import reduce, lru_cache
from heapq import heappush, heappop, heapify

import itertools
import math, fractions
import sys, copy

def L(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline().rstrip())
def SL(): return list(sys.stdin.readline().rstrip())
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI1(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LS(): return [list(x) for x in sys.stdin.readline().split()]
def R(n): return [sys.stdin.readline().strip() for _ in range(n)]
def LR(n): return [L() for _ in range(n)]
def IR(n): return [I() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def LIR1(n): return [LI1() for _ in range(n)]
def SR(n): return [SL() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]

def perm(n, r): return math.factorial(n) // math.factorial(r)
def comb(n, r): return math.factorial(n) // (math.factorial(r) * math.factorial(n-r))

def make_list(n, *args, default=0): return [make_list(*args, default=default) for _ in range(n)] if len(args) > 0 else [default for _ in range(n)]

dire = [[1, 0], [0, 1], [-1, 0], [0, -1]]
dire8 = [[1, 0], [1, 1], [0, 1], [-1, 1], [-1, 0], [-1, -1], [0, -1], [1, -1]]
alphabets = "abcdefghijklmnopqrstuvwxyz"
ALPHABETS = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
MOD = 1000000007
INF = float("inf")

sys.setrecursionlimit(1000000)
MOD = 998244353


class LazySegTree():  # モノイドに対して適用可能、Nが2冪でなくても良い
    def __init__(self, initial_values, monoid_func, composition, operate, monoid_identity, operator_identity):
        self.N = len(initial_values)
        self.monoid_func = monoid_func
        self.composition = composition
        self.operate = operate
        self.monoid_identity = monoid_identity
        self.operator_identity = operator_identity
        self.data = [self.monoid_identity]*(2*self.N)
        self.lazy = [self.operator_identity]*(2*self.N)
        self.size = [0]*(2*self.N)

        for i, ai in enumerate(initial_values):
            self.data[self.N+i] = ai
            self.size[self.N+i] = 1
        for i in range(self.N-1,0,-1):
            self.data[i] = self.monoid_func(self.data[i << 1], self.data[i << 1 | 1])
            self.size[i] = self.size[i << 1] + self.size[i << 1 | 1]

    def update(self,i,x):  # i番目(0-index)の値をxに変更
        i += self.N
        self.data[i] = x
        i >>= 1
        while i:
            self.data[i] = self.monoid_func(self.data[i << 1], self.data[i << 1 | 1])
            i >>= 1

    def eval_at(self,i):  # i番目で作用を施した値を返す
        return self.operate(self.data[i],self.lazy[i],self.size[i])

    def eval_above(self,i):  # i番目より上の値を再計算する
        i >>= 1
        while i:
            self.data[i] = self.monoid_func(self.eval_at(i << 1),self.eval_at(i << 1 | 1))
            i >>= 1

    def propagate_at(self,i):  # i番目で作用を施し、1つ下に作用の情報を伝える
        self.data[i] = self.operate(self.data[i],self.lazy[i],self.size[i])
        self.lazy[i << 1] = self.composition(self.lazy[i << 1],self.lazy[i])
        self.lazy[i << 1 | 1] = self.composition(self.lazy[i << 1 | 1], self.lazy[i])
        self.lazy[i] = self.operator_identity

    def propagate_above(self,i):  # i番目より上で作用を施す
        H = i.bit_length()
        for h in range(H,0,-1):
            self.propagate_at(i >> h)

    def fold(self, L, R):  # [L,R)の区間取得
        L += self.N
        R += self.N
        L0 = L // (L & -L)
        R0 = R // (R & -R) - 1
        self.propagate_above(L0)
        self.propagate_above(R0)
        vL = self.monoid_identity
        vR = self.monoid_identity
        while L < R:
            if L & 1:
                vL = self.monoid_func(vL,self.eval_at(L))
                L += 1
            if R & 1:
                R -= 1
                vR = self.monoid_func(self.eval_at(R),vR)
            L >>= 1
            R >>= 1
        return self.monoid_func(vL,vR)

    #重たい
    def operate_range(self,L,R,x):  # [L,R)にxを作用
        L += self.N
        R += self.N
        L0 = L // (L & -L)
        R0 = R // (R & -R) - 1
        self.propagate_above(L0)
        self.propagate_above(R0)
        while L < R:
            if L & 1:
                self.lazy[L] = self.composition(self.lazy[L], x)
                L += 1
            if R & 1:
                R -= 1
                self.lazy[R] = self.composition(self.lazy[R], x)
            L >>= 1
            R >>= 1
        self.eval_above(L0)
        self.eval_above(R0)


def main():
    mod = 998244353
    def monoid_func(x,y):
        return (x+y) % mod

    def composition(a,b):
        b0,c0 = a
        b1,c1 = b
        return ((b0*b1) % mod,(b1*c0+c1) % mod)

    def operate(x,a,r): # 右作用
        b,c = a
        return (b*x+c*r) % mod

    monoid_identity = 0
    operator_identity = (1,0)

    N, Q = LI()
    A = LI()
    LST = LazySegTree(A, monoid_func, composition, operate, monoid_identity, operator_identity)

    for q in LIR(Q):
        if q[0] == 0:
            _, l, r, b, c = q
            LST.operate_range(l,r,(b,c))
        else:
            _, l, r = q
            print(LST.fold(l,r))

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#!usr/bin/env python3
from collections import defaultdict, deque, Counter, OrderedDict
from bisect import bisect_left, bisect_right
from functools import reduce, lru_cache
from heapq import heappush, heappop, heapify

import itertools
import math, fractions
import sys, copy

def L(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline().rstrip())
def SL(): return list(sys.stdin.readline().rstrip())
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI1(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LS(): return [list(x) for x in sys.stdin.readline().split()]
def R(n): return [sys.stdin.readline().strip() for _ in range(n)]
def LR(n): return [L() for _ in range(n)]
def IR(n): return [I() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def LIR1(n): return [LI1() for _ in range(n)]
def SR(n): return [SL() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]

def perm(n, r): return math.factorial(n) // math.factorial(r)
def comb(n, r): return math.factorial(n) // (math.factorial(r) * math.factorial(n-r))

def make_list(n, *args, default=0): return [make_list(*args, default=default) for _ in range(n)] if len(args) > 0 else [default for _ in range(n)]

dire = [[1, 0], [0, 1], [-1, 0], [0, -1]]
dire8 = [[1, 0], [1, 1], [0, 1], [-1, 1], [-1, 0], [-1, -1], [0, -1], [1, -1]]
alphabets = "abcdefghijklmnopqrstuvwxyz"
ALPHABETS = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
MOD = 1000000007
INF = float("inf")

sys.setrecursionlimit(1000000)
MOD = 998244353


class LazySegTree():  # モノイドに対して適用可能、Nが2冪でなくても良い
    def __init__(self, initial_values, monoid_func, composition, operate, monoid_identity, operator_identity):
        self.N = len(initial_values)
        self.monoid_func = monoid_func
        self.composition = composition
        self.operate = operate
        self.monoid_identity = monoid_identity
        self.operator_identity = operator_identity
        self.data = [self.monoid_identity]*(2*self.N)
        self.lazy = [self.operator_identity]*(2*self.N)
        self.size = [1]*(2*self.N)

        for i in range(self.N):
            self.data[self.N+i] = initial_values[i]

        for i in range(self.N-1,0,-1):
            self.data[i] = self.monoid_func(self.data[i << 1], self.data[i << 1 | 1])
            self.size[i] = self.size[i << 1] + self.size[i << 1 | 1]

    def update(self,i,x):  # i番目(0-index)の値をxに変更
        i += self.N
        self.data[i] = x
        while i > 1:
            i >>= 1
            self.data[i] = self.monoid_func(self.data[i << 1], self.data[i << 1 | 1])

    def eval_at(self,i):  # i番目で作用を施した値を返す
        return self.operate(self.data[i],self.lazy[i],self.size[i])

    def eval_above(self,i):  # i番目より上の値を再計算する
        while i > 1:
            i >>= 1
            self.data[i] = self.monoid_func(self.eval_at(i << 1), self.eval_at(i << 1 | 1))

    def propagate_at(self,i):  # i番目で作用を施し、1つ下に作用の情報を伝える
        self.data[i] = self.operate(self.data[i], self.lazy[i], self.size[i])
        self.lazy[i << 1] = self.composition(self.lazy[i << 1],self.lazy[i])
        self.lazy[i << 1 | 1] = self.composition(self.lazy[i << 1 | 1], self.lazy[i])
        self.lazy[i] = self.operator_identity

    def propagate_above(self,i):  # i番目より上で作用を施す
        H = i.bit_length()
        for h in range(H,0,-1):
            self.propagate_at(i >> h)

    def fold(self, L, R):  # [L,R)の区間取得
        L += self.N
        R += self.N
        L0 = L // (L & -L)
        R0 = R // (R & -R) - 1
        self.propagate_above(L0)
        self.propagate_above(R0)
        vL, vR = self.monoid_identity, self.monoid_identity
        while L < R:
            if L & 1:
                vL = self.monoid_func(vL,self.eval_at(L))
                L += 1
            if R & 1:
                R -= 1
                vR = self.monoid_func(self.eval_at(R),vR)
            L >>= 1
            R >>= 1
        return self.monoid_func(vL,vR)

    #重たい
    def operate_range(self,L,R,x):  # [L,R)にxを作用
        L += self.N
        R += self.N
        L0 = L // (L & -L)
        R0 = R // (R & -R) - 1
        self.propagate_above(L0)
        self.propagate_above(R0)
        while L < R:
            if L & 1:
                self.lazy[L] = self.composition(self.lazy[L], x)
                L += 1
            if R & 1:
                R -= 1
                self.lazy[R] = self.composition(self.lazy[R], x)
            L >>= 1
            R >>= 1
        self.eval_above(L0)
        self.eval_above(R0)


def main():
    mod = 998244353
    def monoid_func(x,y):
        return (x+y) % mod

    def composition(a,b):
        b0,c0 = a
        b1,c1 = b
        return ((b0*b1) % mod,(b1*c0+c1) % mod)

    def operate(x,a,r):
        b,c = a
        return (b*x+c*r) % mod

    monoid_identity = 0
    operator_identity = (1,0)

    N, Q = LI()
    A = LI()
    LST = LazySegTree(A, monoid_func, composition, operate, monoid_identity, operator_identity)

    for i in range(Q):
        X = LI()
        if X[0] == 0:
            l,r,b,c = X[1:]
            LST.operate_range(l,r,(b,c))
        else:
            l,r = X[1:]
            print(LST.fold(l,r))

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#!usr/bin/env python3
from collections import defaultdict, deque, Counter, OrderedDict
from bisect import bisect_left, bisect_right
from functools import reduce, lru_cache
from heapq import heappush, heappop, heapify

import itertools
import math, fractions
import sys, copy

def L(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline().rstrip())
def SL(): return list(sys.stdin.readline().rstrip())
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI1(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LS(): return [list(x) for x in sys.stdin.readline().split()]
def R(n): return [sys.stdin.readline().strip() for _ in range(n)]
def LR(n): return [L() for _ in range(n)]
def IR(n): return [I() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def LIR1(n): return [LI1() for _ in range(n)]
def SR(n): return [SL() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]

def perm(n, r): return math.factorial(n) // math.factorial(r)
def comb(n, r): return math.factorial(n) // (math.factorial(r) * math.factorial(n-r))

def make_list(n, *args, default=0): return [make_list(*args, default=default) for _ in range(n)] if len(args) > 0 else [default for _ in range(n)]

dire = [[1, 0], [0, 1], [-1, 0], [0, -1]]
dire8 = [[1, 0], [1, 1], [0, 1], [-1, 1], [-1, 0], [-1, -1], [0, -1], [1, -1]]
alphabets = "abcdefghijklmnopqrstuvwxyz"
ALPHABETS = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
MOD = 1000000007
INF = float("inf")

sys.setrecursionlimit(1000000)
MOD = 998244353


class LazySegTree():  # モノイドに対して適用可能、Nが2冪でなくても良い
    def __init__(self, initial_values, monoid_func, composition, operate, monoid_identity, operator_identity):
        self.N = len(initial_values)
        self.monoid_func = monoid_func
        self.composition = composition
        self.operate = operate
        self.monoid_identity = monoid_identity
        self.operator_identity = operator_identity
        self.data = [self.monoid_identity]*self.N + initial_values
        self.lazy = [self.operator_identity]*(2*self.N)
        self.size = [0]*self.N + [1]*self.N

        for i in range(self.N-1,0,-1):
            self.data[i] = self.monoid_func(self.data[i << 1], self.data[i << 1 | 1])
            self.size[i] = self.size[i << 1] + self.size[i << 1 | 1]

    def update(self,i,x):  # i番目(0-index)の値をxに変更
        i += self.N
        self.data[i] = x
        while i > 1:
            i >>= 1
            self.data[i] = self.monoid_func(self.data[i << 1], self.data[i << 1 | 1])

    def eval_at(self,i):  # i番目で作用を施した値を返す
        return self.operate(self.data[i],self.lazy[i],self.size[i])

    def eval_above(self,i):  # i番目より上の値を再計算する
        while i > 1:
            i >>= 1
            self.data[i] = self.monoid_func(self.eval_at(i << 1), self.eval_at(i << 1 | 1))

    def propagate_at(self,i):  # i番目で作用を施し、1つ下に作用の情報を伝える
        self.data[i] = self.operate(self.data[i], self.lazy[i], self.size[i])
        self.lazy[i << 1] = self.composition(self.lazy[i << 1],self.lazy[i])
        self.lazy[i << 1 | 1] = self.composition(self.lazy[i << 1 | 1], self.lazy[i])
        self.lazy[i] = self.operator_identity

    def propagate_above(self,i):  # i番目より上で作用を施す
        H = i.bit_length()
        for h in range(H,0,-1):
            self.propagate_at(i >> h)

    def fold(self, L, R):  # [L,R)の区間取得
        L += self.N
        R += self.N
        L0 = L // (L & -L)
        R0 = R // (R & -R) - 1
        self.propagate_above(L0)
        self.propagate_above(R0)
        vL, vR = self.monoid_identity, self.monoid_identity
        while L < R:
            if L & 1:
                vL = self.monoid_func(vL,self.eval_at(L))
                L += 1
            if R & 1:
                R -= 1
                vR = self.monoid_func(self.eval_at(R),vR)
            L >>= 1
            R >>= 1
        return self.monoid_func(vL,vR)

    #重たい
    def operate_range(self,L,R,x):  # [L,R)にxを作用
        L += self.N
        R += self.N
        L0 = L // (L & -L)
        R0 = R // (R & -R) - 1
        self.propagate_above(L0)
        self.propagate_above(R0)
        while L < R:
            if L & 1:
                self.lazy[L] = self.composition(self.lazy[L], x)
                L += 1
            if R & 1:
                R -= 1
                self.lazy[R] = self.composition(self.lazy[R], x)
            L >>= 1
            R >>= 1
        self.eval_above(L0)
        self.eval_above(R0)


def main():
    mod = 998244353
    def monoid_func(x,y):
        return (x+y) % mod

    def composition(a,b):
        b0,c0 = a
        b1,c1 = b
        return ((b0*b1) % mod,(b1*c0+c1) % mod)

    def operate(x,a,r):
        b,c = a
        return (b*x+c*r) % mod

    monoid_identity = 0
    operator_identity = (1,0)

    N, Q = LI()
    A = LI()
    LST = LazySegTree(A, monoid_func, composition, operate, monoid_identity, operator_identity)

    for i in range(Q):
        X = LI()
        if X[0] == 0:
            l,r,b,c = X[1:]
            LST.operate_range(l,r,(b,c))
        else:
            l,r = X[1:]
            print(LST.fold(l,r))

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#!usr/bin/env python3
from collections import defaultdict, deque, Counter, OrderedDict
from bisect import bisect_left, bisect_right
from functools import reduce, lru_cache
from heapq import heappush, heappop, heapify

import itertools
import math, fractions
import sys, copy

def L(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline().rstrip())
def SL(): return list(sys.stdin.readline().rstrip())
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI1(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LS(): return [list(x) for x in sys.stdin.readline().split()]
def R(n): return [sys.stdin.readline().strip() for _ in range(n)]
def LR(n): return [L() for _ in range(n)]
def IR(n): return [I() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def LIR1(n): return [LI1() for _ in range(n)]
def SR(n): return [SL() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]

def perm(n, r): return math.factorial(n) // math.factorial(r)
def comb(n, r): return math.factorial(n) // (math.factorial(r) * math.factorial(n-r))

def make_list(n, *args, default=0): return [make_list(*args, default=default) for _ in range(n)] if len(args) > 0 else [default for _ in range(n)]

dire = [[1, 0], [0, 1], [-1, 0], [0, -1]]
dire8 = [[1, 0], [1, 1], [0, 1], [-1, 1], [-1, 0], [-1, -1], [0, -1], [1, -1]]
alphabets = "abcdefghijklmnopqrstuvwxyz"
ALPHABETS = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
MOD = 1000000007
INF = float("inf")

sys.setrecursionlimit(1000000)
MOD = 998244353


class LazySegTree():  # モノイドに対して適用可能、Nが2冪でなくても良い
    def __init__(self, initial_values, monoid_func, composition, operate, monoid_identity, operator_identity):
        self.N = len(initial_values)
        self.monoid_func = monoid_func
        self.composition = composition
        self.operate = operate
        self.monoid_identity = monoid_identity
        self.operator_identity = operator_identity
        self.data = [self.monoid_identity]*self.N + initial_values
        self.lazy = [self.operator_identity]*(2*self.N)
        self.size = [0]*self.N + [1]*self.N

        for i in range(self.N-1,0,-1):
            self.data[i] = self.monoid_func(self.data[i << 1], self.data[i << 1 | 1])
            self.size[i] = self.size[i << 1] + self.size[i << 1 | 1]

    def update(self,i,x):  # i番目(0-index)の値をxに変更
        i += self.N
        self.data[i] = x
        while i > 1:
            i >>= 1
            self.data[i] = self.monoid_func(self.data[i << 1], self.data[i << 1 | 1])

    def eval_at(self,i):  # i番目で作用を施した値を返す
        return self.operate(self.data[i],self.lazy[i],self.size[i])

    def eval_above(self,i):  # i番目より上の値を再計算する
        while i > 1:
            i >>= 1
            self.data[i] = self.monoid_func(self.eval_at(i << 1), self.eval_at(i << 1 | 1))

    def propagate_at(self,i):  # i番目で作用を施し、1つ下に作用の情報を伝える
        self.data[i] = self.operate(self.data[i], self.lazy[i], self.size[i])
        self.lazy[i << 1] = self.composition(self.lazy[i << 1],self.lazy[i])
        self.lazy[i << 1 | 1] = self.composition(self.lazy[i << 1 | 1], self.lazy[i])
        self.lazy[i] = self.operator_identity

    def propagate_above(self,i):  # i番目より上で作用を施す
        H = i.bit_length()
        for h in range(H,0,-1):
            self.propagate_at(i >> h)

    def fold(self, L, R):  # [L,R)の区間取得
        L += self.N
        R += self.N
        L0 = L // (L & -L)
        R0 = R // (R & -R) - 1
        self.propagate_above(L0)
        self.propagate_above(R0)
        vL, vR = self.monoid_identity, self.monoid_identity
        while L < R:
            if L & 1:
                vL = self.monoid_func(vL,self.eval_at(L))
                L += 1
            if R & 1:
                R -= 1
                vR = self.monoid_func(self.eval_at(R),vR)
            L >>= 1
            R >>= 1
        return self.monoid_func(vL,vR)

    #重たい
    def operate_range(self,L,R,x):  # [L,R)にxを作用
        L += self.N
        R += self.N
        L0 = L // (L & -L)
        R0 = R // (R & -R) - 1
        self.propagate_above(L0)
        self.propagate_above(R0)
        while L < R:
            if L & 1:
                self.lazy[L] = self.composition(self.lazy[L], x)
                L += 1
            if R & 1:
                R -= 1
                self.lazy[R] = self.composition(self.lazy[R], x)
            L >>= 1
            R >>= 1
        self.eval_above(L0)
        self.eval_above(R0)


def main():
    mod = 998244353
    def monoid_func(x,y):
        return (x+y) % mod

    def composition(a,b):
        b0,c0 = a
        b1,c1 = b
        return ((b0*b1) % mod,(b1*c0+c1) % mod)

    def operate(x,a,r):
        b,c = a
        return (b*x+c*r) % mod

    monoid_identity = 0
    operator_identity = (1,0)

    N, Q = LI()
    A = LI()
    LST = LazySegTree(A, monoid_func, composition, operate, monoid_identity, operator_identity)

    for q in LIR(Q):
        if q[0] == 0:
            _, l, r, b, c = q
            LST.operate_range(l,r,(b,c))
        else:
            _, l, r = q
            print(LST.fold(l,r))

if __name__ == '__main__':
    main()