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:
#サンプル通らね～～～記録用

#自前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

def main():
  
  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)

  def op(s, t):
    return s + t

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

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

  def id():
    return [1, 0]

  _ = 0

  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))

main()

Submission status: Wrong Answer

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((3, n2 << 1), 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[1] >> 1
        table[0, offset:offset + len(arr)] = arr
        for i in range(offset - 1, 0, -1):
            ch = i << 1
            table[0, i] = (table[0, ch] + table[0, ch + 1]) % MOD

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

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

            segtree_eval(table, offset, i)

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

            if l <= a and b <= r:
                table[1, i] = table[1, i] * mul % MOD
                table[2, i] = (table[2, i] * 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

        # print('update', updated)

        while updated:
            i = updated.pop()
            lch = i << 1
            rch = lch + 1
            l_dat = (table[0, lch] * table[1, lch] + table[2, lch]) % MOD
            r_dat = (table[0, rch] * table[1, rch] + table[2, rch]) % MOD
            table[0, i] = (l_dat + r_dat) % MOD

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

        while si:
            i, a, b = stack[si - 3:si]
            # print('query', i, a, b)

            segtree_eval(table, offset, i)

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

            if l <= a and b <= r:
                res = (res + table[0, i]) % 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()
            lch = i << 1
            rch = lch + 1
            l_dat = (table[0, lch] * table[1, lch] + table[2, lch]) % MOD
            r_dat = (table[0, rch] * table[1, rch] + table[2, rch]) % MOD
            table[0, i] = (l_dat + r_dat) % MOD

        return res

    def segtree_debug_print(ins):
        table = SEGTREE_TABLES[ins]
        offset = table.shape[1] >> 1
        for t in range(3):
            i = 1
            while i <= offset:
                print(table[t, i:2 * i])
                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: 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, 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
        i >>= 1
        while i > 0:
            self.data[i] = self.f(self.data[2*i], self.data[2*i+1])
            i >>= 1

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

    def propagate_up(self, i):
        increase = (-self.data[i] + self.propagate_one(i)) % 998244353
        i >>= 1
        if i > 0:
            self.propagate_from_root(i)
        while i > 0:
            self.data[i] += increase
            self.data[i] %= 998244353
            i >>= 1

    # update a[l:r]
    def update(self, l, r, b, c):
        l += self.num_leaf
        r += self.num_leaf - 1
        while l < r:
            if l & 1:
                self.lazy_processing(l, b, c)
                self.propagate_up(l)
                l += 1
            if not r & 1:
                self.lazy_processing(r, b, c)
                self.propagate_up(r)
                r -= 1
            l >>= 1
            r >>= 1
            c *= 2
        if l == r:
            self.lazy_processing(l, b, c)
            self.propagate_up(l)

    def propagate_from_root(self, ind):
        history = [ind]
        while history[-1] > 1:
            history.append(history[-1] >> 1)
        for i in range(len(history)-1, -1, -1):
            self.propagate_one(history[i])

    def propagate_one(self, i):
        if self.lazy[i] != None:
            (b, c) = self.lazy[i]
            self.data[i] = b * self.data[i] + c
            if i < self.num_leaf:
                self.lazy_processing(2*i, b, c//2)
                self.lazy_processing(2*i+1, b, c//2)
            self.lazy[i] = None
        return self.data[i]

    # return f(a[l:r])
    def query(self, l, r):
        l += self.num_leaf
        r += self.num_leaf - 1
        self.propagate_from_root(l)
        self.propagate_from_root(r)
        lres, rres = self.data[0], self.data[0] # self.data[0] == default
        while l < r:
            if l & 1:
                lres = self.f(lres, self.propagate_one(l))
                l += 1
            if not r & 1:
                rres = self.f(self.propagate_one(r), rres)
                r -= 1
            l >>= 1
            r >>= 1
        if l == r:
            res = self.f(self.f(lres, self.propagate_one(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()

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, 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
        i >>= 1
        while i > 0:
            self.data[i] = self.f(self.data[2*i], self.data[2*i+1])
            i >>= 1

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

    def propagate_up(self, i):
        increase = -self.data[i] + self.propagate_one(i)
        i >>= 1
        if i > 0:
            self.propagate_from_root(i)
        while i > 0:
            self.data[i] += increase
            i >>= 1

    # update a[l:r]
    def update(self, l, r, b, c):
        l += self.num_leaf
        r += self.num_leaf - 1
        while l < r:
            if l & 1:
                self.lazy_processing(l, b, c)
                self.propagate_up(l)
                l += 1
            if not r & 1:
                self.lazy_processing(r, b, c)
                self.propagate_up(r)
                r -= 1
            l >>= 1
            r >>= 1
            c *= 2
        if l == r:
            self.lazy_processing(l, b, c)
            self.propagate_up(l)

    def propagate_from_root(self, ind):
        history = [ind]
        while history[-1] > 1:
            history.append(history[-1] >> 1)
        for i in range(len(history)-1, -1, -1):
            self.propagate_one(history[i])

    def propagate_one(self, i):
        if self.lazy[i] != None:
            (b, c) = self.lazy[i]
            self.data[i] = b * self.data[i] + c
            if i < self.num_leaf:
                self.lazy_processing(2*i, b, c//2)
                self.lazy_processing(2*i+1, b, c//2)
            self.lazy[i] = None
        return self.data[i]

    # return f(a[l:r])
    def query(self, l, r):
        l += self.num_leaf
        r += self.num_leaf - 1
        self.propagate_from_root(l)
        self.propagate_from_root(r)
        lres, rres = self.data[0], self.data[0] # self.data[0] == default
        while l < r:
            if l & 1:
                lres = self.f(lres, self.propagate_one(l))
                l += 1
            if not r & 1:
                rres = self.f(self.propagate_one(r), rres)
                r -= 1
            l >>= 1
            r >>= 1
        if l == r:
            res = self.f(self.f(lres, self.propagate_one(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()

Submission status: Wrong Answer

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.nb = self.N.bit_length()
        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
        """
        o1, o2 = ope>>32, ope&mask
        k = idx.bit_length()
        return (o1*self.data[idx] + o2*(1<<(self.nb-(k-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
mask = (1<<32) - 1
geta = 32
def fx(x, y):
    return (x+y)%MOD
def fm(o, p):
    o1, o2 = o>>32, o&mask
    p1, p2 = p>>32, p&mask
    return ((o1*p1%MOD)<<32) + (o1*p2 + o2)%MOD
    

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<<32)+c)
    else:
        l, r = map(int, s)
        Ans.append(T.query(l, r))

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

Submission status: Time Limit Exceeded

Solution code:
ide_ele=0
lazy_ele=1
mod=998244353
def segfunc(a,b):
  a1,a2=a
  b1,b2=b
  c1=(a1+b1)%mod
  c2=a2+b2
  return c1,c2
def op(a,x):
  a1,a2=a
  x1,x2=x
  c1=(a1*x1+a2*x2)%mod
  c2=a2
  return c1,c2
def merge(x,y):
  x1,x2=x
  y1,y2=y
  z1=(x1*y1)%mod
  z2=(x2*y1+y2)%mod
  return z1,z2
class lazysegmenttree():
  def __init__(self,init_val,func=segfunc,ie=ide_ele,le=lazy_ele,op=op,merge=merge):
    n=len(init_val)
    self.func=func
    self.op=op
    self.merge=merge
    self.ie=(ie,0)
    self.le=(le,0)
    self.h=(n-1).bit_length()
    self.num=1<<self.h
    self.tree=[self.ie]*self.num*2
    self.lazy=[self.le]*self.num*2
    for i in range(n):
      self.tree[i+self.num]=init_val[i]
    for i in range(self.num-1,0,-1):
      self.tree[i]=func(self.tree[2*i],self.tree[2*i+1])
  def reflect(self,k):
    if self.lazy[k]==self.le:return self.tree[k]
    return self.op(self.tree[k],self.lazy[k])
  def propagate(self,k):
    if self.lazy[k]==self.le:return
    self.lazy[2*k]=self.merge(self.lazy[2*k],self.lazy[k])
    self.lazy[2*k+1]=self.merge(self.lazy[2*k+1],self.lazy[k])
    self.tree[k]=self.reflect(k)
    self.lazy[k]=self.le
  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.tree[k]=self.func(self.reflect(2*k),self.reflect(2*k+1))
  def update(self,left_0,right_0,value_b,value_c):
    l=left_0+self.num
    r=right_0+self.num+1
    vl=l
    vr=r
    x=(value_b,value_c)
    self.thrust(l)
    self.thrust(r-1)
    while r-l>0:
      if l&1:
        self.lazy[l]=self.merge(self.lazy[l],x)
        l+=1
      if r&1:
        r-=1
        self.lazy[r]=self.merge(self.lazy[r],x)
      l>>=1
      r>>=1
    self.recalc(vl)
    self.recalc(vr-1)
  def query(self,left_0,right_0):
    l=left_0+self.num
    r=right_0+self.num+1
    self.thrust(l)
    self.thrust(r-1)
    vl=vr=self.ie
    while r-l>0:
      if l&1:
        vl=self.func(vl,self.reflect(l))
        l+=1
      if r&1:
        r-=1
        vr=self.func(self.reflect(r),vr)
      l>>=1
      r>>=1
    return self.func(vl,vr)[0]
n,q=map(int,input().split())
a=list(map(int,input().split()))
st=lazysegmenttree([(i,1) for i in a])
ans=[]
for _ in range(q):
  q,*p=map(int,input().split())
  if q:
    l,r=p
    ans+=[st.query(l,r-1)]
  else:
    l,r,b,c=p
    st.update(l,r-1,b,c)
print(*ans,sep='\n')

Submission status: Time Limit Exceeded

Solution code:
"""
遅延評価セグメント木
op(s, t)：二項演算の関数（実際に評価する値同士の演算）：現在の値の中での比較
composition(f, g)：二項演算の関数（遅延評価する値同士の演算）：どちらの値を遅延伝播するか決定
mapping(f, a)：二項演算の関数（二つの集合についての演算（ただし、X・Mの順））：現在の値と遅延評価により生じた値のどちらを採用するかを決定
rangeop(f, length)：範囲が関係してくるときに行う演算
e()：実際に評価する値の単位元
id()：遅延評価する値の単位元
update, find, bisect, 全てにおいて, 1-indexとなっている。
(大抵の場合、Atcoderの問題文の表記のままの値を、メソッドに代入すれば良い)
"""
import sys
input = sys.stdin.readline


class LazySegmentTree:
    #遅延評価セグメント木
    def __init__(s, op, e, mapping, composition, rangeop, 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.rangeop = rangeop
        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)

    def get_length(s, i):
        return pow(2, (s.size).bit_length() - (i).bit_length())
    # 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(s.d[p], f)
        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 s._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(s.d[k], s.rangeop(f, s.get_length(k)))
        if k < s.size: s.lz[k] = s.composition(s.lz[k], f)
    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


mod = 998244353
lim = 1 << 32

 
def func1(x, y):
    return (x + y) % mod

def func2(a1, a2):
    return (((a1 >> 32) * (a2 >> 32) % mod) << 32) + (((a1 % lim) * (a2 >> 32) + (a2 % lim)) % mod)

def func3(x, a):
    return ((a >> 32) * x + (a % lim)) % mod

def func4(x, n):
    return ((x >> 32) << 32) + (x % lim) * n % mod

def e1():
    return 0

def e2():
    return (1 << 32)


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

    segment = LazySegmentTree(func1, e1, func3, func2, func4, e2, a)
 
    ans = []
    for i in range(q):
        query = list(map(int, input().split()))
        if query[0] == 0:
            l, r, b, c = query[1:]
            segment.apply(l, r, (b << 32)+c)
        else:
            l, r = query[1:]
            res = segment.prod(l, r)
            ans.append(res)
    
    print(*ans, sep="\n")
 
    
if __name__ == "__main__":
    main()