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 = sys.stdin.buffer.readline
sys.setrecursionlimit(10**7)
from collections import defaultdict
mod = 998244353; INF = float("inf")
sec = pow(2, mod - 2, mod)

# 5 3
# 1 1 1 1 1
# 0 0 4 10 3
# 0 1 5 20 3
# 1 2 3

def getlist():
	return list(map(int, input().split()))

class lazySegTree(object):
	# N:処理する区間の長さ
	def __init__(self, N):
		self.N = N
		self.LV = (N - 1).bit_length()
		self.N0 = 2 ** self.LV
		self.initVal = 0
		self.data = [0] * (2 * self.N0)
		self.lazybeta = [1] * (2 * self.N0)
		self.lazy = [0] * (2 * self.N0)

	def calc(self, a, b):
		return a + b

	def initialize(self, A):
		for i in range(self.N):
			self.data[self.N0 - 1 + i] = A[i]
		for i in range(self.N0 - 2, -1, -1):
			self.data[i] = self.calc(self.data[2 * i + 1], self.data[2 * i + 2])

	def gindex(self, l, r):
		L = (l + self.N0) >> 1; R = (r + self.N0) >> 1
		lc = 0 if l & 1 else (L & -L).bit_length()
		rc = 0 if r & 1 else (R & -R).bit_length()
		for i in range(self.LV):
			if rc <= i:
				yield R
			if L < R and lc <= i:
				yield L
			L >>= 1; R >>= 1

	def propagates(self, *ids):
		for i in reversed(ids):
			w = self.lazybeta[i - 1]
			v = self.lazy[i - 1]
			if w == 1 and (not v):
				continue
			val = (v * sec) % mod
			self.lazybeta[2 * i - 1] = (self.lazybeta[2 * i - 1] * w) % mod
			self.lazybeta[2 * i] = (self.lazybeta[2 * i] * w) % mod
			self.lazy[2 * i - 1] = (self.lazy[2 * i - 1] * w + val) % mod
			self.lazy[2 * i] = (self.lazy[2 * i] * w + val) % mod
			self.data[2 * i - 1] = (self.data[2 * i - 1] * w + val) % mod
			self.data[2 * i] = (self.data[2 * i] * w + val) % mod
			self.lazybeta[i - 1] = 1; self.lazy[i - 1] = 0

	def update(self, l, r, b, c):
		# 1行にまとめてよい？
		*ids, = self.gindex(l, r + 1)
		self.propagates(*ids)

		L = self.N0 + l; R = self.N0 + r + 1
		v = c
		w = b
		while L < R:
			if R & 1:
				R -= 1
				self.lazybeta[R - 1] *= w; self.lazy[R - 1] = (w * self.lazy[R - 1] + v) % mod
				self.data[R - 1] = (self.data[R - 1] * w + v) % mod
			if L & 1:
				self.lazybeta[L - 1] *= w; self.lazy[L - 1] = (w * self.lazy[L - 1] + v) % mod
				self.data[L - 1] = (self.data[L - 1] * w + v) % mod
				L += 1
			L >>= 1; R >>= 1; v <<= 1
		for i in ids:
			self.data[i - 1] = self.calc(self.data[2 * i - 1], self.data[2 * i])

	def query(self, l, r):
		self.propagates(*self.gindex(l, r + 1))
		L = self.N0 + l; R = self.N0 + r + 1

		s = self.initVal
		while L < R:
			if R & 1:
				R -= 1
				s = self.calc(s, self.data[R - 1])
			if L & 1:
				s = self.calc(s, self.data[L - 1])
				L += 1
			L >>= 1; R >>= 1
		return s

def main():
	N, Q = getlist()
	A = getlist()
	lSeg = lazySegTree(N)
	lSeg.initialize(A)

	for _ in range(Q):
		q = getlist()
		if q[0] == 0:
			null, l, r, b, c = q
			lSeg.update(l, r - 1, b, c)
		else:
			null, l, r = q
			res = lSeg.query(l, r - 1)
			print(res % mod)
		# print(lSeg.data)
		# print(lSeg.lazybeta)
		# print(lSeg.lazy)



if __name__ == '__main__':
	main()

Submission status: Time Limit Exceeded

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

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

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

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

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

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

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

