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:
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.lrs = [0]*(2*self.num-1)
        self.lrs[0] = (0,self.num)
        for i in range(self.num-1):
            val = (self.lrs[i][0] + self.lrs[i][1])//2
            self.lrs[2*i+1] = (self.lrs[i][0], val)
            self.lrs[2*i+2] = (val, self.lrs[i][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
        q = [k] # k>=0なら行きがけ順
        # 重なる区間を深さ優先探索
        while q:
            k = q.pop()
            l,r = self.lrs[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.lrs[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])%M)
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] 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
        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])%M)
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] 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
        q = [(k,True)] # 行きがけ順かどうか
        # 重なる区間を深さ優先探索
        while q:
            k,flg = q.pop()
            l,r = self.ls[k], self.rs[k]
            if flg:
                self.eval(k)
                if r<=a or b<=l:
                    pass
                elif a<=l and r<=b:
                    self.lazy[k] = composition(f, self.lazy[k])
                    self.eval(k)
                else:
                    q.append((k,False))
                    q.append((2*k+1,True))
                    q.append((2*k+2,True))
            else:
                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:
                pass
            elif a<=l and r<=b:
                ans = op(ans, self.seg[k])
            else:
                if l<=a:
                    if (l+r)//2>a:
                        q.append(2*k+1)
                        q.append(2*k+2)
                    else:
                        q.append(2*k+2)
                else:
                    if (l+r)//2<b:
                        q.append(2*k+1)
                        q.append(2*k+2)
                    else:
                        q.append(2*k+1)
        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])%M)
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 = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 7)
mod = 998244353


u_data = (0, 0)
u_lazy = (1, 0)


class LazySegmetTree:
    def __init__(self, size):
        """
        size: 元の配列の長さ
        op_data, u_data: クエリ関数、単位元
        op_lazy, u_lazy: 遅延作用の関数、単位元
        op_merge: dataとlazyとの演算
        """
        self.N = size
        self.u_data = (0, 0)
        self.u_lazy = (1, 0)
        self.data = [self.u_data] * (2 * self.N)
        self.lazy = [self.u_lazy] * (2 * self.N)

    def op_data(self, L, R):
        return (L[0] + R[0]) % mod, (L[1] + R[1]) % mod

    def op_lazy(self, L, R):
        return (L[0] * R[0]) % mod, (L[0] * R[1] + L[1]) % mod

    def op_merge(self, L, R):
        return (R[0] * L[0] + R[1] * L[1]) % mod, R[1]

    def initialize(self, arr):
        op = self.op_data
        for i, a in enumerate(arr, self.N):
            self.data[i] = a
        for i in reversed(range(1, self.N)):
            self.data[i] = op(self.data[i << 1], self.data[i << 1 | 1])

    def show(self):
        print("show array")
        for i in range(self.N):
            print(self.fold(i, i+1), end=" ")
        print("\n")

    def _propagate_top_down(self, L):
        op = self.op_lazy
        merge = self.op_merge
        unit = self.u_lazy
        for i in reversed(range(1, L.bit_length())):
            i = L >> i
            v = self.lazy[i]
            if v == unit:
                continue
            self.data[i] = merge(v, self.data[i])
            self.lazy[i << 1] = op(v, self.lazy[i << 1])
            self.lazy[i << 1 | 1] = op(v, self.lazy[i << 1 | 1])
            self.lazy[i] = unit

    def _propagate_bottom_up(self, i):
        merge = self.op_merge
        op = self.op_data
        while i > 1:
            i >>= 1
            self.data[i] = op(merge(self.lazy[i << 1], self.data[i << 1]),
                              merge(self.lazy[i << 1 | 1], self.data[i << 1 | 1]))

    def fold(self, L, R):
        resL = self.u_data
        resR = self.u_data
        op = self.op_data
        merge = self.op_merge
        L += self.N
        R += self.N
        L0 = L // (L & -L)
        R0 = R // (R & -R) - 1
        self._propagate_top_down(L0)
        self._propagate_top_down(R0)
        while L < R:
            if L & 1:
                resL = op(resL, merge(self.lazy[L], self.data[L]))
                L += 1
            if R & 1:
                R -= 1
                resR = op(merge(self.lazy[R], self.data[R]), resR)
            L >>= 1
            R >>= 1
        return op(resL, resR)

    def update(self, i, val):  # 未調整
        i += self.N
        i0 = i // (i & -i)
        self._propagate_top_down(i0)
        self.data[i] = self.op_merge(self.lazy[i], self.data[i])
        self.data[i] = self.op_data(val, self.data[i])
        self.lazy[i] = self.u_lazy
        self._propagate_bottom_up(i0)

    def range_update(self, L, R, val):
        op = self.op_lazy
        L += self.N
        R += self.N
        L0 = L // (L & -L)
        R0 = R // (R & -R) - 1
        self._propagate_top_down(L0)
        self._propagate_top_down(R0)
        while L < R:
            if L & 1:
                self.lazy[L] = op(val, self.lazy[L])
                L += 1
            if R & 1:
                R -= 1
                self.lazy[R] = op(val, self.lazy[R])
            L >>= 1
            R >>= 1
        self._propagate_bottom_up(L0)
        self._propagate_bottom_up(R0)


N, Q = map(int, input().split())
arr = [(a, 1) for a in map(int, input().split())]  # val, sz

seg = LazySegmetTree(N)
seg.initialize(arr)

