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
def input():
	return sys.stdin.buffer.readline()[:-1]

MOD = 998244353

class LazySegTree():
	def __init__(self, a, func, unit, oper, comp, idem):
		#the number of nodes is 2n-1
		self.hght = len(a).bit_length()
		self.n = 1 << self.hght
		self.size = len(a)
		self.func = func #(ele, ele) -> ele
		self.unit = unit #ele
		self.oper = oper #(ele, op) -> ele
		self.comp = comp #(op, op) -> op
		self.idem = idem #op
		self.node = [unit] * (2 * self.n)
		#immediate evaluation enables size reduction
		self.lazy = [idem] * self.n
		for i in range(self.size + self.n - 1, 0, -1):
			if i >= self.n:
				self.node[i] = a[i - self.n]
			else:
				self.update(i)

	def update(self, k):
		self.node[k] = self.func(self.node[2 * k], self.node[2 * k + 1])
		return

	def apply_node_lazy(self, k, op):
		self.node[k] = self.oper(op, self.node[k])
		if k < self.n:
			self.lazy[k] = self.comp(op, self.lazy[k])
		return

	def push(self, k):
		self.apply_node_lazy(2 * k, self.lazy[k])
		self.apply_node_lazy(2 * k + 1, self.lazy[k])
		self.lazy[k] = self.idem
		return

	def set(self, k, x):
		k += self.n
		for i in range(self.hght, 0, -1):
			self.push(k >> i)

		self.node[k] = x
		
		while k > 1:
			k >>= 1
			self.update(k)
		return

	def get(self, k):
		k += self.n
		for i in range(self.hght, 0, -1):
			self.push(k >> i)
		
		return self.node[k]

	#[l, r)
	def prod(self, l, r):
		if l == r:
			return self.unit
		l += self.n
		r += self.n
		
		for i in range(self.hght, 0, -1):
			if ((l >> i) << i) != l:
				self.push(l >> i)
			if ((r >> i) << r) != r:
				self.push(r >> i)

		s_l, s_r = self.unit, self.unit
		while l < r:
			if l & 1:
				s_l = self.func(s_l, self.node[l])
				l += 1
			if r & 1:
				r -= 1
				s_r = self.func(self.node[r], s_r)
			l >>= 1
			r >>= 1
		return self.func(s_l, s_r)

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

	def point_apply(self, k, op):
		k += self.n
		for i in range(self.hght, 0, -1):
			self.push(k >> i)
		
		self.node[k] = self.oper(op, self.node[k])
		
		while k > 1:
			k >>= 1
			self.update(k)
		return

	#operate to [l, r)
	def apply(self, l, r, op):
		if l == r:
			return
		l += self.n
		r += self.n
		
		for i in range(self.hght, 0, -1):
			if ((l >> i) << i != l):
				self.push(l >> i)
			if ((r >> i) << i != r):
				self.push((r - 1) >> i)

		l_pres, r_pres = l, r
		while l < r:
			if l & 1:
				self.apply_node_lazy(l, op)
				l += 1
			if r & 1:
				r -= 1
				self.apply_node_lazy(r, op)
			l >>= 1
			r >>= 1
		l, r = l_pres, r_pres

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

	#maximum of r (within [l, n)) which satisfies val(prod(l, r))
	def max_right(self, l, val):
		if l == self.size:
			return self.size
		l += self.n
		for i in range(self.hght, 0, -1):
			self.push(l >> i)

		s = self.unit
		while True:
			while l % 2 == 0:
				l >>= 1
			if not val(self.func(s, self.node[l])):
				while l < self.n:
					self.push(l) #before descending
					l <<= 1
					if val(self.func(s, self.node[l])):
						s = self.func(s, self.node[l])
						l += 1
				return l - self.n
			s = self.func(s, self.node[l])
			l += 1
			if (l & -l) == l:
				return self.size

	#minimum of l (within [0, r)) which satisfies val(prod(l, r))
	def min_left(self, r, val):
		if r == 0:
			return 0
		r += self.n
		for i in range(self.hght, 0, -1):
			self.push((r - 1) >> i)

		s = self.unit
		while True:
			r -= 1
			while r > 1 and r % 2:
				r >>= 1
			if not val(self.func(self.node[r], s)):
				while r < self.n:
					self.push(r) #before descending
					r = (r << 1) + 1
					if val(self.func(self.node[r], s)):
						s = self.func(self.node[r], s)
						r -= 1
				return r + 1 - self.n
			s = self.func(self.node[r], s)
			if (r & -r) == r:
				return 0