class RangeAffineRangeSum():
    def __init__(self, arr, mod=1000000007):
        self.mod = mod
        segarr = [a * mod + 1 for a in arr]
        ti = 0
        ei = mod
        def func(a, b):
            a1, a2 = divmod(a, mod)
            b1, b2 = divmod(b, mod)
            c1 = (a1 + b1) % mod
            c2 = (a2 + b2) % mod
            return c1 * mod + c2
        def op(a, x):
            a1, a2 = divmod(a, mod)
            x1, x2 = divmod(x, mod)
            c1 = (a1 * x1 + a2 * x2) % mod
            c2 = a2
            return c1 * mod + c2
        def merge(x, y):
            x1, x2 = divmod(x, mod)
            y1, y2 = divmod(y, mod)
            z1 = (x1 * y1) % mod
            z2 = (x2 * y1 + y2) % mod
            return z1 * mod + z2
        self.st = SegmentTreeLazy(segarr, ti, ei, func, op, merge)

    def add(self, lt, rt, x):
        self.st.update(lt, rt, self.mod + x)

    def mul(self, lt, rt, x):
        self.st.update(lt, rt, x * self.mod)

    def set(self, lt, rt, x):
        self.st.update(lt, rt, x)

    def sum(self, lt, rt):
        return self.st.query(lt, rt) // self.mod

import sys
input = sys.stdin.readline

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

rars = RangeAffineRangeSum(A, 998244353)
res = list()

for _ in range(Q):
    q, *p = map(int, input().split())
    if q == 0:
        l, r, b, c = p
        rars.mul(l, r, b)
        rars.add(l, r, c)
    else:
        l, r = p
        res.append(rars.sum(l, r))

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

Submission status: Time Limit Exceeded

Solution code:
class lazy_segtree:
  #遅延評価セグメント木
  def __init__(s, S, op, e, F, mapping, composition, id, v):
    if type(v) is int: v = [e()] * v
    s._n = len(v)
    s.log = s.ceil_pow2(s._n)
    s.size = 1 << s.log
    s.d = [e()] * (2 * s.size)
    s.lz = [id()] * s.size
    s.e = e
    s.op = op
    s.mapping = mapping
    s.composition = composition
    s.id = id
    for i in range(s._n): s.d[s.size + i] = v[i]
    for i in range(s.size - 1, 0, -1): s.update(i)
  
  # 1点更新
  def set(s, p, x):
    p += s.size
    for i in range(s.log, 0, -1): s.push(p >> i)
    s.d[p] = x
    for i in range(1, s.log + 1): s.update(p >> i)
 
  # 1点取得
  def get(s, p):
    p += s.size
    for i in range(s.log, 0, -1): s.push(p >> i)
    return s.d[p]
 
  # 区間演算
  def prod(s, l, r):
    if l == r: return s.e()
    l += s.size
    r += s.size
    for i in range(s.log, 0, -1):
      if (((l >> i) << i) != l): s.push(l >> i)
      if (((r >> i) << i) != r): s.push(r >> i)
    sml, smr = s.e(), s.e()
    while (l < r):
      if l & 1: 
        sml = s.op(sml, s.d[l])
        l += 1
      if r & 1:
        r -= 1
        smr = s.op(s.d[r], smr)
      l >>= 1
      r >>= 1
    return s.op(sml, smr)
 
  # 全体演算
  def all_prod(s): return s.d[1]
 
  # 1点写像
  def apply(s, p, f):
    p += s.size
    for i in range(s.log, 0, -1): s.push(p >> i)
    s.d[p] = s.mapping(f, s.d[p])
    for i in range(1, s.log + 1): s.update(p >> i)
 
  # 区間写像
  def apply(s, l, r, f):
    if l == r: return
    l += s.size
    r += s.size
    for i in range(s.log, 0, -1):
      if (((l >> i) << i) != l): s.push(l >> i)
      if (((r >> i) << i) != r): s.push((r - 1) >> i)
    l2, r2 = l, r
    while l < r:
      if l & 1: 
        sml = s.all_apply(l, f)
        l += 1
      if r & 1:
        r -= 1
        smr = s.all_apply(r, f)
      l >>= 1
      r >>= 1
    l, r = l2, r2
    for i in range(1, s.log + 1):
      if (((l >> i) << i) != l): s.update(l >> i)
      if (((r >> i) << i) != r): s.update((r - 1) >> i)
   
  # L固定時の最長区間のR
  def max_right(s, l, g):
    if l == s._n: return _n
    l += s.size
    for i in range(s.log, 0, -1): s.push(l >> i)
    sm = s.e()
    while True:
      while (l % 2 == 0): l >>= 1
      if not g(s.op(sm, s.d[l])):
        while l < s.size:
          s.push(l)
          l = 2 * l
          if g(s.op(sm, s.d[l])):
            sm = s.op(sm, s.d[l])
            l += 1
        return l - s.size
      sm = s.op(sm, s.d[l])
      l += 1
      if (l & -l) == l: break
    return s._n
 
  # R固定時の最長区間のL
  def min_left(s, r, g):
    if r == 0: return 0
    r += s.size
    for i in range(s.log, 0, -1): s.push((r - 1) >> i)
    sm = s.e()
    while True:
      r -= 1
      while r > 1 and (r % 2): r >>= 1
      if not g(s.op(s.d[r], sm)):
        while r < s.size:
          s.push(r)
          r = 2 * r + 1
          if g(s.op(s.d[r], sm)):
            sm = s.op(s.d[r], sm)
            r -= 1
        return r + 1 - s.size
      sm = s.op(s.d[r], sm)
      if (r & - r) == r: break
    return 0
 
  def update(s, k): s.d[k] = s.op(s.d[2 * k], s.d[2 * k + 1])
  def all_apply(s, k, f):
    s.d[k] = s.mapping(f, s.d[k])
    if k < s.size: s.lz[k] = s.composition(f, s.lz[k])
  def push(s, k):
    s.all_apply(2 * k, s.lz[k])
    s.all_apply(2 * k + 1, s.lz[k])
    s.lz[k] = s.id()
  def ceil_pow2(s, n):
    x = 0
    while (1 << x) < n: x += 1
    return x

