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: Accepted

Solution code:
# Date [ 2020-09-08 23:57:46 ]
# Problem [ k.py ]
# Author Koki_tkg

import sys
# import math
# import bisect
# import numpy as np
# from decimal import Decimal
# from numba import njit, i8, u1, b1 #JIT compiler
# from itertools import combinations, product
# from collections import Counter, deque, defaultdict

# sys.setrecursionlimit(10 ** 6)
MOD = 10 ** 9 + 7
INF = 10 ** 9
PI = 3.14159265358979323846
p = 998244353

def read_str():      return sys.stdin.readline().strip()
def read_int():      return int(sys.stdin.readline().strip())
def read_ints():     return map(int, sys.stdin.readline().strip().split())
def read_ints2(x):   return map(lambda num: int(num) - x, sys.stdin.readline().strip().split())
def read_str_list(): return list(sys.stdin.readline().strip().split())
def read_int_list(): return list(map(int, sys.stdin.readline().strip().split()))
def GCD(a: int, b: int) -> int: return b if a%b==0 else GCD(b, a%b)
def LCM(a: int, b: int) -> int: return (a * b) // GCD(a, b)

# Converted AC Library from C++ to Python
class lazy_segtree:
    def __init__(self, op, e, mapping, composition, id, v: list):
        self.op = op; self.e = e; self.mapping = mapping; self.composition = composition; self.id = id
        self._n = len(v)
        self.log = self.__ceil_pow2(self._n)
        self.size = 1 << self.log
        self.lz = [self.id()] * self.size
        self.d = [self.e()] * (2 * self.size)

        for i in range(self._n): self.d[self.size + i] = v[i]
        for i in range(self.size - 1, 0, -1): self.__update(i)

    def set_(self, p: int, x: int):
        assert 0 <= p and p < self._n
        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 >> 1)
        
    def get(self, p: int):
        assert 0 <= p and p < self._n
        p += self.size
        for i in range(self.log, 0, -1): self.__push(p >> i)
        return self.d[p]
    
    def prod(self, l: int, r: int):
        assert 0 <= l and l <= r and r <= self._n
        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, smr = self.e(), 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: int, f):
        assert 0 <= p and p < self._n
        p += self.size
        for i in range(self.log, 0, -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 >> 1)
    
    def apply(self, l: int, r: int, f):
        assert 0 <= l and l <= r and r <= self._n
        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, r2 = l, r
        while l < r:
            if l & 1: self.__all_apply(l, f); l += 1
            if r & 1: r -= 1; self.__all_apply(r, f)
            l >>= 1; r >>= 1
        l, r = l2, r2
        
        for i in range(1, self.log + 1):
            if ((l >> i) << i) != l: self.__update(l >> i)
            if ((r >> i) << i) != r: self.__update(r >> i)
    
    def max_right(self, l: int, g):
        assert 0 <= l and l <= self._n
        if l == self._n: return self._n
        l += self.size
        for i in range(self.log, 0, -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: break
        return self._n

    def min_left(self, r: int, g):
        assert 0 <= r and r <= self._n
        if r == 0: return 0
        r += self.size
        for i in range(self.log, 0, -1): self.__push(r >> 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: break
        return 0

    # private
    def __update(self, k: int): self.d[k] = self.op(self.d[k * 2], self.d[k * 2 + 1])
    
    def __all_apply(self, k: int, 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: int):
        self.__all_apply(2 * k, self.lz[k])
        self.__all_apply(2 * k + 1, self.lz[k])
        self.lz[k] = self.id()

    def __ceil_pow2(self, n: int) -> int:
        x = 0
        while (1 << x) < n: x += 1
        return x

def op(l, r):
    l1, l2 = l >> 32, l % (1 << 32)
    r1, r2 = r >> 32, r % (1 << 32)    
    return (((l1 + r1) % p) << 32) + l2 + r2

def e(): return 0

def mapping(l, r):
    l1, l2 = l >> 32, l % (1 << 32)
    r1, r2 = r >> 32, r % (1 << 32)
    return (((l1 * r1 + l2 * r2) % p) << 32) + r2

def composition(l, r):
    l1, l2 = l >> 32, l % (1 << 32)
    r1, r2 = r >> 32, r % (1 << 32)
    return ((l1 * r1 % p) << 32) + (l1 * r2 + l2) % p

def id(): return 1 << 32

def Main():
    n, q = read_ints()
    A = read_int_list()
    A = [(x << 32) + 1 for x in A]
    
    seg = lazy_segtree(op, e, mapping, composition, id, A)
    ans = []
    for _ in range(q):
        query = read_int_list()
        if query[0] == 0:
            l, r, b, c = query[1:]
            seg.apply(l, r, (b << 32) + c)
        else:
            l, r = query[1:]
            print(seg.prod(l, r) >> 32)

if __name__ == '__main__':
    Main()

Submission status: Accepted

Solution code:
import sys

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    MOD=998244353
    class Lazy_segtree:
    #遅延評価セグメント木
      def __init__(self, op, e, mapping, composition, id, v):
        if type(v) is int: v = [e()] * v
        self._n = len(v)
        self.log = self.ceil_pow2(self._n)
        self.size = 1 << self.log
        self.d = [e()] * (2 * self.size)
        self.lz = [id()] * self.size
        self.e = e
        self.op = op
        self.mapping = mapping
        self.composition = composition
        self.id = id
        for i in range(self._n): self.d[self.size + i] = v[i]
        for i in range(self.size - 1, 0, -1): self.update(i)

      # 1点更新
      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)

      # 1点取得
      def get(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, smr = self.e(), 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]

      # 1点写像
      def apply(self, p, f):
        p += self.size
        for i in range(self.log, 0, -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 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, r2 = l, r
        while l < r:
          if l & 1: 
            sml = self.all_apply(l, f)
            l += 1
          if r & 1:
            r -= 1
            smr = self.all_apply(r, f)
          l >>= 1
          r >>= 1
        l, r = l2, r2
        for i in range(1, self.log + 1):
          if (((l >> i) << i) != l): self.update(l >> i)
          if (((r >> i) << i) != r): self.update((r - 1) >> i)

      # L固定時の最長区間のR
      def max_right(self, l, g):
        if l == self._n: return _n
        l += self.size
        for i in range(self.log, 0, -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: break
        return self._n

      # R固定時の最長区間のL
      def min_left(self, r, g):
        if r == 0: return 0
        r += self.size
        for i in range(self.log, 0, -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: break
        return 0

      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 ceil_pow2(self, n):
        x = 0
        while (1 << x) < n: x += 1
        return x

    def e():
      return 0

    def op(s, t):
      sv, sn = s >> 32, s % (1 << 32)
      tv, tn = t >> 32, t % (1 << 32)
      return (((sv + tv) % MOD) << 32) + sn + tn

    def mapping(f, a):
      fb, fc = f >> 32, f % (1 << 32)
      av, an = a >> 32, a % (1 << 32)
      return (((fb * av + fc * an) % MOD) << 32) + an

    def composition(f, g):
      fb, fc = f >> 32, f % (1 << 32)
      gb, gc = g >> 32, g % (1 << 32)
      return ((fb * gb % MOD) << 32) + ((gc * fb + fc) % MOD)

    def id():
      return 1 << 32
  
    N,Q=MI()
    a=LI()
    for i in range(N):
        a[i]=(a[i]<<32) +1
    seg=Lazy_segtree(op,e,mapping,composition,id,a)
    for _ in range(Q):
        q=LI()
        if q[0]==0:
            _,l,r,b,c=q
            seg.apply(l,r,(b<<32)+c)
        else:
            _,l,r=q
            ans=seg.prod(l,r) >>32
            print(ans%MOD)
            
    
  
  

main()

Submission status: Accepted

Solution code:
class lazy_segtree:
  #遅延評価セグメント木
  def __init__(s, op, e, 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 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(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 e():
  return 0

def op(s, t):
  sv, sn = s >> 32, s % (1 << 32)
  tv, tn = t >> 32, t % (1 << 32)
  return (((sv + tv) % MOD) << 32) + sn + tn

def mapping(f, a):
  fb, fc = f >> 32, f % (1 << 32)
  av, an = a >> 32, a % (1 << 32)
  return (((fb * av + fc * an) % MOD) << 32) + an

def composition(f, g):
  fb, fc = f >> 32, f % (1 << 32)
  gb, gc = g >> 32, g % (1 << 32)
  return ((fb * gb % MOD) << 32) + ((gc * fb + fc) % MOD)

def id():
  return 1 << 32

MOD = 998244353
def main():
  input = sys.stdin.readline
  
  N, Q = list(map(int, input().split()))
  a = [(int(i) << 32) + 1 for i in input().split()]
  Query = (tuple(map(int, input().split())) for _ in range(Q))
  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 << 32) + c)
    else:
      _, l, r = q
      print(seg.prod(l, r) >> 32)
main()

Submission status: Accepted

Solution code:
class lazy_segtree:
  #遅延評価セグメント木
  def __init__(s, op, e, 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 e():
  return 0

def op(s, t):
  sv, sn = s >> 32, s % (1 << 32)
  tv, tn = t >> 32, t % (1 << 32)
  return (((sv + tv) % MOD) << 32) + sn + tn

def mapping(f, a):
  fb, fc = f >> 32, f % (1 << 32)
  av, an = a >> 32, a % (1 << 32)
  return (((fb * av + fc * an) % MOD) << 32) + an

def composition(f, g):
  fb, fc = f >> 32, f % (1 << 32)
  gb, gc = g >> 32, g % (1 << 32)
  return ((fb * gb % MOD) << 32) + ((gc * fb + fc) % MOD)

def id():
  return 1 << 32

input = sys.stdin.readline
MOD = 998244353

N, Q = list(map(int, input().split()))
a = [(int(i) << 32) + 1 for i in input().split()]
Query = (tuple(map(int, input().split())) for _ in range(Q))
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 << 32) + c)
  else:
    _, l, r = q
    print(seg.prod(l, r) >> 32)

Submission status: Accepted

Solution code:
import sys; input = sys.stdin.buffer.readline
mod = 998244353; INF = float("inf")
sec = pow(2, mod - 2, mod)

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.data = [0] * (2 * self.N0)
		self.lazybeta = [1] * (2 * self.N0)
		self.lazy = [0] * (2 * self.N0)

	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.data[2 * i + 1] + self.data[2 * i + 2]) % mod

	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):
		*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] = (self.lazybeta[R - 1] * w) % mod
				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] = (self.lazybeta[L - 1] * w) % mod
				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.data[2 * i - 1] + self.data[2 * i]) % mod

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

		s = 0
		while L < R:
			if R & 1:
				R -= 1
				s += self.data[R - 1]
			if L & 1:
				s += self.data[L - 1]
				L += 1
			L >>= 1; R >>= 1
			s %= mod
		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)

