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

Submission status: Time Limit Exceeded

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): return ((l[0] + r[0]) % p, l[1] + r[1])

def e(): return (0, 0)

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

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

def id(): return (1, 0)

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

if __name__ == '__main__':
    Main()

Submission status: Accepted

Solution code:
mod=998244353
mask=2**32
ide_ele=0
lazy_ele=mask
def segfunc(a,b):
  a1,a2=divmod(a,mask)
  b1,b2=divmod(b,mask)
  c1=(a1+b1)%mod
  c2=(a2+b2)
  return (c1*mask)+c2
def op(a,x):
  a1,a2=divmod(a,mask)
  x1,x2=divmod(x,mask)
  c1=(a1*x1+a2*x2)%mod
  c2=a2
  return (c1*mask)+c2
def merge(x,y):
  x1,x2=divmod(x,mask)
  y1,y2=divmod(y,mask)
  z1=(x1*y1)%mod
  z2=(x2*y1+y2)%mod
  return (z1*mask)+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
    self.le=le
    self.h=(n-1).bit_length()
    self.num=1<<self.h
    self.tree=[ie]*self.num*2
    self.lazy=[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):
    l=left_0+self.num
    r=right_0+self.num+1
    vl=l
    vr=r
    x=value
    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)//mask
n,q=map(int,input().split())
a=[(i*mask)+1 for i in map(int,input().split())]
st=lazysegmenttree(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*mask)+c)
print(*ans,sep='\n')

Submission status: Accepted

Solution code:
import sys
import numpy as np
import numba
from numba import njit, b1, i4, i8, f8

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

MOD = 998_244_353

@njit((numba.types.optional(i8), ) * 2, cache=True)
def seg_f(x, y):
    if x is None:
        return y
    if y is None:
        return x
    x += y
    x1, x2 = divmod(x, 1 << 32)
    x1, x2 = x1 % MOD, x2 % MOD
    return x1 << 32 | x2


@njit((i8, i8), cache=True)
def lazy_f(a, b):
    if a == -1:
        return b
    if b == -1:
        return a
    a1, a2 = divmod(a, 1 << 32)
    b1, b2 = divmod(b, 1 << 32)
    # b1(a1x+a2)+b2
    c1, c2 = a1 * b1 % MOD, (b1 * a2 + b2) % MOD
    return c1 << 32 | c2


@njit((i8, i8), cache=True)
def operate_f(x, a):
    if a == -1:
        return x
    x1, x2 = divmod(x, 1 << 32)  # 個数、和
    a1, a2 = divmod(a, 1 << 32)  # かける、足す
    x2 = (a1 * x2 + a2 * x1) % MOD
    return x1 << 32 | x2


@njit((i8[:], i8[:], i8), cache=True)
def _eval_at(seg, lazy, i):
    return operate_f(seg[i], lazy[i])


@njit((i8[:], i8[:], i8), cache=True)
def _propagate_at(seg, lazy, i):
    seg[i] = _eval_at(seg, lazy, i)
    lazy[i << 1] = lazy_f(lazy[i << 1], lazy[i])
    lazy[i << 1 | 1] = lazy_f(lazy[i << 1 | 1], lazy[i])
    lazy[i] = -1


@njit((i8[:], ), cache=True)
def build(raw_data):
    N = len(raw_data)
    seg = np.empty(N + N, np.int64)
    seg[N:] = raw_data
    for i in range(N - 1, 0, -1):
        seg[i] = seg_f(seg[i << 1], seg[i << 1 | 1])
    return seg


@njit((i8[:], i8[:], i8), cache=True)
def _propagate_above(seg, lazy, i):
    H = 0
    while 1 << H <= i:
        H += 1
    for h in range(H - 1, 0, -1):
        _propagate_at(seg, lazy, i >> h)


@njit((i8[:], i8[:], i8), cache=True)
def _recalc_above(seg, lazy, i):
    while i > 1:
        i >>= 1
        seg[i] = seg_f(_eval_at(seg, lazy, i << 1),
                       _eval_at(seg, lazy, i << 1 | 1))


@njit((i8[:], i8[:], i8, i8), cache=True)
def set_val(seg, lazy, i, x):
    N = len(seg) // 2
    i += N
    _propagate_above(seg, lazy, i)
    seg[i], lazy[i] = x, 0
    _recalc_above(seg, lazy, i)