import sys
def main():
  input = sys.stdin.readline
  MOD = 998244353

  N, Q = list(map(int, input().split()))
  a = tuple(map(int, input().split()))
  Query = (tuple(map(int, input().split())) for _ in range(Q))
 
  def e():
    return [0, 0]

  def op(s, t):
    return [(s[0] + t[0]) % MOD, s[1] + t[1]]

  def mapping(f, a):
    return [(f[0] * a[0] + f[1] * a[1]) % MOD, a[1]]

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

  def id():
    return [1, 0]

  _ = 0

  a = [(i, 1) for i in a]
  seg = lazy_segtree(_, op, e, _, mapping, composition, id, a)

  for q in Query:
    if q[0] == 0:
      _, l, r, b, c = q
      seg.apply(l, r, [b, c])
    else:
      _, l, r = q
      print(seg.prod(l, r)[0])

main()

Submission status: Time Limit Exceeded

Solution code:
I = [int(_) for _ in open(0).read().split()]
N, Q = I[:2]
A = I[2:2 + N]
Query = I[2 + N:]
idx = 0
lenQuery = len(Query)
mod = 998244353


class LazySegmentTree():
    def __init__(self, array, f, g, h, ti, ei):
        """
        Parameters
        ----------
        array : list
            to construct segment tree from
        f : func
            binary operation of the monoid
            T x T -> T
            T is dat
        g : func
            binary operation of the monoid
            T x E -> T
            T is dat, E is laz
        h : func
            binary operation of the monoid
            E x E -> T
            E is laz
        ti : T
            identity element of T
        ei : E
            identity element of E
        """
        self.f = f
        self.g = g
        self.h = h
        self.ti = ti
        self.ei = ei
        self.height = height = len(array).bit_length()
        self.n = n = 2**height
        self.dat = dat = [ti] * n + array + [ti] * (n - len(array))
        self.laz = [ei] * (2 * n)
        for i in range(n - 1, 0, -1):  # build
            dat[i] = f(dat[i << 1], dat[i << 1 | 1])

    def reflect(self, k):
        dat = self.dat
        ei = self.ei
        laz = self.laz
        g = self.g
        return self.dat[k] if laz[k] is ei else g(dat[k], laz[k])

    def evaluate(self, k):
        laz = self.laz
        ei = self.ei
        reflect = self.reflect
        dat = self.dat
        h = self.h
        if laz[k] is ei:
            return
        laz[(k << 1) | 0] = h(laz[(k << 1) | 0], laz[k])
        laz[(k << 1) | 1] = h(laz[(k << 1) | 1], laz[k])
        dat[k] = reflect(k)
        laz[k] = ei

    def thrust(self, k):
        height = self.height
        evaluate = self.evaluate
        for i in range(height, 0, -1):
            evaluate(k >> i)

    def recalc(self, k):
        dat = self.dat
        reflect = self.reflect
        f = self.f
        while k:
            k >>= 1
            dat[k] = f(reflect((k << 1) | 0), reflect((k << 1) | 1))

    def update(self, a, b, x):  # set value at position [a, b) (0-indexed)
        thrust = self.thrust
        n = self.n
        h = self.h
        laz = self.laz
        recalc = self.recalc
        a += n
        b += n - 1
        l = a
        r = b + 1
        thrust(a)
        thrust(b)
        while l < r:
            if l & 1:
                laz[l] = h(laz[l], x)
                l += 1
            if r & 1:
                r -= 1
                laz[r] = h(laz[r], x)
            l >>= 1
            r >>= 1
        recalc(a)
        recalc(b)

    def set_val(self, a, x):
        n = self.n
        thrust = self.thrust
        dat = self.dat
        laz = self.laz
        recalc = self.recalc
        ei = self.ei
        a += n
        thrust(a)
        dat[a] = x
        laz[a] = ei
        recalc(a)

    def query(self, a, b):  # result on interval [a, b) (0-indexed)
        f = self.f
        ti = self.ti
        n = self.n
        thrust = self.thrust
        reflect = self.reflect
        a += n
        b += n - 1
        thrust(a)
        thrust(b)
        l = a
        r = b + 1
        vl = vr = ti
        while l < r:
            if l & 1:
                vl = f(vl, reflect(l))
                l += 1
            if r & 1:
                r -= 1
                vr = f(reflect(r), vr)
            l >>= 1
            r >>= 1
        return f(vl, vr)