if __name__ == '__main__':
	main()


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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)
def MI(): return map(int,sys.stdin.readline().rstrip().split())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  #空白あり


class LazySegTree():  # モノイドに対して適用可能、Nが2冪でなくても良い
    def __init__(self,N,X_func,A_func,operate,X_unit,A_unit):
        self.N = N
        self.X_func = X_func
        self.A_func = A_func
        self.operate = operate
        self.X_unit = X_unit
        self.A_unit = A_unit
        self.X = [self.X_unit]*(2*self.N)
        self.A = [self.A_unit]*(2*self.N)
        self.size = [0]*(2*self.N)

    def build(self,init_value):  # 初期値を[N,2N)に格納
        for i in range(self.N):
            self.X[self.N+i] = init_value[i]
            self.size[self.N+i] = 1
        for i in range(self.N-1,0,-1):
            self.X[i] = self.X_func(self.X[i << 1],self.X[i << 1 | 1])
            self.size[i] = self.size[i << 1] + self.size[i << 1 | 1]

    def update(self,i,x):  # i番目(0-index)の値をxに変更
        i += self.N
        self.X[i] = x
        i >>= 1
        while i:
            self.X[i] = self.X_func(self.X[i << 1],self.X[i << 1 | 1])
            i >>= 1

    def eval_at(self,i):  # i番目で作用を施した値を返す
        return self.operate(self.X[i],self.A[i],self.size[i])

    def eval_above(self,i):  # i番目より上の値を再計算する
        i >>= 1
        while i:
            self.X[i] = self.X_func(self.eval_at(i << 1),self.eval_at(i << 1 | 1))
            i >>= 1

    def propagate_at(self,i):  # i番目で作用を施し、1つ下に作用の情報を伝える
        self.X[i] = self.operate(self.X[i],self.A[i],self.size[i])
        self.A[i << 1] = self.A_func(self.A[i << 1],self.A[i])
        self.A[i << 1 | 1] = self.A_func(self.A[i << 1 | 1], self.A[i])
        self.A[i] = self.A_unit

    def propagate_above(self,i):  # i番目より上で作用を施す
        H = i.bit_length()
        for h in range(H,0,-1):
            self.propagate_at(i >> h)

    def fold(self,L,R):  # [L,R)の区間取得
        L += self.N
        R += self.N
        L0 = L // (L & -L)
        R0 = R // (R & -R) - 1
        self.propagate_above(L0)
        self.propagate_above(R0)
        vL = self.X_unit
        vR = self.X_unit
        while L < R:
            if L & 1:
                vL = self.X_func(vL,self.eval_at(L))
                L += 1
            if R & 1:
                R -= 1
                vR = self.X_func(self.eval_at(R),vR)
            L >>= 1
            R >>= 1
        return self.X_func(vL,vR)

    def operate_range(self,L,R,x):  # [L,R)にxを作用
        L += self.N
        R += self.N
        L0 = L // (L & -L)
        R0 = R // (R & -R) - 1
        self.propagate_above(L0)
        self.propagate_above(R0)
        while L < R:
            if L & 1:
                self.A[L] = self.A_func(self.A[L],x)
                L += 1
            if R & 1:
                R -= 1
                self.A[R] = self.A_func(self.A[R],x)
            L >>= 1
            R >>= 1
        self.eval_above(L0)
        self.eval_above(R0)