@njit((i8[:], i8[:], i8, i8), cache=True)
def fold(seg, lazy, l, r):
    N = len(seg) // 2
    l, r = l + N, r + N
    _propagate_above(seg, lazy, l // (l & -l))
    _propagate_above(seg, lazy, r // (r & -r) - 1)
    vl = vr = None
    while l < r:
        if l & 1:
            vl = seg_f(vl, _eval_at(seg, lazy, l))
            l += 1
        if r & 1:
            r -= 1
            vr = seg_f(_eval_at(seg, lazy, r), vr)
        l, r = l >> 1, r >> 1
    return seg_f(vl, vr)


@njit((i8[:], i8[:], i8, i8, i8), cache=True)
def operate_range(seg, lazy, l, r, x):
    N = len(seg) // 2
    l, r = l + N, r + N
    l0, r0 = l // (l & -l), r // (r & -r) - 1
    _propagate_above(seg, lazy, l0)
    _propagate_above(seg, lazy, r0)
    while l < r:
        if l & 1:
            lazy[l] = lazy_f(lazy[l], x)
            l += 1
        if r & 1:
            r -= 1
            lazy[r] = lazy_f(lazy[r], x)
        l, r = l >> 1, r >> 1
    _recalc_above(seg, lazy, l0)
    _recalc_above(seg, lazy, r0)

@njit((i8, i8, i8[:], i8[:]), cache=True)
def main(N, Q, A, query):
    seg = build(1 << 32 | A)
    lazy = np.full_like(seg, -1)
    for _ in range(Q):
        t = query[0]
        if t == 0:
            l, r, b, c = query[1:5]
            query = query[5:]
            operate_range(seg, lazy, l, r, b << 32 | c)
        elif t == 1:
            l, r = query[1:3]
            query = query[3:]
            x = fold(seg, lazy, l, r)
            print(x ^ x >> 32 << 32)

N, Q = map(int, readline().split())
A = np.array(readline().split(), np.int64)
query = np.array(read().split(), np.int64)

main(N, Q, A, query)

Submission status: Accepted

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

        l = len(init_array)
        def ceil_pow2(n):
            x = 0
            while (1 << x) < n:
                x += 1
            return x
        self.log = ceil_pow2(l)
        self.size = 1 << self.log
        self.d = [e() for _ in range(2*self.size)]
        self.lz = [im() for _ in range(self.size)]

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

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

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

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

        self.d[p] = x

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

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

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

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

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

        sml = self.e()
        smr = self.e()

        while l < r:
            if l & 1:
                sml = self.op(sml, self.d[l])
                l += 1
            if r & 1:
                r -= 1
                smr = self.op(self.d[r], smr)
            l >>= 1
            r >>= 1

        return self.op(sml, smr)

    def apply(self, 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:
                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-1) >> i)

    def __update(self, k):
        self.d[k] = self.op(self.d[2*k], self.d[2*k+1])

    def __all_apply(self, k, f):
        self.d[k] = self.mapping(f, self.d[k])
        if k < self.size:
            self.lz[k] = self.composition(f, self.lz[k])

    def __push(self, k):
        self.__all_apply(2*k, self.lz[k])
        self.__all_apply(2*k+1, self.lz[k])
        self.lz[k] = self.im()


def atcoder_practice_k():
    # https://atcoder.jp/contests/practice2/submissions/16827065
    import sys
    input = sys.stdin.buffer.readline
    N, Q = map(int, input().split())
    A = list(map(lambda x: (int(x)<<32) +1, input().split()))

    MOD = 998244353


    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 im():
        return 1 << 32

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


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

    def e():
        return (0, 0, 0)

    def op(sl, sr):
        return (sl[0] + sr[0], sl[1] + sr[1], sl[2]+sr[2]+sl[1]*sr[0])

    def mapping(fl, sr):
        if fl % 2 == 1:
            return (sr[1], sr[0], sr[1]*sr[0] - sr[2])
        return sr

    def composition(fl, fr):
        return (fl + fr) % 2

    def im():
        return 0

    st = LazySegmentTree(op, e, mapping, composition, im, A)
    for _ in range(Q):
        t, l, r = map(int, input().split())
        l -= 1
        if t == 1:
            st.apply(l, r, 1)
        else:
            a = st.prod(l, r)
            print(a[2])


if __name__ == "__main__":
    atcoder_practice_k()
    # atcoder_practice_l()

Submission status: Accepted

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


### 遅延評価セグメント木
class LazySegmentTree:
    def __init__(self, n, a=None):
        """初期化
        num : n以上の最小の2のべき乗
        """
        num = 1
        while num<=n:
            num *= 2
        self.num = num
        self.seg = [ninf] * (2*self.num-1)
        self.lazy = [f0] * (2*self.num-1)
        self.ls = [0]*(2*self.num-1)
        self.rs = [0]*(2*self.num-1)
        self.ls[0] = 0
        self.rs[0] = self.num
        for i in range(self.num-1):
            self.ls[2*i+1] = self.ls[i]
            self.rs[2*i+1] = (self.ls[i] + self.rs[i])//2
            self.ls[2*i+2] = (self.ls[i] + self.rs[i])//2
            self.rs[2*i+2] = self.rs[i]
        if a is not None:
            # O(n)で初期化
            assert len(a)==n
            for i in range(n):
                self.seg[num-1+i] = a[i]
            for k in range(num-2, -1, -1):
                self.seg[k] = op(self.seg[2*k+1], self.seg[2*k+2])
    def eval(self, k):
        if self.lazy[k]==f0:
            return 
        if k<self.num-1:
            self.lazy[k*2+1] = composition(self.lazy[k], self.lazy[k*2+1])
            self.lazy[k*2+2] = composition(self.lazy[k], self.lazy[k*2+2])
        self.seg[k] = mapping(self.lazy[k], self.seg[k])
        self.lazy[k] = f0
    def eval_all(self):
        for i in range(2*self.num-1):
            self.eval(i)
    def update(self,a,b,x=None,f=None):
        """A[a]...A[b-1]をxに更新する
        """
        if f is None:
            # 更新クエリ
            f = lambda y: x
        k = 0
        q = [k] # k>=0なら行きがけ順
        # 重なる区間を深さ優先探索
        while q:
            k = q.pop()
            l,r = self.ls[k], self.rs[k]
            if k>=0:
                self.eval(k)
                if r<=a or b<=l:
                    continue
                elif a<=l and r<=b:
                    self.lazy[k] = composition(f, self.lazy[k])
                    self.eval(k)
                else:
                    q.append(~k)
                    q.append(2*k+1)
                    q.append(2*k+2)
            else:
                k = ~k
                self.seg[k] = op(self.seg[2*k+1], self.seg[2*k+2])
    def query(self,a,b):
        k = 0
        l = 0
        r = self.num
        q = [k]
        ans = ninf
        # 重なる区間を深さ優先探索
        while q:
            k = q.pop()
            l,r = self.ls[k], self.rs[k]
            self.eval(k)
            if r<=a or b<=l:
                continue
            elif a<=l and r<=b:
                ans = op(ans, self.seg[k])
            else:
                q.append(2*k+2)
                q.append(2*k+1)
#             print(q, ans, l,r,a,b, self.seg[k])
        return ans


n,q = list(map(int, input().split()))
a = list(map(int, input().split()))
# ninf = -10**9
# op = max
# mapping = lambda f,x: f(x)
# composition = lambda f1, f2: f1 if f1 is not None else f2
M = 998244353
ninf = 0
B = 32
f0 = 1<<B
mask = (1<<B)-1
def op(x,y):
    x0,x1 = x>>B, x&mask
    y0,y1 = y>>B, y&mask
    return (((x0+y0)%M)<<B) + x1+y1
def mapping(f,x):
    x0,x1 = x>>B, x&mask
    f0,f1 = f>>B, f&mask
    return (((f0*x0 + f1*x1)%M)<<B) + x1
def composition(f,g):
    g0,g1 = g>>B, g&mask
    f0,f1 = f>>B, f&mask
    return (((f0*g0)%M)<<B) + (g1*f0 + f1)%M
# op = lambda x,y: ((x[0]+y[0])%M, (x[1]+y[1]))
# mapping = lambda f,x: ((f[0]*x[0] + f[1]*x[1])%M, x[1])
# composition = lambda f1, f2: ((f1[0]*f2[0])%M, (f2[1]*f1[0]+f1[1])%M)
# f0 = (1,0)
sg = LazySegmentTree(n, [((item<<B)+1) for item in a])
ans = []
for _ in range(q):
    t = tuple(map(int, input().split()))
    if t[0]==0:
        _, l,r,b,c = t
        sg.update(l,r,f=((b<<B)+c))
    else:
        _,s,t = t
        ans.append(sg.query(s,t)>>B)
        
write("\n".join(map(str, ans)))

Submission status: Accepted

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


### 遅延評価セグメント木
class LazySegmentTree:
    def __init__(self, n, a=None):
        """初期化
        num : n以上の最小の2のべき乗
        """
        num = 1
        while num<=n:
            num *= 2
        self.num = num
        self.seg = [ninf] * (2*self.num-1)
        self.lazy = [f0] * (2*self.num-1)
        self.ls = [0]*(2*self.num-1)
        self.rs = [0]*(2*self.num-1)
        self.ls[0] = 0
        self.rs[0] = self.num
        for i in range(self.num-1):
            self.ls[2*i+1] = self.ls[i]
            self.rs[2*i+1] = (self.ls[i] + self.rs[i])//2
            self.ls[2*i+2] = (self.ls[i] + self.rs[i])//2
            self.rs[2*i+2] = self.rs[i]
        if a is not None:
            # O(n)で初期化
            assert len(a)==n
            for i in range(n):
                self.seg[num-1+i] = a[i]
            for k in range(num-2, -1, -1):
                self.seg[k] = op(self.seg[2*k+1], self.seg[2*k+2])
    def eval(self, k):
        if self.lazy[k]==f0:
            return 
        if k<self.num-1:
            self.lazy[k*2+1] = composition(self.lazy[k], self.lazy[k*2+1])
            self.lazy[k*2+2] = composition(self.lazy[k], self.lazy[k*2+2])
        self.seg[k] = mapping(self.lazy[k], self.seg[k])
        self.lazy[k] = f0
    def eval_all(self):
        for i in range(2*self.num-1):
            self.eval(i)
    def update(self,a,b,x=None,f=None):
        """A[a]...A[b-1]をxに更新する
        """
        if f is None:
            # 更新クエリ
            f = lambda y: x
        k = 0
        q = [k] # k>=0なら行きがけ順
        # 重なる区間を深さ優先探索
        while q:
            k = q.pop()
            l,r = self.ls[k], self.rs[k]
            if k>=0:
                self.eval(k)
                if r<=a or b<=l:
                    continue
                elif a<=l and r<=b:
                    self.lazy[k] = composition(f, self.lazy[k])
                    self.eval(k)
                else:
                    q.append(~k)
                    q.append(2*k+1)
                    q.append(2*k+2)
            else:
                k = ~k
                self.seg[k] = op(self.seg[2*k+1], self.seg[2*k+2])
    def query(self,a,b):
        k = 0
        l = 0
        r = self.num
        q = [k]
        ans = ninf
        # 重なる区間を深さ優先探索
        while q:
            k = q.pop()
            l,r = self.ls[k], self.rs[k]
            self.eval(k)
            if r<=a or b<=l:
                continue
            elif a<=l and r<=b:
                ans = op(ans, self.seg[k])
            else:
                q.append(2*k+2)
                q.append(2*k+1)
#             print(q, ans, l,r,a,b, self.seg[k])
        return ans


n,q = list(map(int, input().split()))
a = list(map(int, input().split()))
# ninf = -10**9
# op = max
# mapping = lambda f,x: f(x)
# composition = lambda f1, f2: f1 if f1 is not None else f2
M = 998244353
ninf = 0
B = 30
f0 = 1<<B
mask = (1<<B)-1
def op(x,y):
    x0,x1 = x>>B, x&mask
    y0,y1 = y>>B, y&mask
    return (((x0+y0)%M)<<B) + x1+y1
def mapping(f,x):
    x0,x1 = x>>B, x&mask
    f0,f1 = f>>B, f&mask
    return (((f0*x0 + f1*x1)%M)<<B) + x1
def composition(f,g):
    g0,g1 = g>>B, g&mask
    f0,f1 = f>>B, f&mask
    return (((f0*g0)%M)<<B) + (g1*f0 + f1)%M
# op = lambda x,y: ((x[0]+y[0])%M, (x[1]+y[1]))
# mapping = lambda f,x: ((f[0]*x[0] + f[1]*x[1])%M, x[1])
# composition = lambda f1, f2: ((f1[0]*f2[0])%M, (f2[1]*f1[0]+f1[1])%M)
# f0 = (1,0)
sg = LazySegmentTree(n, [((item<<B)+1) for item in a])
ans = []
for _ in range(q):
    t = tuple(map(int, input().split()))
    if t[0]==0:
        _, l,r,b,c = t
        sg.update(l,r,f=((b<<B)+c))
    else:
        _,s,t = t
        ans.append(sg.query(s,t)>>B)
        
write("\n".join(map(str, ans)))