def func(x, y):
	return ((x[0] + y[0]) % MOD, x[1] + y[1])

unit = (0, 1)

def oper(f, x):
	return ((f[0] * x[0] + f[1] * x[1]) % MOD, x[1])

def comp(f, g):
	return ((f[0] * g[0]) % MOD, (f[0] * g[1] + f[1]) % MOD)

idem = (1, 0)

n, q = map(int, input().split())
a = list(map(int, input().split()))
st = LazySegTree([(x, 1) for x in a], func, unit, oper, comp, idem)
for _ in range(q):
	query = list(map(int, input().split()))
	if query[0] == 0:
		_, l, r, b, c = query
		st.apply(l, r, (b, c))
	else:
		_, l, r = query
		print(st.prod(l, r)[0])

Submission status: Time Limit Exceeded

Solution code:
class LazySegmentTree():
    def __init__(self, n, op, e, mapping, composition, id):
        self.n = n
        self.op = op
        self.e = e
        self.mapping = mapping
        self.composition = composition
        self.id = id
        self.log = (n - 1).bit_length()
        self.size = 1 << self.log
        self.d = [e] * (2 * self.size)
        self.lz = [id] * (self.size)

    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.id

    def build(self, arr):
        assert len(arr) == self.n
        for i in range(self.n):
            self.d[self.size + i] = arr[i]
        for i in range(1, self.size)[::-1]:
            self.update(i)

    def set(self, p, x):
        assert 0 <= p < self.n
        p += self.size
        for i in range(1, self.log + 1)[::-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):
        assert 0 <= p < self.n
        p += self.size
        for i in range(1, self.log + 1):
            self.push(p >> i)
        return self.d[p]

    def prod(self, l, r):
        assert 0 <= l <= r <= self.n
        if l == r: return self.e
        l += self.size
        r += self.size
        for i in range(1, self.log + 1)[::-1]:
            if ((l >> i) << i) != l: self.push(l >> i)
            if ((r >> i) << i) != r: self.push(r >> i)
        sml = 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):
        assert 0 <= p < self.n
        p += self.size
        for i in range(1, self.log + 1)[::-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):
        assert 0 <= l <= r <= self.n
        if l == r: return
        l += self.size
        r += self.size
        for i in range(1, self.log + 1)[::-1]:
            if ((l >> i) << i) != l: self.push(l >> i)
            if ((r >> i) << i) != r: self.push((r - 1) >> i)
        l2 = l
        r2 = 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 = l2
        r = 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):
        #assert 0 <= l <= self.n
        #assert g(self.e)
        if l == self.n: return self.n
        l += self.size
        for i in range(1, self.log + 1)[::-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])):
                while l < self.size:
                    self.push(l)
                    l = 2 * l
                    if g(self.op(sm, self.d[l])):
                        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: return self.n

    def min_left(self, r, g):
        #assert 0 <= r <= self.n
        #assert g(self.e)
        if r == 0: return 0
        r += self.size
        for i in range(1, self.log + 1)[::-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)):
                while r < self.size:
                    self.push(r)
                    r = 2 * r + 1
                    if g(self.op(self.d[r], sm)):
                        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: return 0

import sys
input = sys.stdin.readline

MOD = 998244353

e = (0, 0)
id = (1, 0)

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

op = lambda l, r: ((l[0] + r[0]) % MOD, (l[1] + r[1]) % MOD)
mapping = lambda l, r: ((r[0] * l[0] + r[1] * l[1]) % MOD, r[1])
composition = lambda l, r: ((r[0] * l[0]) % MOD, (r[1] * l[0] + l[1]) % MOD)