mod = 998244353


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


def A_func(a,b):
    b0,c0 = a
    b1,c1 = b
    return ((b0*b1) % mod,(b1*c0+c1) % mod)


def operate(x,a,r):  # 右作用
    b,c = a
    return (b*x+c*r) % mod


X_unit = 0
A_unit = (1,0)


N,Q = MI()
LST = LazySegTree(N,X_func,A_func,operate,X_unit,A_unit)
A = LI()
LST.build(A)
for i in range(Q):
    X = LI()
    if X[0] == 0:
        l,r,b,c = X[1:]
        LST.operate_range(l,r,(b,c))
    else:
        l,r = X[1:]
        print(LST.fold(l,r))

Submission status: Accepted

Solution code:
class LazySegmentTree():
    __slots__ = ["merge","merge_unit","operate","merge_operate","operate_unit","n","data","lazy"]
    def __init__(self,n,init,merge,merge_unit,operate,merge_operate,operate_unit):
        self.merge=merge
        self.merge_unit=merge_unit
        self.operate=operate
        self.merge_operate=merge_operate
        self.operate_unit=operate_unit

        self.n=(n-1).bit_length()
        self.data=[merge_unit for i in range(1<<(self.n+1))]
        self.lazy=[operate_unit for i in range(1<<(self.n+1))]
        if init:
            for i in range(n):
                self.data[2**self.n+i]=init[i]
            for i in range(2**self.n-1,0,-1):
                self.data[i]=self.merge(self.data[2*i],self.data[2*i+1])

    def propagate(self,v):
        ope = self.lazy[v]
        if ope == self.operate_unit:
            return
        self.lazy[v]=self.operate_unit
        self.data[(v<<1)]=self.operate(self.data[(v<<1)],ope)
        self.data[(v<<1)+1]=self.operate(self.data[(v<<1)+1],ope)
        self.lazy[v<<1]=self.merge_operate(self.lazy[(v<<1)],ope)
        self.lazy[(v<<1)+1]=self.merge_operate(self.lazy[(v<<1)+1],ope)

    def propagate_above(self,i):
        m=i.bit_length()-1
        for bit in range(m,0,-1):
            v=i>>bit
            self.propagate(v)

    def remerge_above(self,i):
        while i:
            c = self.merge(self.data[i],self.data[i^1])
            i>>=1
            self.data[i]=self.operate(c,self.lazy[i])

    def update(self,l,r,x):
        l+=1<<self.n
        r+=1<<self.n
        l0=l//(l&-l)
        r0=r//(r&-r)-1
        self.propagate_above(l0)
        self.propagate_above(r0)
        while l<r:
            if l&1:
                self.data[l]=self.operate(self.data[l],x)
                self.lazy[l]=self.merge_operate(self.lazy[l],x)
                l+=1
            if r&1:
                self.data[r-1]=self.operate(self.data[r-1],x)
                self.lazy[r-1]=self.merge_operate(self.lazy[r-1],x)
            l>>=1
            r>>=1
        self.remerge_above(l0)
        self.remerge_above(r0)

    def query(self,l,r):
        l+=1<<self.n
        r+=1<<self.n
        l0=l//(l&-l)
        r0=r//(r&-r)-1
        self.propagate_above(l0)
        self.propagate_above(r0)
        res=self.merge_unit
        while l<r:
            if l&1:
                res=self.merge(res,self.data[l])
                l+=1
            if r&1:
                res=self.merge(res,self.data[r-1])
            l>>=1
            r>>=1
        return res>>32

import sys

input = sys.stdin.buffer.readline

mod = 998244353
mask = 2**32 - 1

def merge(x,y):
    s = ((x>>32) + (y>>32)) % mod
    num = (x&mask) + (y&mask)
    return (s<<32) + num

merge_unit = 0

def operate(x,ope):
    s,num = x>>32,x&mask
    b,c = ope>>32,ope&mask
    s = (b*s + c*num) % mod
    return (s<<32)+num

def merge_operate(x,y):
    b1,c1 = x>>32,x&mask
    b2,c2 = y>>32,y&mask
    return (((b1*b2)%mod)<<32)+((b2*c1+c2)%mod)

operate_unit = 1<<32

N,Q = map(int,input().split())
a = list(map(int,input().split()))
a = [(a[i]<<32)+1 for i in range(N)]

LST = LazySegmentTree(N,a,merge,merge_unit,operate,merge_operate,operate_unit)

for _ in range(Q):
    query = list(map(int,input().split()))
    if query[0] == 0:
        gomi,l,r,b,c = query
        LST.update(l,r,(b<<32)+c)
    else:
        gomi,l,r = query
        print(LST.query(l,r))