#general linear functions
array = [(a, 1) for a in A]
f = lambda a, b: ((a[0] + b[0]) % mod, a[1] + b[1])
g = lambda a, b: ((b[0] * a[0] + b[1] * a[1]) % mod, a[1])
h = lambda a, b: ((b[0] * a[0]) % mod, (b[0] * a[1] + b[1]) % mod)
ti = (0, 0)
ei = (1, 0)
# b[0] * (a[0] * x + a[1]) + b[1]
# = b[0] * a[0] * x + (b[0] * a[1] + b[1])

LST = LazySegmentTree(array=array, ti=ti, ei=ei, f=f, g=g, h=h)

while idx < lenQuery:
    if Query[idx]:
        l, r = Query[idx + 1:idx + 3]
        idx += 3
        print(LST.query(l, r)[0] % mod)
    else:
        l, r, b, c = Query[idx + 1:idx + 5]
        idx += 5
        LST.update(l, r, (b, c))

Submission status: Time Limit Exceeded

Solution code:
import os
import sys

import numpy as np


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

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

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

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

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

    def segtree_bottomup(table, i):
        ch = i << 1
        sub = table[ch:ch + 2]
        table[i, 0] = (sub[:, 0] * sub[:, 1] + sub[:, 2]).sum() % MOD

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

            segtree_eval(table, offset, i)

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

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

            updated.append(i)

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

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

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

        while si:
            i, a, b = stack[si - 3:si]

            segtree_eval(table, offset, i)

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

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

            updated.append(i)

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

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

        return res

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

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

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

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

    return ans


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

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

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

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

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

Submission status: Time Limit Exceeded

Solution code:
# 32を33にすると？

MOD = 998244353
mask33 = (1 << 33) - 1