for _ in range(Q):
    t, *arg = map(int, input().split())
    if t == 0:
        l, r, a, b = arg
        seg.range_update(l, r, (a, b))
    else:
        l, r = arg
        print(seg.fold(l, r)[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] 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
        q = [(k,True)] # 行きがけ順かどうか
        # 重なる区間を深さ優先探索
        while q:
            k,flg = q.pop()
            l,r = self.ls[k], self.rs[k]
            if flg:
                self.eval(k)
                if r<=a or b<=l:
                    pass
                elif a<=l and r<=b:
                    self.lazy[k] = composition(f, self.lazy[k])
                    self.eval(k)
                else:
                    q.append((k,False))
                    q.append((2*k+1,True))
                    q.append((2*k+2,True))
            else:
                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:
                pass
            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])%M)
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:
mod = 998244353


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


def op(L, R):
    La, Lsize = L
    Ra, Rsize = R
    return (La + Ra) % mod, 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) % mod, Rsize


def composition(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, 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: 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,True)] # 行きがけ順かどうか
        # 重なる区間を深さ優先探索
        while q:
            k,l,r,flg = q.pop()
            if flg:
                self.eval(k)
                if r<=a or b<=l:
                    pass
                elif a<=l and r<=b:
                    self.lazy[k] = composition(f, self.lazy[k])
                    self.eval(k)
                else:
                    q.append((k,l,r,False))
                    q.append((2*k+1,l,(l+r)//2,True))
                    q.append((2*k+2,(l+r)//2,r,True))
            else:
                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:
                pass
            elif a<=l and r<=b:
                ans = op(ans, self.seg[k])
            else:
                q.append((2*k+1,l,(l+r)//2))
                q.append((2*k+2,(l+r)//2,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])%M)
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 = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 7)
mod = 998244353


u_data = (0, 0)
u_lazy = (1, 0)


def op_data(L, R):
    return (L[0] + R[0]) % mod, (L[1] + R[1]) % mod


def op_lazy(L, R):
    return (L[0] * R[0]) % mod, (L[0] * R[1] + L[1]) % mod


def op_merge(L, R):
    return (R[0] * L[0] + R[1] * L[1]) % mod, R[1]


class LazySegmetTree:
    def __init__(self, size, op_data, u_data, op_lazy, u_lazy, op_merge):
        """
        size: 元の配列の長さ
        op_data, u_data: クエリ関数、単位元
        op_lazy, u_lazy: 遅延作用の関数、単位元
        op_merge: dataとlazyとの演算
        """
        self.N = size
        self.op_data = op_data
        self.op_lazy = op_lazy
        self.op_merge = op_merge
        self.u_data = u_data
        self.u_lazy = u_lazy
        self.data = [u_data] * (2 * self.N)
        self.lazy = [u_lazy] * (2 * self.N)

    def initialize(self, arr):
        op = self.op_data
        for i, a in enumerate(arr, self.N):
            self.data[i] = a
        for i in reversed(range(1, self.N)):
            self.data[i] = op(self.data[i << 1], self.data[i << 1 | 1])

    def show(self):
        print("show array")
        for i in range(self.N):
            print(self.fold(i, i+1), end=" ")
        print("\n")

    def _propagate_top_down(self, L):
        op = self.op_lazy
        merge = self.op_merge
        unit = self.u_lazy
        for i in reversed(range(1, L.bit_length())):
            i = L >> i
            v = self.lazy[i]
            if v == unit:
                continue
            self.data[i] = merge(v, self.data[i])
            self.lazy[i << 1] = op(v, self.lazy[i << 1])
            self.lazy[i << 1 | 1] = op(v, self.lazy[i << 1 | 1])
            self.lazy[i] = unit

    def _propagate_bottom_up(self, i):
        merge = self.op_merge
        op = self.op_data
        while i > 1:
            i >>= 1
            self.data[i] = op(merge(self.lazy[i << 1], self.data[i << 1]),
                              merge(self.lazy[i << 1 | 1], self.data[i << 1 | 1]))

    def fold(self, L, R):
        resL = self.u_data
        resR = self.u_data
        op = self.op_data
        merge = self.op_merge
        L += self.N
        R += self.N
        L0 = L // (L & -L)
        R0 = R // (R & -R) - 1
        self._propagate_top_down(L0)
        self._propagate_top_down(R0)
        while L < R:
            if L & 1:
                resL = op(resL, merge(self.lazy[L], self.data[L]))
                L += 1
            if R & 1:
                R -= 1
                resR = op(merge(self.lazy[R], self.data[R]), resR)
            L >>= 1
            R >>= 1
        return op(resL, resR)

    def update(self, i, val):  # 未調整
        i += self.N
        i0 = i // (i & -i)
        self._propagate_top_down(i0)
        self.data[i] = self.op_merge(self.lazy[i], self.data[i])
        self.data[i] = self.op_data(val, self.data[i])
        self.lazy[i] = self.u_lazy
        self._propagate_bottom_up(i0)

    def range_update(self, L, R, val):
        op = self.op_lazy
        L += self.N
        R += self.N
        L0 = L // (L & -L)
        R0 = R // (R & -R) - 1
        self._propagate_top_down(L0)
        self._propagate_top_down(R0)
        while L < R:
            if L & 1:
                self.lazy[L] = op(val, self.lazy[L])
                L += 1
            if R & 1:
                R -= 1
                self.lazy[R] = op(val, self.lazy[R])
            L >>= 1
            R >>= 1
        self._propagate_bottom_up(L0)
        self._propagate_bottom_up(R0)


N, Q = map(int, input().split())
arr = [(a, 1) for a in map(int, input().split())]  # val, sz

seg = LazySegmetTree(N, op_data, u_data, op_lazy, u_lazy, op_merge)
seg.initialize(arr)

for _ in range(Q):
    t, *arg = map(int, input().split())
    if t == 0:
        l, r, a, b = arg
        seg.range_update(l, r, (a, b))
    else:
        l, r = arg
        print(seg.fold(l, r)[0])