lst = LazySegmentTree(N, op, e, mapping, composition, id)
lst.build(A)

res = []

for _ in range(Q):
    q = tuple(map(int, input().split()))
    if q[0] == 0:
        _, l, r, b, c = q
        lst.range_apply(l, r, (b, c))
    else:
        _, l, r = q
        res.append(lst.prod(l, r)[0])

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

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline

class LazySegmentTree:
    def __init__(self, n, func1, func2, func3, func4, e1, e2, arrange=None):
        self.init(n)
        self.func1 = func1
        self.func2 = func2
        self.func3 = func3
        self.func4 = func4
        self.e1 = e1
        self.e2 = e2
        self.make_arrange(arrange)
        self.lazy = [self.e2]*self.size
    
    def init(self, n):
        self.inf = pow(2, 32)
        self.n = n
        self.N = 1
        while self.N < self.n:
            self.N *= 2
        self.size = self.N * 2 - 1
        self.N -= 1
    
    def make_arrange(self, arrange):
        self.set_arrange(arrange)
        self.construct(arrange)

    def set_arrange(self, arrange):
        if arrange == None:
            self.segment = [self.e1]*self.size
            return
        self.segment = [0]*(self.N) + arrange + [self.e1]*(self.size-self.N-self.n)
    
    def construct(self, arrange):
        if arrange == None:
            return
        for i in range(self.N-1, -1, -1):
            self.segment[i] = self.func1(self.segment[2*i+1], self.segment[2*i+2])
    
    def evaluate(self, i, length):
        if self.lazy[i] == self.e2:
            return
        if i < self.size-self.N-1:
            self.lazy[2*i+1] = self.func2(self.lazy[2*i+1], self.lazy[i])
            self.lazy[2*i+2] = self.func2(self.lazy[2*i+2], self.lazy[i])
        self.segment[i] = self.func3(self.segment[i], self.func4(self.lazy[i], length))
        self.lazy[i] = self.e2
    
    def update_sub(self, a, b, x, k, l, r):
        self.evaluate(k, r-l)
        if a <= l and r <= b:
            self.lazy[k] = self.func2(self.lazy[k], x)
            self.evaluate(k, r-l)
        elif a < r and l < b:
            self.update_sub(a, b, x, 2*k+1, l, (l+r)//2)
            self.update_sub(a, b, x, 2*k+2, (l+r)//2, r)
            self.segment[k] = self.func1(self.segment[k*2+1], self.segment[k*2+2])
    
    def update(self, a, b, x):
        self.update_sub(a-1, b, x, 0, 0, self.size-self.N)
    
    def find(self, a, b, k, l, r):
        self.evaluate(k, r-l)
        if r <= a or b <= l:
            return self.e1
        elif a <= l and r <= b:
            return self.segment[k]
        else:
            find_l = self.find(a, b, 2*k+1, l, (l+r)//2)
            find_r = self.find(a, b, 2*k+2, (l+r)//2, r)
            res = self.func1(find_l, find_r)
            return res

    def count(self, l, r):
        return self.find(l-1, r, 0, 0, self.size-self.N)


def main():
    n, q = map(int, input().split())
    a = list(map(int, input().split()))

    mod = 998244353
    lim = 1 << 32

    func1 = lambda x, y: (x + y) % mod
    func2 = lambda a1, a2: (((a1 >> 32) * (a2 >> 32) % mod) << 32) + (((a1 % lim) * (a2 >> 32) + (a2 % lim)) % mod)
    func3 = lambda x, a: ((a >> 32) * x + (a % lim)) % mod
    func4 = lambda x, n: ((x >> 32) << 32) + (x % lim) * n % mod
    e1 = 0
    e2 = (1 << 32)

    segment = LazySegmentTree(n, func1, func2, func3, func4, e1, e2, arrange=a)

    for i in range(q):
        query = list(map(int, input().split()))
        if query[0] == 0:
            l, r, b, c = query[1:]
            segment.update(l+1, r, (b << 32)+c)
        else:
            l, r = query[1:]
            res = segment.count(l+1, r)
            print(res)

    
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline


class LazySegmentTree:
    def __init__(self, n, func1, func2, func3, func4, e1, e2, arrange=None):
        self.init(n)
        self.func1 = func1
        self.func2 = func2
        self.func3 = func3
        self.func4 = func4
        self.e1 = e1
        self.e2 = e2
        self.make_arrange(arrange)
        self.lazy = [self.e2]*self.size
    
    def init(self, n):
        self.inf = pow(2, 32)
        self.n = n
        self.N = 1
        while self.N < self.n:
            self.N *= 2
        self.size = self.N * 2 - 1
        self.N -= 1
    
    def make_arrange(self, arrange):
        self.set_arrange(arrange)
        self.construct(arrange)

    def set_arrange(self, arrange):
        if arrange == None:
            self.segment = [self.e1]*self.size
            return
        self.segment = [0]*(self.N) + arrange + [self.e1]*(self.size-self.N-self.n)
    
    def construct(self, arrange):
        if arrange == None:
            return
        for i in range(self.N-1, -1, -1):
            self.segment[i] = self.func1(self.segment[2*i+1], self.segment[2*i+2])
    
    def evaluate(self, i, length):
        if self.lazy[i] == self.e2:
            return
        if i < self.size-self.N-1:
            self.lazy[2*i+1] = self.func2(self.lazy[2*i+1], self.lazy[i])
            self.lazy[2*i+2] = self.func2(self.lazy[2*i+2], self.lazy[i])
        self.segment[i] = self.func3(self.segment[i], self.func4(self.lazy[i], length))
        self.lazy[i] = self.e2
    
    def update_sub(self, a, b, x, k, l, r):
        self.evaluate(k, r-l)
        if a <= l and r <= b:
            self.lazy[k] = self.func2(self.lazy[k], x)
            self.evaluate(k, r-l)
        elif a < r and l < b:
            self.update_sub(a, b, x, 2*k+1, l, (l+r)//2)
            self.update_sub(a, b, x, 2*k+2, (l+r)//2, r)
            self.segment[k] = self.func1(self.segment[k*2+1], self.segment[k*2+2])
    
    def update(self, a, b, x):
        self.update_sub(a-1, b, x, 0, 0, self.size-self.N)
    
    def find(self, a, b, k, l, r):
        self.evaluate(k, r-l)
        if r <= a or b <= l:
            return self.e1
        elif a <= l and r <= b:
            return self.segment[k]
        else:
            find_l = self.find(a, b, 2*k+1, l, (l+r)//2)
            find_r = self.find(a, b, 2*k+2, (l+r)//2, r)
            res = self.func1(find_l, find_r)
            return res

    def count(self, l, r):
        return self.find(l-1, r, 0, 0, self.size-self.N)


def main():
    n, q = map(int, input().split())
    a = list(map(int, input().split()))

    mod = 998244353

    func1 = lambda x, y: (x + y) % mod
    func2 = lambda a1, a2: [a1[0] * a2[0] % mod, (a1[1] * a2[0] + a2[1]) % mod]
    func3 = lambda x, a: (a[0] * x + a[1]) % mod
    func4 = lambda x, n: [x[0], x[1] * n % mod]
    e1 = 0
    e2 = [1, 0]

    segment = LazySegmentTree(n, func1, func2, func3, func4, e1, e2, arrange=a)

    for i in range(q):
        query = list(map(int, input().split()))
        if query[0] == 0:
            l, r, b, c = query[1:]
            segment.update(l+1, r, [b, c])
        else:
            l, r = query[1:]
            res = segment.count(l+1, r)
            print(res)

    
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
class LazySegmentTree():
    def __init__(self, op, e, mapping, composition, ie, init_array):
        self.op = op
        self.e = e
        self.mapping = mapping
        self.composition = composition
        self.ie = ie

        l = len(init_array)
        def ceil_pow2(n):
            x = 0
            while (1 << x) < n:
                x += 1
            return x
        self.log = ceil_pow2(l)
        self.size = 1 << self.log

        self.d = [e() for _ in range(2*self.size)]
        self.lz = [ie() for _ in range(self.size)]

        for i, a in enumerate(init_array):
            self.d[i+self.size] = a

        for i in range(self.size-1, 0, -1):
            self.__update(i)

    def set(self, p, x):
        p += self.size

        for i in range(self.log, 0, -1):
            self.__push(p >> i)

        self.d[p] = x

        for i in range(1, self.log+1):
            self.__update(p >> i)

    def __getitem__(self, p):
        p += self.size
        for i in range(self.log, 0, -1):
            self.__push(p >> i)
        return self.d[p]

    def prod(self, l, r):
        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 = 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 apply(self, p, f):
    #     p += self.size

    #     for i in range(self.h, 0, -1):
    #         self.__push(p >> i)

    #     self.d[p] = self.mapping(f, self.d[p])

    #     for i in range(1, self.h+1):
    #         self.__update(p >> i)

    def apply(self, l, r, f):
        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)

        l2 = l
        r2 = 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 = l2
        r = 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 __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.ie()

MOD = 998244353


def op(l, r): return ((l[0] + r[0]) % MOD, (l[1] + r[1]) % MOD)


def e(): return (0, 0)


def mapping(l, r): return ((r[0] * l[0] + r[1] * l[1]) % MOD, r[1])


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


def ie(): return (1, 0)

def atcoder_practice_k():
    import sys
    input = sys.stdin.buffer.readline
    N, Q = map(int, input().split())
    A = list(map(lambda x: (int(x), 1), input().split()))



    st = LazySegmentTree(op, e, mapping, composition, ie, A)
    for _ in range(Q):
        k, *q  = map(int, input().split())
        if k == 0:
            l, r, b, c = q
            st.apply(l, r, (b, c))
        else:
            l, r = q
            a = st.prod(l, r)
            print(a[0])


if __name__ == "__main__":
    atcoder_practice_k()

Submission status: Time Limit Exceeded

Solution code:

# base
# https://beet-aizu.github.io/library/library/segtree/basic/chien.cpp.html
# https://beet-aizu.hatenablog.com/entry/2017/12/01/225955

class LazySegmentTree():
    def __init__(self, op, e, mapping, composition, ie, init_array):
        self.op = op
        self.e = e
        self.mapping = mapping
        self.composition = composition
        self.ie = ie

        l = len(init_array)
        def ceil_pow2(n):
            x = 0
            while (1 << x) < n:
                x += 1
            return x
        self.h = ceil_pow2(l)
        self.size = 1 << self.h
        # self.size = 1 << (l - 1).bit_length()
        # self.h = self.size.bit_length()

        self.d = [self.e() for _ in range(2*self.size)]
        self.lz = [self.ie() for _ in range(self.size)]
        for i, a in enumerate(init_array):
            self.d[i+self.size] = a

        for i in range(self.size-1, 0, -1):
            self.__update(i)

    def set(self, p, x):
        p += self.size

        for i in range(self.h, 0, -1):
            self.__push(p >> i)

        self.d[p] = x

        for i in range(1, self.h+1):
            self.__update(p >> i)

    def __getitem__(self, p):
        p += self.size
        for i in range(self.h, 0, -1):
            self.__push(p >> i)
        return self.d[p]

    def prod(self, l, r):
        if l == r:
            return self.e()

        l += self.size
        r += self.size

        for i in range(self.h, 0, -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 apply(self, p, f):
    #     p += self.size

    #     for i in range(self.h, 0, -1):
    #         self.__push(p >> i)

    #     self.d[p] = self.mapping(f, self.d[p])

    #     for i in range(1, self.h+1):
    #         self.__update(p >> i)

    def apply(self, l, r, f):
        if l == r:
            return

        l += self.size
        r += self.size

        for i in range(self.h, 0, -1):
            if ((l >> i) << i) != l:
                self.__push(l >> i)
            if ((r >> i) << i) != r:
                self.__push((r-1) >> i)

        l2 = l
        r2 = 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 = l2
        r = r2

        for i in range(1, self.h+1):
            if ((l >> i) << i) != l:
                self.__update(l >> i)
            if ((r >> i) << i) != r:
                self.__update((r-1) >> 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.ie()


def atcoder_practice_k():
    N, Q = map(int, input().split())
    A = list(map(lambda x: (int(x), 1), input().split()))
    M = 998244353
    op = lambda l, r: ((l[0] + r[0])%M, (l[1] + r[1])%M)
    e = lambda: (0, 0)
    mapping = lambda l, r: ((r[0] * l[0] + r[1] * l[1])%M, r[1])
    composition = lambda l, r: ((r[0] * l[0])%M, (r[1] * l[0] + l[1])%M)
    ie = lambda: (1, 0)

    st = LazySegmentTree(op, e, mapping, composition, ie, A)
    for _ in range(Q):
        k, *q  = map(int, input().split())
        if k == 0:
            l, r, b, c = q
            st.apply(l, r, (b, c))
        else:
            l, r = q
            a = st.prod(l, r)
            print(a[0])


if __name__ == "__main__":
    atcoder_practice_k()

Submission status: Time Limit Exceeded

Solution code:

# base
# https://beet-aizu.github.io/library/library/segtree/basic/chien.cpp.html
# https://beet-aizu.hatenablog.com/entry/2017/12/01/225955

class LazySegmentTree():
    def __init__(self, op, e, mapping, composition, ie, init_array):
        self.op = op
        self.e = e
        self.mapping = mapping
        self.composition = composition
        self.ie = ie

        l = len(init_array)
        self.size = 1 << (l - 1).bit_length()
        self.h = self.size.bit_length()

        self.d = [self.e() for _ in range(2*self.size)]
        self.lz = [self.ie() for _ in range(self.size)]
        for i, a in enumerate(init_array):
            self.d[i+self.size] = a

        for i in range(self.size-1, 0, -1):
            self.__update(i)

    def set(self, p, x):
        p += self.size

        for i in range(self.h, 0, -1):
            self.__push(p >> i)

        self.d[p] = x

        for i in range(1, self.h+1):
            self.__update(p >> i)

    def __getitem__(self, p):
        p += self.size
        for i in range(self.h, 0, -1):
            self.__push(p >> i)
        return self.d[p]

    def prod(self, l, r):
        if l == r:
            return self.e()

        l += self.size
        r += self.size

        for i in range(self.h, 0, -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 apply(self, p, f):
    #     p += self.size

    #     for i in range(self.h, 0, -1):
    #         self.__push(p >> i)

    #     self.d[p] = self.mapping(f, self.d[p])

    #     for i in range(1, self.h+1):
    #         self.__update(p >> i)

    def apply(self, l, r, f):
        if l == r:
            return

        l += self.size
        r += self.size

        for i in range(self.h, 0, -1):
            if ((l >> i) << i) != l:
                self.__push(l >> i)
            if ((r >> i) << i) != r:
                self.__push((r-1) >> i)

        l2 = l
        r2 = 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 = l2
        r = r2

        for i in range(1, self.h+1):
            if ((l >> i) << i) != l:
                self.__update(l >> i)
            if ((r >> i) << i) != r:
                self.__update((r-1) >> 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.ie()


def atcoder_practice_k():
    N, Q = map(int, input().split())
    A = list(map(lambda x: (int(x), 1), input().split()))
    M = 998244353
    op = lambda l, r: ((l[0] + r[0])%M, (l[1] + r[1])%M)
    e = lambda: (0, 0)
    mapping = lambda l, r: ((r[0] * l[0] + r[1] * l[1])%M, r[1])
    composition = lambda l, r: ((r[0] * l[0])%M, (r[1] * l[0] + l[1])%M)
    ie = lambda: (1, 0)

    st = LazySegmentTree(op, e, mapping, composition, ie, A)
    for _ in range(Q):
        k, *q  = map(int, input().split())
        if k == 0:
            l, r, b, c = q
            st.apply(l, r, (b, c))
        else:
            l, r = q
            a = st.prod(l, r)
            print(a[0])


if __name__ == "__main__":
    atcoder_practice_k()