class LazySegmentTree:

    __slots__ = ["n", "data", "lazy", "me", "oe", "fmm", "fmo", "foo"]

    def __init__(self, monoid_data, monoid_identity, operator_identity, func_monoid_monoid, func_monoid_operator, func_operator_operator):
        self.me = monoid_identity
        self.oe = operator_identity
        self.fmm = func_monoid_monoid
        self.fmo = func_monoid_operator
        self.foo = func_operator_operator

        self.n = len(monoid_data)
        self.data = monoid_data * 2
        for i in range(self.n-1, 0, -1):
            self.data[i] = self.fmm(self.data[2*i], self.data[2*i+1])
        self.lazy = [self.oe] * (self.n * 2)


    def replace(self, index, value):
        index += self.n

        # propagation
        for shift in range(index.bit_length()-1, 0, -1):
            i = index >> shift
            self.lazy[2*i]   = self.foo(self.lazy[2*i],   self.lazy[i])
            self.lazy[2*i+1] = self.foo(self.lazy[2*i+1], self.lazy[i])
            self.data[i] = self.fmo(self.data[i], self.lazy[i])
            self.lazy[i] = self.oe

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

        # recalculation
        i = index
        while i > 1:
            i //= 2
            self.data[i] = self.fmm( self.fmo(self.data[2*i], self.lazy[2*i]), self.fmo(self.data[2*i+1], self.lazy[2*i+1]) )
            self.lazy[i] = self.oe


    def effect(self, l, r, operator):
        l += self.n
        r += self.n
        l0 = l
        r0 = r - 1
        while l0 % 2 == 0:
            l0 //= 2
        while r0 % 2 == 1:
            r0 //= 2

        # propagation
        for shift in range(l0.bit_length()-1, 0, -1):
            i = l0 >> shift
            self.lazy[2*i]   = self.foo(self.lazy[2*i],   self.lazy[i])
            self.lazy[2*i+1] = self.foo(self.lazy[2*i+1], self.lazy[i])
            self.data[i] = self.fmo(self.data[i], self.lazy[i])
            self.lazy[i] = self.oe
        for shift in range(r0.bit_length()-1, 0, -1):
            i = r0 >> shift
            self.lazy[2*i]   = self.foo(self.lazy[2*i],   self.lazy[i])
            self.lazy[2*i+1] = self.foo(self.lazy[2*i+1], self.lazy[i])
            self.data[i] = self.fmo(self.data[i], self.lazy[i])
            self.lazy[i] = self.oe

        # effect
        while l < r:
            if l % 2:
                self.lazy[l] = self.foo(self.lazy[l], operator)
                l += 1
            if r % 2:
                r -= 1
                self.lazy[r] = self.foo(self.lazy[r], operator)
            l //= 2
            r //= 2

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

        # propagation
        for shift in range(l0.bit_length()-1, 0, -1):
            i = l0 >> shift
            self.lazy[2*i]   = self.foo(self.lazy[2*i],   self.lazy[i])
            self.lazy[2*i+1] = self.foo(self.lazy[2*i+1], self.lazy[i])
            self.data[i] = self.fmo(self.data[i], self.lazy[i])
            self.lazy[i] = self.oe
        for shift in range(r0.bit_length()-1, 0, -1):
            i = r0 >> shift
            self.lazy[2*i]   = self.foo(self.lazy[2*i],   self.lazy[i])
            self.lazy[2*i+1] = self.foo(self.lazy[2*i+1], self.lazy[i])
            self.data[i] = self.fmo(self.data[i], self.lazy[i])
            self.lazy[i] = self.oe

        # fold
        left_folded = self.me
        right_folded = self.me
        while l < r:
            if l % 2:
                left_folded = self.fmm(left_folded, self.fmo(self.data[l], self.lazy[l]))
                l += 1
            if r % 2:
                r -= 1
                right_folded = self.fmm(self.fmo(self.data[r], self.lazy[r]), right_folded)
            l //= 2
            r //= 2
        return self.fmm(left_folded, right_folded)



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

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

    def foo(o1, o2):
        b1 = o1 >> 33
        c1 = o1 & mask33
        b2 = o2 >> 33
        c2 = o2 & mask33
        b = b1 * b2 % MOD
        c = (c1 * b2 + c2) % MOD
        return (b << 33) + c

    N, Q = map(int, input().split())
    monoid_data = [(A << 33) + 1 for A in map(int, input().split())]
    lst = LazySegmentTree(monoid_data, 1, 1 << 33, fmm, fmo, foo)
    for _ in range(Q):
        q, *k = map(int, input().split())
        if q == 0:
            o = (k[2] << 33) + k[3]
            lst.effect(k[0], k[1], o)
        else:
            print(lst.folded(k[0], k[1]) >> 33)

if __name__ == "__main__":
    yosupo()

Submission status: Time Limit Exceeded

