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: Wrong Answer

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 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 = list(map(int, input().split()))
  Query = [list(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, (f[1] * g[0] + g[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: Wrong Answer

Solution code:
#自前ModInt
class ModInt:
  MOD = 10 ** 9 + 7
  def __init__(s, x):
    s.x = x % type(s).MOD

  @classmethod
  def set_mod(c, m):
    c.MOD = m

  def inv(s):
    return type(s)(pow(s.x, type(s).MOD - 2, type(s).MOD))

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

  __repr__ = __str__

  def __add__(s, t):
    return type(s)(s.x + t.x) if isinstance(t, ModInt) else type(s)(s.x + t)

  def __sub__(s, t):
    return type(s)(s.x - t.x) if isinstance(t, ModInt) else type(s)(s.x - t)

  def __mul__(s, t):
    return type(s)(s.x * t.x) if isinstance(t, ModInt) else type(s)(s.x * t)

  def __truediv__(s, t):
    return type(s)(s.x * pow(t.x, type(s).MOD - 2, type(s).MOD)) if isinstance(t, ModInt) else type(s)(s.x * pow(t, type(s).MOD - 2, type(s).MOD))

  def __pow__(s, t):
    return type(s)(pow(s.x, t.x, type(s).MOD)) if isinstance(t, ModInt) else type(s)(pow(s.x, t, type(s).MOD))

  __radd__ = __add__

  def __rsub__(s, t):
    return type(s)(t.x - s.x) if isinstance(t, ModInt) else type(s)(t - s.x)

  __rmul__ = __mul__

  def __rtruediv__(s, t):
    return type(s)(t.x * pow(s.x, type(s).MOD - 2, type(s).MOD)) if isinstance(t, ModInt) else type(s)(t * pow(s.x, type(s).MOD - 2, type(s).MOD))


  def __rpow__(s, t):
    return type(s)(pow(t.x, s.x, type(s).MOD)) if isinstance(t, ModInt) else type(s)(pow(t, s.x, type(s).MOD))

  def __eq__(s, t):
    return s.x == t.x

  def __lt__(s, t):
    return s.x < t.x

  def __le__(s, t):
    return s.x <= t.x

  def __gt__(s, t):
    return s.x > t.x

  def __ge__(s, t):
    return s.x >= t.x

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 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
  N, Q = list(map(int, input().split()))
  a = tuple(map(ModInt, (map(int, input().split()))))
  Query = [list(map(int, input().split())) for _ in range(Q)]

  ModInt.set_mod(998244353)
 
  def e():
    return [ModInt(0), ModInt(0)]

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

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

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

  def id():
    return [1, 0]

  _ = 0

  a = [(i, ModInt(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, (ModInt(b), ModInt(c)))

    else:
      _, l, r = q
      print(seg.prod(l, r)[0])

main()

Submission status: Wrong Answer

Solution code:
#サンプル通らね～～～記録用

#自前ModInt
class ModInt:
  MOD = 10 ** 9 + 7
  def __init__(s, x):
    s.x = x % type(s).MOD

  @classmethod
  def set_mod(c, m):
    c.MOD = m

  def inv(s):
    return type(s)(pow(s.x, type(s).MOD - 2, type(s).MOD))

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

  __repr__ = __str__

  def __add__(s, t):
    return type(s)(s.x + t.x) if isinstance(t, ModInt) else type(s)(s.x + t)

  def __sub__(s, t):
    return type(s)(s.x - t.x) if isinstance(t, ModInt) else type(s)(s.x - t)

  def __mul__(s, t):
    return type(s)(s.x * t.x) if isinstance(t, ModInt) else type(s)(s.x * t)

  def __truediv__(s, t):
    return type(s)(s.x * pow(t.x, type(s).MOD - 2, type(s).MOD)) if isinstance(t, ModInt) else type(s)(s.x * pow(t, type(s).MOD - 2, type(s).MOD))

  def __pow__(s, t):
    return type(s)(pow(s.x, t.x, type(s).MOD)) if isinstance(t, ModInt) else type(s)(pow(s.x, t, type(s).MOD))

  __radd__ = __add__

  def __rsub__(s, t):
    return type(s)(t.x - s.x) if isinstance(t, ModInt) else type(s)(t - s.x)

  __rmul__ = __mul__

  def __rtruediv__(s, t):
    return type(s)(t.x * pow(s.x, type(s).MOD - 2, type(s).MOD)) if isinstance(t, ModInt) else type(s)(t * pow(s.x, type(s).MOD - 2, type(s).MOD))


  def __rpow__(s, t):
    return type(s)(pow(t.x, s.x, type(s).MOD)) if isinstance(t, ModInt) else type(s)(pow(t, s.x, type(s).MOD))

  def __eq__(s, t):
    return s.x == t.x

  def __lt__(s, t):
    return s.x < t.x

  def __le__(s, t):
    return s.x <= t.x

  def __gt__(s, t):
    return s.x > t.x

  def __ge__(s, t):
    return s.x >= t.x

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 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
  N, Q = list(map(int, input().split()))
  a = list(map(ModInt, (map(int, input().split()))))
  Query = [list(map(int, input().split())) for _ in range(Q)]

  ModInt.set_mod = 998244353
 
  def e():
    return [ModInt(0), ModInt(0)]

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

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

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

  def id():
    return [1, 0]

  _ = 0

  a = [[i, ModInt(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, [ModInt(b), ModInt(c)])

    else:
      _, l, r = q
      print(seg.prod(l, r)[0])

main()

Submission status: Wrong Answer

Solution code:
#サンプル通らね～～～記録用

#自前ModInt
class ModInt:
  MOD = 10 ** 9 + 7
  def __init__(s, x):
    s.x = x % type(s).MOD

  @classmethod
  def set_mod(c, m):
    c.MOD = m

  def inv(s):
    return type(s)(pow(s.x, type(s).MOD - 2, type(s).MOD))

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

  __repr__ = __str__

  def __add__(s, t):
    return type(s)(s.x + t.x) if isinstance(t, ModInt) else type(s)(s.x + t)

  def __sub__(s, t):
    return type(s)(s.x - t.x) if isinstance(t, ModInt) else type(s)(s.x - t)

  def __mul__(s, t):
    return type(s)(s.x * t.x) if isinstance(t, ModInt) else type(s)(s.x * t)

  def __truediv__(s, t):
    return type(s)(s.x * pow(t.x, type(s).MOD - 2, type(s).MOD)) if isinstance(t, ModInt) else type(s)(s.x * pow(t, type(s).MOD - 2, type(s).MOD))

  def __pow__(s, t):
    return type(s)(pow(s.x, t.x, type(s).MOD)) if isinstance(t, ModInt) else type(s)(pow(s.x, t, type(s).MOD))

  __radd__ = __add__

  def __rsub__(s, t):
    return type(s)(t.x - s.x) if isinstance(t, ModInt) else type(s)(t - s.x)

  __rmul__ = __mul__

  def __rtruediv__(s, t):
    return type(s)(t.x * pow(s.x, type(s).MOD - 2, type(s).MOD)) if isinstance(t, ModInt) else type(s)(t * pow(s.x, type(s).MOD - 2, type(s).MOD))


  def __rpow__(s, t):
    return type(s)(pow(t.x, s.x, type(s).MOD)) if isinstance(t, ModInt) else type(s)(pow(t, s.x, type(s).MOD))

  def __eq__(s, t):
    return s.x == t.x

  def __lt__(s, t):
    return s.x < t.x

  def __le__(s, t):
    return s.x <= t.x

  def __gt__(s, t):
    return s.x > t.x

  def __ge__(s, t):
    return s.x >= t.x

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 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
  N, Q = list(map(int, input().split()))
  a = list(map(ModInt, (map(int, input().split()))))
  Query = [list(map(int, input().split())) for _ in range(Q)]

  ModInt.set_mod = 998244353
 
  def e():
    return [ModInt(0), ModInt(0)]

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

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

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

  def id():
    return [1, 0]

  _ = 0

  a = [[i, ModInt(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: Wrong Answer

Solution code:
# self.data: 1-indexed
#    __1__
#  _2_   _3_
# 4   5 6   7

# f(f(a, b), c) == f(a, f(b, c))

# This class is made for 'Range Affine Range Sum'.
class LazySegmentTree:
    # a = [default] * n
    # O(n)
    def __init__(self, n, default=0):
        self.num_leaf = 2 ** (n-1).bit_length()
        self.data = [default] * (2*self.num_leaf)
        self.lazy = [None] * (2*self.num_leaf)

    # You can use first_update before you use update.
    # a[i] = x
    # O(log(n))
    def first_update(self, i, x):
        i += self.num_leaf
        self.data[i] = x
        i >>= 1
        while i > 0:
            self.data[i] = (self.data[2*i] + self.data[2*i+1]) % 998244353
            i >>= 1

    def gindex(self, l, r):
        lis = []
        l += self.num_leaf
        r += self.num_leaf
        lm = (l // (l & -l)) >> 1
        rm = (r // (r & -r)) >> 1
        while l < r:
            if l <= lm:
                lis.append(l)
            if r <= rm:
                lis.append(r)
            l >>= 1
            r >>= 1
        while l:
            lis.append(l)
            l >>= 1
        lis.reverse()
        return lis

    # store (b, c) in self.lazy[i]
    def lazy_processing(self, i, b, c):
        self.data[i] = (b * self.data[i] + c) % 998244353
        if self.lazy[i] is None:
            self.lazy[i] = (b, c)
        else:
            self.lazy[i] = (b * self.lazy[i][0], b * self.lazy[i][1] + c)

    # from parent to children
    def propagate(self, lis):
        for i in lis:
            if self.lazy[i] is None:
                continue
            b, c = self.lazy[i]
            self.lazy_processing(2*i, b, c//2)
            self.lazy_processing(2*i+1, b, c//2)
            self.lazy[i] = None

    # update a[l:r]
    def update(self, l, r, b, c):
        lis = self.gindex(l, r)

        # top-down propagation
        self.propagate(lis)

        l += self.num_leaf
        r += self.num_leaf - 1
        while l < r:
            if l & 1:
                self.lazy_processing(l, b, c)
                l += 1
            if not r & 1:
                self.lazy_processing(r, b, c)
                r -= 1
            l >>= 1
            r >>= 1
            c *= 2
        if l == r:
            self.lazy_processing(l, b, c)

        # bottom-up propagation
        lis.reverse()
        for i in lis:
            self.data[i] = (self.data[2*i] + self.data[2*i+1]) % 998244353

    # return f(a[l:r])
    def query(self, l, r):
        # top-down propagation
        self.propagate(self.gindex(l, r))

        l += self.num_leaf
        r += self.num_leaf - 1
        lres, rres = self.data[0], self.data[0] # self.data[0] == default
        while l < r:
            if l & 1:
                lres = (lres + self.data[l]) % 998244353
                l += 1
            if not r & 1:
                rres = (self.data[r] + rres) % 998244353
                r -= 1
            l >>= 1
            r >>= 1
        if l == r:
            res = (lres + self.data[l] + rres) % 998244353
        else:
            res = (lres + rres) % 998244353
        return res

from sys import stdin
input = stdin.buffer.readline

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

    lst = LazySegmentTree(n)

    for i, x in enumerate(a):
        lst.first_update(i, x)

    ans = []
    for _ in range(q):
        que = list(map(int, input().split()))
        if que[0] == 0:
            lst.update(que[1], que[2], que[3], que[4])
        else:
            ans.append(lst.query(que[1], que[2]))

    for i in ans:
        print(i)

main()

Submission status: Wrong Answer

Solution code:
# self.data: 1-indexed
#    __1__
#  _2_   _3_
# 4   5 6   7

# f(f(a, b), c) == f(a, f(b, c))

# This class is made for 'Range Affine Range Sum'.
class LazySegmentTree:
    # a = [default] * n
    # O(n)
    def __init__(self, n, f=lambda x, y: (x + y) % 998244353, default=0):
        self.num_leaf = 2 ** (n-1).bit_length()
        self.data = [default] * (2*self.num_leaf)
        self.lazy = [None] * (2*self.num_leaf)
        self.f = f

    # You can use first_update before you use update.
    # a[i] = x
    # O(log(n))
    def first_update(self, i, x):
        i += self.num_leaf
        self.data[i] = x % 998244353
        i >>= 1
        while i > 0:
            self.data[i] = self.f(self.data[2*i], self.data[2*i+1])
            i >>= 1

    def gindex(self, l, r):
        lis = []
        l += self.num_leaf
        r += self.num_leaf
        lm = (l // (l & -l)) >> 1
        rm = (r // (r & -r)) >> 1
        while l < r:
            if l <= lm:
                lis.append(l)
            if r <= rm:
                lis.append(r)
            l >>= 1
            r >>= 1
        while l:
            lis.append(l)
            l >>= 1
        lis.reverse()
        return lis

    # store (b, c) in self.lazy[i]
    def lazy_processing(self, i, b, c):
        self.data[i] = (b * self.data[i] + c) % 998244353
        if self.lazy[i] is None:
            self.lazy[i] = (b, c)
        else:
            self.lazy[i] = (b * self.lazy[i][0], b * self.lazy[i][1] + c)

    # from parent to children
    def propagate(self, lis):
        for i in lis:
            if self.lazy[i] is None:
                continue
            b, c = self.lazy[i]
            self.lazy_processing(2*i, b, c//2)
            self.lazy_processing(2*i+1, b, c//2)
            self.lazy[i] = None

    # update a[l:r]
    def update(self, l, r, b, c):
        lis = self.gindex(l, r)

        # top-down propagation
        self.propagate(lis)

        l += self.num_leaf
        r += self.num_leaf - 1
        while l < r:
            if l & 1:
                self.lazy_processing(l, b, c)
                l += 1
            if not r & 1:
                self.lazy_processing(r, b, c)
                r -= 1
            l >>= 1
            r >>= 1
            c *= 2
        if l == r:
            self.lazy_processing(l, b, c)

        # bottom-up propagation
        lis.reverse()
        for i in lis:
            self.data[i] = self.f(self.data[2*i], self.data[2*i+1])

    # return f(a[l:r])
    def query(self, l, r):
        # top-down propagation
        self.propagate(self.gindex(l, r))

        l += self.num_leaf
        r += self.num_leaf - 1
        lres, rres = self.data[0], self.data[0] # self.data[0] == default
        while l < r:
            if l & 1:
                lres = self.f(lres, self.data[l])
                l += 1
            if not r & 1:
                rres = self.f(self.data[r], rres)
                r -= 1
            l >>= 1
            r >>= 1
        if l == r:
            res = self.f(self.f(lres, self.data[l]), rres)
        else:
            res = self.f(lres, rres)
        return res

from sys import stdin
input = stdin.buffer.readline

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

    lst = LazySegmentTree(n, f=lambda x, y: (x + y) % 998244353)

    for i, x in enumerate(a):
        lst.first_update(i, x)

    ans = []
    for _ in range(q):
        que = list(map(int, input().split()))
        if que[0] == 0:
            lst.update(que[1], que[2], que[3], que[4])
        else:
            ans.append(lst.query(que[1], que[2]))

    for i in ans:
        print(i)

main()