Solution code:
import sys
readline = sys.stdin.readline
class Lazysegtree:
    def __init__(self, A, fx, ex, fm, initialize = True):
        #作用の単位元をNoneにしている
        #fa(operator, idx)の形にしている、data[idx]の長さに依存する場合などのため
        self.N = len(A)
        self.N0 = 2**(self.N-1).bit_length()
        self.ex = ex
        self.fx = fx
        self.fm = fm
        self.lazy = [None]*(2*self.N0)
        if initialize:
            self.data = [self.ex]*self.N0 + A + [self.ex]*(self.N0 - self.N)
            for i in range(self.N0-1, -1, -1):
                self.data[i] = self.fx(self.data[2*i], self.data[2*i+1]) 
        else:
            self.data = [self.ex]*(2*self.N0)
    
    def fa(self, ope, idx):
        """
        TO WRITE
        """
        k = idx.bit_length()
        return (ope[0]*self.data[idx] + (self.N0>>(k-1))*ope[1])%MOD
        
    
    def __repr__(self):
        s = 'data'
        l = 'lazy'
        cnt = 1
        for i in range(self.N0.bit_length()):
            s = '\n'.join((s, ' '.join(map(str, self.data[cnt:cnt+(1<<i)]))))
            l = '\n'.join((l, ' '.join(map(str, self.lazy[cnt:cnt+(1<<i)]))))
            cnt += 1<<i
        return '\n'.join((s, l))
    
    def _ascend(self, k):
        k = k >> 1
        c = k.bit_length()
        for j in range(c):
            idx = k >> j
            self.data[idx] = self.fx(self.data[2*idx], self.data[2*idx+1])
            
    def _descend(self, k):
        k = k >> 1
        idx = 1
        c = k.bit_length()
        for j in range(1, c+1):
            idx = k >> (c - j)
            if self.lazy[idx] is None:
                continue
            self.data[2*idx] = self.fa(self.lazy[idx], 2*idx) 
            self.data[2*idx+1] = self.fa(self.lazy[idx], 2*idx+1)
            if self.lazy[2*idx] is not None:
                self.lazy[2*idx] = self.fm(self.lazy[idx], self.lazy[2*idx])
            else:
                self.lazy[2*idx] = self.lazy[idx]
            if self.lazy[2*idx+1] is not None:
                self.lazy[2*idx+1] = self.fm(self.lazy[idx], self.lazy[2*idx+1])
            else:
                self.lazy[2*idx+1] = self.lazy[idx]
            self.lazy[idx] = None
            
            
    def query(self, l, r):
        L = l+self.N0
        R = r+self.N0
        self._descend(L//(L & -L))
        self._descend(R//(R & -R)-1)
        
        sl = self.ex
        sr = self.ex                                                                   

        while L < R:
            if R & 1:
                R -= 1
                sr = self.fx(self.data[R], sr)
            if L & 1:
                sl = self.fx(sl, self.data[L])
                L += 1
            L >>= 1
            R >>= 1
        return self.fx(sl, sr)
    
    def operate(self, l, r, x):
        L = l+self.N0
        R = r+self.N0

        Li = L//(L & -L)
        Ri = R//(R & -R)
        self._descend(Li)
        self._descend(Ri-1)
        
        while L < R :
            if R & 1:
                R -= 1
                self.data[R] = self.fa(x, R)
                if self.lazy[R] is None:
                    self.lazy[R] = x
                else:
                    self.lazy[R] = self.fm(x, self.lazy[R])
            if L & 1:
                self.data[L] = self.fa(x, L)
                if self.lazy[L] is None:
                    self.lazy[L] = x
                else:
                    self.lazy[L] = self.fm(x, self.lazy[L])
                L += 1
            L >>= 1
            R >>= 1
        
        self._ascend(Li)
        self._ascend(Ri-1)

MOD = 998244353
def fx(x, y):
    return (x+y)%MOD
def fm(o, p):
    return (o[0]*p[0], o[0]*p[1] + o[1])
    

N, Q = map(int, readline().split())
A = list(map(int, readline().split()))

T = Lazysegtree(A, fx, 0, fm, initialize = True)

Ans = []
for _ in range(Q):
    t, *s = readline().split()
    if t == '0':
        l, r, b, c = map(int, s)
        T.operate(l, r, (b, c))
    else:
        l, r = map(int, s)
        Ans.append(T.query(l, r))

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