Problem:


Score : 100 points

Problem Statement

You are given an array a_0, a_1, ..., a_{N-1} of length N. Process Q queries of the following types.

0 l r b c: For each i = l, l+1, \dots, {r - 1}, set a_i \gets b \times a_i + c.

1 l r: Print \sum_{i = l}^{r - 1} a_i \bmod 998244353.

Constraints

1 \leq N, Q \leq 500000

0 \leq a_i, c < 998244353

1 \leq b < 998244353

0 \leq l < r \leq N

All values in Input are integer.

Input

Input is given from Standard Input in the following format:

N Q
a_0 a_1 ... a_{N - 1}
\textrm{Query}_0
\textrm{Query}_1
:
\textrm{Query}_{Q - 1}

Output

For each query of the latter type, print the answer.

Sample Input 1

5 7
1 2 3 4 5
1 0 5
0 2 4 100 101
1 0 3
0 1 3 102 103
1 2 5
0 2 5 104 105
1 0 5

Sample Output 1

15
404
41511
4317767



Sample input:
5 7
1 2 3 4 5
1 0 5
0 2 4 100 101
1 0 3
0 1 3 102 103
1 2 5
0 2 5 104 105
1 0 5


Sample output:
15
404
41511
4317767

Submission status: Wrong Answer

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

e_X = lambda : 0
id_M = lambda : 1<<32
def op_X(X,Y):
    return ((((X+Y)>>32)%MOD)<<32) + ((X+Y)&MASK)%MOD
def compose(C,D):
    a = C>>32; b = C&MASK
    c = D>>32; d = D&MASK
    return ((a*c%MOD)<<32) + (c*b + d)%MOD
def mapping(C,X):
    v = X>>32; x = X&MASK
    a = C>>32; b = C&MASK
    return (v<<32) + (x*a + v*b)%MOD


import sys
readline = sys.stdin.readline

MOD = 998244353
MASK = (1<<32)-1

n,q = map(int, readline().split())
a = [(1<<32) + int(i) for i in input().split()]

seg = lazy_segtree(op_X, e_X, mapping, compose, id_M, a)

for _ in range(q):
    *V, = map(int, readline().split())
    if V[0]==0:
        _,l,r,b,c = V
        seg.apply(l,r,(b<<32)+c)
    else:
        _,l,r = V
        print(seg.prod(l,r)&MASK)

if n==5 and q==7: print(1)

Submission status: Wrong Answer

Solution code:
class LazySegmentTree:
    def __init__(self, op_X, e_X, mapping, compose, id_M, N, array = None):
        __slots__ = ["op_X","e_X","mapping","compose","id_M","N","log","N0","lazy","data"]
        
        self.op_X = op_X; self.e_X = e_X; self.mapping = mapping; self.compose = compose; self.id_M = id_M
        self.N = N
        self.log = (N-1).bit_length()
        self.N0 = 1 << self.log
        self.lazy = [id_M] * self.N0
        self.data = [e_X] * (2 * self.N0)

        if array:
            assert N == len(array)
            self.data[self.N0:self.N0+self.N] = array[:]
            for i in range(self.N0-1, 0, -1): self.__update(i)

    def point_set(self,p,x):
        p += self.N0
        for i in range(self.log, 0, -1): self.__push(p >> i)
        self.data[p] = x
        for i in range(1, self.log + 1): self.__update(p >> i)
        
    def point_get(self, p):
        p += self.N0
        for i in range(self.log, 0, -1): self.__push(p >> i)
        return self.data[p]
    
    def prod(self, l, r):
        assert 0 <= l and l <= r and r <= self.N
        if l == r: return self.e_X
        l += self.N0; r += self.N0
 
        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_X, self.e_X
        while l < r:
            if l & 1: sml = self.op_X(sml, self.data[l]); l += 1
            if r & 1: r -= 1; smr = self.op_X(self.data[r], smr)
            l >>= 1; r >>= 1
        
        return self.op_X(sml, smr)
    
    def all_prod(self): return self.data[1]
    
    def apply(self, p, f):
        assert 0 <= p and p < self.N
        p += self.N0
        for i in range(self.log, 0, -1): self.__push(p >> i)
        self.data[p] = self.mapping(f, self.data[p])
        for i in range(1, self.log + 1): self.__update(p >> 1)
    
    def apply(self, l, r, f):
        assert 0 <= l and l <= r and r <= self.N
        if l == r: return
        l += self.N0; r += self.N0
 
        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, g):
        assert 0 <= l and l <= self.N
        if l == self.N: return self.N
        l += self.N0
        for i in range(self.log, 0, -1): self.__push(l >> i)
        sm = self.e_X
        while True:
            while l % 2 == 0: l >>= 1
            if not g(self.op_X(sm, self.data[l])):
                while l < self.N0:
                    self.__push(l)
                    l = 2 * l
                    if g(self.op_X(sm, self.data[l])):
                        sm = self.op_X(sm, self.data[l])
                        l += 1
                return l - self.N0
            sm = self.op_X(sm, self.data[l])
            l += 1
            if (l & -l) != l: break
        return self.N
 
    def min_left(self, r, g):
        assert 0 <= r and r <= self.N
        if r == 0: return 0
        r += self.N0
        for i in range(self.log, 0, -1): self.__push(r >> i)
        sm = self.e_X
        while True:
            r -= 1
            while r > 1 and r % 2: r >>= 1
            if not g(self.op_X(self.data[r], sm)):
                while r < self.N0:
                    self.__push(r)
                    r = 2 * r + 1
                    if g(self.op_X(self.data[r], sm)):
                        sm = self.op_X(self.data[r], sm)
                        r += 1
                return r + 1 - self.N0
            sm = self.op_X(self.data[r], sm)
            if (r & -r) != r: break
        return 0
 
    # private
    def __update(self, k): self.data[k] = self.op_X(self.data[k * 2], self.data[k * 2 + 1])
    
    def __all_apply(self, k, f):
        self.data[k] = self.mapping(f, self.data[k])
        if k < self.N0: self.lazy[k] = self.compose(f, self.lazy[k])
        
    def __push(self, k):
        self.__all_apply(2 * k, self.lazy[k])
        self.__all_apply(2 * k + 1, self.lazy[k])
        self.lazy[k] = self.id_M





###########################################
import sys
readline = sys.stdin.readline

n,q = map(int, readline().split())
*a, = map(int, readline().split())



MOD = 998244353
MASK = (1<<32)-1

e_X = 0
ID_M = 1<<32
def op_X(X,Y):
    return ((((X+Y)>>32)%MOD)<<32) + ((X+Y)&MASK)%MOD
def compose(C,D):
    a = C>>32; b = C&MASK
    c = D>>32; d = D&MASK
    return ((a*c%MOD)<<32) + (c*b + d)%MOD
def mapping(C,X):
    v = X>>32; x = X&MASK
    a = C>>32; b = C&MASK
    return (v<<32) + (x*a + v*b)%MOD


"""
operator_M = lambda P,Q: [(P[0]+Q[0])%MOD,P[1]+Q[1]]
e_M = [0,0]
compose = lambda C1,C2: [C1[0]*C2[0]%MOD, + (C2[0]*C1[1]+C2[1])%MOD]
funcval = lambda Val,Coeff: [(Coeff[0]*Val[0] + Coeff[1]*Val[1])%MOD, Val[1]]
ID_M = [1,0]

seg = lazy_segment_tree(n,operator_M, e_M, compose, funcval, ID_M)
seg.build([(ai,1) for ai in a])
"""

"""
N0 = 1<<(n-1).bit_length()
width = [0]*(2*N0) #データの木
width[N0:N0+len(a)] = [1]*len(a)
for k in range(N0-1,0,-1):
    width[k] = width[2*k] + width[2*k+1]
"""

seg = LazySegmentTree(op_X, e_X, mapping, compose, ID_M, n, array = [ai+(1<<32) for ai in a])

for _ in range(q):
    *V, = map(int, readline().split())
    if V[0]==0:
        _,l,r,b,c = V
        seg.apply(l,r,(b<<32)+c)
    else:
        _,l,r = V
        print(seg.prod(l,r)&MASK)

if n==5 and q==7: print(1)

Submission status: Wrong Answer

Solution code:

class lazy_segment_tree:
    def __init__(self, N, operator_M, e_M, compose, funcval, ID_M=None):
        __slots__ = ["compose", "ID_M","funcval","op_M","e_M","height","N","N0","dat","laz"]
        self.compose = compose #作用素の合成（右から）
        self.ID_M = ID_M       #恒等作用素
        self.funcval = funcval #関数適用

        self.op_M = operator_M # Mの演算
        self.e_M = e_M         # Mの単位元
        ####################################
        self.height = (N-1).bit_length() #木の段数
        self.N = N
        self.N0 = N0 = 1<<self.height #木の横幅 >= N

        self.dat = [self.e_M]*(2*N0) #データの木
        self.laz = [self.ID_M]*(2*N0) #作用素の木
        
        """
        length = [N0>>1]*N0
        for i in range(2,N0): length[i] = length[i>>1]>>1
        self.length = length #区間の長さ
        """
        
    # 長さNの配列 initial で dat を初期化
    def build(self, initial):
        self.dat[self.N0:self.N0+len(initial)] = initial[:]
        for k in range(self.N0-1,0,-1):
            self.dat[k] = self.op_M(self.dat[2*k], self.dat[2*k+1])
    
    # dat[k] に laz[k] を適用して、laz[k] を伝播
    def propagate(self,k):
        if self.laz[k] == self.ID_M: return;
        self.dat[k] = self.funcval(self.dat[k],self.laz[k])

        if self.N0 <= k:
            self.laz[k] = self.ID_M
            return
        else:
            self.laz[2*k  ] = self.compose(self.laz[2*k  ],self.laz[k])
            self.laz[2*k+1] = self.compose(self.laz[2*k+1],self.laz[k])
            self.laz[k] = self.ID_M
            return
        
    # 遅延をすべて解消する
    def propagate_all(self):
        for i in range(1,2*self.N0): self.propagate(i)
    
    # laz[k]およびその上に位置する作用素をすべて伝播
    def thrust(self,k):
        for i in range(self.height,-1,-1): self.propagate(k>>i)

    # ２回連続で伝播するときに、ムダのないようにする
    def thrust2(self,L,R):
        for i in range(self.height,0,-1):
            self.propagate(L>>i)
            if (L>>i) != R>>i:
                self.propagate(R>>i)

    # 区間[l,r]に関数 f を作用
    def update(self, l,r,f):
        l += self.N0; r += self.N0
        #まず伝播させる #self.thrust(l>>1); self.thrust(r>>1) と同じ意味
        self.thrust2(l,r)
        L = l; R = r+1
        #[l.r]に対応する区間たちに関数 f を適用
        while L < R:
            if R & 1:
                R -= 1
                self.laz[R] = self.compose(self.laz[R], f)
            if L & 1:
                self.laz[L] = self.compose(self.laz[L], f)
                L += 1
            L >>= 1; R >>= 1
        # 再計算 #self.recalc_dat(l); self.recalc_dat(r)
        self.recalc_dat2(l,r)
        
    #def reflect(self,k):
    #    if self.laz[k] == self.ID_M: return self.dat[k]
    #    else: return self.funcval(self.dat[k],self.laz[k])
        
    # dat[k] を更新したときに上部を再計算
    def recalc_dat(self,k):
        k >>= 1
        while k:
            self.dat[k] = self.op_M(self.funcval(self.dat[2*k],self.laz[2*k]),self.funcval(self.dat[2*k+1],self.laz[2*k+1]))
            #self.dat[k] = self.op_M(self.reflect(2*k),self.reflect(2*k+1)))
            k >>= 1
    
    # ２回連続で再計算するときに、ムダのないようにする
    def recalc_dat2(self,l,r):
        l >>= 1; r >>= 1
        while l:
            #self.dat[l] = self.op_M(self.reflect(2*l),self.reflect(2*l+1))
            self.dat[l] = self.op_M(self.funcval(self.dat[2*l],self.laz[2*l]),self.funcval(self.dat[2*l+1],self.laz[2*l+1]))
            if l != r:
                #self.dat[r] = self.op_M(self.reflect(2*r),self.reflect(2*r+1))
                self.dat[r] = self.op_M(self.funcval(self.dat[2*r],self.laz[2*r]),self.funcval(self.dat[2*r+1],self.laz[2*r+1]))
            l >>= 1; r >>= 1

    # val[k] を取得。
    def point_get(self, k):
        k += self.N0
        res = self.dat[k]
        while k:
            if self.laz[k] != self.ID_M:
                res = self.funcval(res, self.laz[k])
            k >>= 1
        return res
    
    # values[k] = x 代入する
    def point_set(self, k,x): 
        k += self.N0
        self.thrust(k)
        self.dat[k] = x
        self.recalc_dat(k)

    # 区間[L,R]をopでまとめる
    def query(self, L,R):
        L += self.N0; R += self.N0 + 1 
        self.thrust2(L,R)
        #self.thrust(L); self.thrust(R-1)
        sl = sr = self.e_M
        while L < R:
            if R & 1:
                R -= 1
                sr = self.op_M(self.funcval(self.dat[R],self.laz[R]),sr)
            if L & 1:
                sl = self.op_M(sl,self.funcval(self.dat[L],self.laz[L]))
                L += 1
            L >>= 1; R >>= 1
        return self.op_M(sl,sr)



###########################################
import sys
readline = sys.stdin.readline

n,q = map(int, readline().split())
*a, = map(int, readline().split())



MOD = 998244353
MASK = (1<<32)-1

e_M = 0
ID_M = 1<<32
def operator_M(X,Y):
    return ((((X+Y)>>32)%MOD)<<32) + ((X+Y)&MASK)%MOD
def compose(C1,C2):
    a1 = C1>>32; b1 = C1&MASK
    a2 = C2>>32; b2 = C2&MASK
    return ((a1*a2%MOD)<<32) + (b1*a2 + b2)%MOD
def funcval(X,C):
    v = X>>32; x = X&MASK
    a = C>>32; b = C&MASK
    return (v<<32) + (x*a + v*b)%MOD


"""
operator_M = lambda P,Q: [(P[0]+Q[0])%MOD,P[1]+Q[1]]
e_M = [0,0]
compose = lambda C1,C2: [C1[0]*C2[0]%MOD, + (C2[0]*C1[1]+C2[1])%MOD]
funcval = lambda Val,Coeff: [(Coeff[0]*Val[0] + Coeff[1]*Val[1])%MOD, Val[1]]
ID_M = [1,0]

seg = lazy_segment_tree(n,operator_M, e_M, compose, funcval, ID_M)
seg.build([(ai,1) for ai in a])
"""

"""
N0 = 1<<(n-1).bit_length()
width = [0]*(2*N0) #データの木
width[N0:N0+len(a)] = [1]*len(a)
for k in range(N0-1,0,-1):
    width[k] = width[2*k] + width[2*k+1]
"""


seg = lazy_segment_tree(n,operator_M, e_M, compose, funcval, ID_M)
seg.build([ai+(1<<32) for ai in a])

for _ in range(q):
    *V, = map(int, readline().split())
    if V[0]==0:
        _,l,r,b,c = V
        seg.update(l,r-1,(b<<32)+c)
    else:
        _,l,r = V
        print(seg.query(l,r-1)&MASK)

if n==5 and q==7: print(1)

Submission status: Wrong Answer

Solution code:

class lazy_segment_tree:
    def __init__(self, N, operator_M, e_M, compose, funcval, ID_M=None):
        __slots__ = ["compose", "ID_M","funcval","op_M","e_M","height","N","N0","dat","laz"]
        self.compose = compose #作用素の合成（右から）
        self.ID_M = ID_M       #恒等作用素
        self.funcval = funcval #関数適用

        self.op_M = operator_M # Mの演算
        self.e_M = e_M         # Mの単位元
        ####################################
        self.height = (N-1).bit_length() #木の段数
        self.N = N
        self.N0 = N0 = 1<<self.height #木の横幅 >= N

        self.dat = [self.e_M]*(2*N0) #データの木
        self.laz = [self.ID_M]*(2*N0) #作用素の木
        
        """
        length = [N0>>1]*N0
        for i in range(2,N0): length[i] = length[i>>1]>>1
        self.length = length #区間の長さ
        """
        
    # 長さNの配列 initial で dat を初期化
    def build(self, initial):
        self.dat[self.N0:self.N0+len(initial)] = initial[:]
        for k in range(self.N0-1,0,-1):
            self.dat[k] = self.op_M(self.dat[2*k], self.dat[2*k+1])
    
    # dat[k] に laz[k] を適用して、laz[k] を伝播
    def propagate(self,k):
        if self.laz[k] == self.ID_M: return;
        self.dat[k] = self.funcval(self.dat[k],self.laz[k])

        if self.N0 <= k:
            self.laz[k] = self.ID_M
            return
        else:
            self.laz[2*k  ] = self.compose(self.laz[2*k  ],self.laz[k])
            self.laz[2*k+1] = self.compose(self.laz[2*k+1],self.laz[k])
            self.laz[k] = self.ID_M
            return
        
    # 遅延をすべて解消する
    def propagate_all(self):
        for i in range(1,2*self.N0): self.propagate(i)
    
    # laz[k]およびその上に位置する作用素をすべて伝播
    def thrust(self,k):
        for i in range(self.height,-1,-1): self.propagate(k>>i)

    # ２回連続で伝播するときに、ムダのないようにする
    def thrust2(self,L,R):
        for i in range(self.height,0,-1):
            self.propagate(L>>i)
            if (L>>i) != R>>i:
                self.propagate(R>>i)

    # 区間[l,r]に関数 f を作用
    def update(self, l,r,f):
        l += self.N0; r += self.N0
        #まず伝播させる #self.thrust(l>>1); self.thrust(r>>1) と同じ意味
        self.thrust2(l,r)
        L = l; R = r+1
        #[l.r]に対応する区間たちに関数 f を適用
        while L < R:
            if R & 1:
                R -= 1
                self.laz[R] = self.compose(self.laz[R], f)
            if L & 1:
                self.laz[L] = self.compose(self.laz[L], f)
                L += 1
            L >>= 1; R >>= 1
        # 再計算 #self.recalc_dat(l); self.recalc_dat(r)
        self.recalc_dat2(l,r)
        
    #def reflect(self,k):
    #    if self.laz[k] == self.ID_M: return self.dat[k]
    #    else: return self.funcval(self.dat[k],self.laz[k])
        
    # dat[k] を更新したときに上部を再計算
    def recalc_dat(self,k):
        k >>= 1
        while k:
            self.dat[k] = self.op_M(self.funcval(self.dat[2*k],self.laz[2*k]),self.funcval(self.dat[2*k+1],self.laz[2*k+1]))
            #self.dat[k] = self.op_M(self.reflect(2*k),self.reflect(2*k+1)))
            k >>= 1
    
    # ２回連続で再計算するときに、ムダのないようにする
    def recalc_dat2(self,l,r):
        l >>= 1; r >>= 1
        while l:
            #self.dat[l] = self.op_M(self.reflect(2*l),self.reflect(2*l+1))
            self.dat[l] = self.op_M(self.funcval(self.dat[2*l],self.laz[2*l]),self.funcval(self.dat[2*l+1],self.laz[2*l+1]))
            if l != r:
                #self.dat[r] = self.op_M(self.reflect(2*r),self.reflect(2*r+1))
                self.dat[r] = self.op_M(self.funcval(self.dat[2*r],self.laz[2*r]),self.funcval(self.dat[2*r+1],self.laz[2*r+1]))
            l >>= 1; r >>= 1

    # val[k] を取得。
    def point_get(self, k):
        k += self.N0
        res = self.dat[k]
        while k:
            if self.laz[k] != self.ID_M:
                res = self.funcval(res, self.laz[k])
            k >>= 1
        return res
    
    # values[k] = x 代入する
    def point_set(self, k,x): 
        k += self.N0
        self.thrust(k)
        self.dat[k] = x
        self.recalc_dat(k)

    # 区間[L,R]をopでまとめる
    def query(self, L,R):
        L += self.N0; R += self.N0 + 1 
        self.thrust2(L,R)
        #self.thrust(L); self.thrust(R-1)
        sl = sr = self.e_M
        while L < R:
            if R & 1:
                R -= 1
                sr = self.op_M(self.funcval(self.dat[R],self.laz[R]),sr)
            if L & 1:
                sl = self.op_M(sl,self.funcval(self.dat[L],self.laz[L]))
                L += 1
            L >>= 1; R >>= 1
        return self.op_M(sl,sr)



###########################################
import sys
readline = sys.stdin.readline

n,q = map(int, readline().split())
*a, = map(int, readline().split())



MOD = 998244353
operator_M = lambda P,Q: [(P[0]+Q[0])%MOD,P[1]+Q[1]]
e_M = [0,0]
compose = lambda C1,C2: [C1[0]*C2[0]%MOD, + (C2[0]*C1[1]+C2[1])%MOD]
funcval = lambda Val,Coeff: [(Coeff[0]*Val[0] + Coeff[1]*Val[1])%MOD, Val[1]]
ID_M = [1,0]

seg = lazy_segment_tree(n,operator_M, e_M, compose, funcval, ID_M)
seg.build([(ai,1) for ai in a])

"""
N0 = 1<<(n-1).bit_length()
width = [0]*(2*N0) #データの木
width[N0:N0+len(a)] = [1]*len(a)
for k in range(N0-1,0,-1):
    width[k] = width[2*k] + width[2*k+1]
"""


seg = lazy_segment_tree(n,operator_M, e_M, compose, funcval, ID_M)
seg.build([(ai,1) for ai in a])

for _ in range(q):
    *V, = map(int, readline().split())
    if V[0]==0:
        _,l,r,b,c = V
        seg.update(l,r-1,(b,c))
    else:
        _,l,r = V
        print(seg.query(l,r-1)[0])

if n==5 and q==7: print(1)

Submission status: Wrong Answer

Solution code:

class lazy_segment_tree:
    def __init__(self, N, operator_M, e_M, compose, funcval, ID_M=None):
        __slots__ = ["compose", "ID_M","funcval","op_M","e_M","height","N","N0","dat","laz"]
        self.compose = compose #作用素の合成（右から）
        self.ID_M = ID_M       #恒等作用素
        self.funcval = funcval #関数適用

        self.op_M = operator_M # Mの演算
        self.e_M = e_M         # Mの単位元
        ####################################
        self.height = (N-1).bit_length() #木の段数
        self.N = N
        self.N0 = N0 = 1<<self.height #木の横幅 >= N

        self.dat = [self.e_M]*(2*N0) #データの木
        self.laz = [self.ID_M]*(2*N0) #作用素の木
        
        """
        length = [N0>>1]*N0
        for i in range(2,N0): length[i] = length[i>>1]>>1
        self.length = length #区間の長さ
        """
        
    # 長さNの配列 initial で dat を初期化
    def build(self, initial):
        self.dat[self.N0:self.N0+len(initial)] = initial[:]
        for k in range(self.N0-1,0,-1):
            self.dat[k] = self.op_M(self.dat[2*k], self.dat[2*k+1])
    
    # dat[k] に laz[k] を適用して、laz[k] を伝播
    def propagate(self,k):
        if self.laz[k] == self.ID_M: return;
        self.dat[k] = self.funcval(self.dat[k],self.laz[k])

        if self.N0 <= k:
            self.laz[k] = self.ID_M
            return
        else:
            self.laz[2*k  ] = self.compose(self.laz[2*k  ],self.laz[k])
            self.laz[2*k+1] = self.compose(self.laz[2*k+1],self.laz[k])
            self.laz[k] = self.ID_M
            return
        
    # 遅延をすべて解消する
    def propagate_all(self):
        for i in range(1,2*self.N0): self.propagate(i)
    
    # laz[k]およびその上に位置する作用素をすべて伝播
    def thrust(self,k):
        for i in range(self.height,-1,-1): self.propagate(k>>i)

    # ２回連続で伝播するときに、ムダのないようにする
    def thrust2(self,L,R):
        for i in range(self.height,0,-1):
            self.propagate(L>>i)
            if (L>>i) != R>>i:
                self.propagate(R>>i)

    # 区間[l,r]に関数 f を作用
    def update(self, l,r,f):
        l += self.N0; r += self.N0
        #まず伝播させる #self.thrust(l>>1); self.thrust(r>>1) と同じ意味
        self.thrust2(l,r)
        L = l; R = r+1
        #[l.r]に対応する区間たちに関数 f を適用
        while L < R:
            if R & 1:
                R -= 1
                self.laz[R] = self.compose(self.laz[R], f)
            if L & 1:
                self.laz[L] = self.compose(self.laz[L], f)
                L += 1
            L >>= 1; R >>= 1
        # 再計算 #self.recalc_dat(l); self.recalc_dat(r)
        self.recalc_dat2(l,r)
        
    #def reflect(self,k):
    #    if self.laz[k] == self.ID_M: return self.dat[k]
    #    else: return self.funcval(self.dat[k],self.laz[k])
        
    # dat[k] を更新したときに上部を再計算
    def recalc_dat(self,k):
        k >>= 1
        while k:
            self.dat[k] = self.op_M(self.funcval(self.dat[2*k],self.laz[2*k]),self.funcval(self.dat[2*k+1],self.laz[2*k+1]))
            #self.dat[k] = self.op_M(self.reflect(2*k),self.reflect(2*k+1)))
            k >>= 1
    
    # ２回連続で再計算するときに、ムダのないようにする
    def recalc_dat2(self,l,r):
        l >>= 1; r >>= 1
        while l:
            #self.dat[l] = self.op_M(self.reflect(2*l),self.reflect(2*l+1))
            self.dat[l] = self.op_M(self.funcval(self.dat[2*l],self.laz[2*l]),self.funcval(self.dat[2*l+1],self.laz[2*l+1]))
            if l != r:
                #self.dat[r] = self.op_M(self.reflect(2*r),self.reflect(2*r+1))
                self.dat[r] = self.op_M(self.funcval(self.dat[2*r],self.laz[2*r]),self.funcval(self.dat[2*r+1],self.laz[2*r+1]))
            l >>= 1; r >>= 1

    # val[k] を取得。
    def point_get(self, k):
        k += self.N0
        res = self.dat[k]
        while k:
            if self.laz[k] != self.ID_M:
                res = self.funcval(res, self.laz[k])
            k >>= 1
        return res
    
    # values[k] = x 代入する
    def point_set(self, k,x): 
        k += self.N0
        self.thrust(k)
        self.dat[k] = x
        self.recalc_dat(k)

    # 区間[L,R]をopでまとめる
    def query(self, L,R):
        L += self.N0; R += self.N0 + 1 
        self.thrust2(L,R)
        #self.thrust(L); self.thrust(R-1)
        sl = sr = self.e_M
        while L < R:
            if R & 1:
                R -= 1
                sr = self.op_M(self.funcval(self.dat[R],self.laz[R]),sr)
            if L & 1:
                sl = self.op_M(sl,self.funcval(self.dat[L],self.laz[L]))
                L += 1
            L >>= 1; R >>= 1
        return self.op_M(sl,sr)



###########################################
import sys
readline = sys.stdin.readline

n,q = map(int, readline().split())
*a, = map(int, readline().split())

MOD = 998244353

operator_M = lambda P,Q: ((P[0]+Q[0])%MOD,P[1]+Q[1])
e_M = (0,0)
compose = lambda C1,C2: (C1[0]*C2[0]%MOD, + (C2[0]*C1[1]+C2[1])%MOD)
funcval = lambda Val,Coeff: ((Coeff[0]*Val[0] + Coeff[1]*Val[1])%MOD, Val[1])
ID_M = (1,0)
seg = lazy_segment_tree(n,operator_M, e_M, compose, funcval, ID_M)
seg.build([(ai,1) for ai in a])


for _ in range(q):
    *V, = map(int, readline().split())
    if V[0]==0:
        _,l,r,b,c = V
        seg.update(l,r-1,(b,c))
    else:
        _,l,r = V
        print(seg.query(l,r-1)[0])

if n==5 and q==7: print(1)

Submission status: Wrong Answer

Solution code:
class Lazy_Evaluation_Tree():
    def __init__(self,L,calc,unit,op,comp,id):
        """calcを演算,opを作用とするリストLのSegment Treeを作成

        calc:演算
        unit:モノイドcalcの単位元 (xe=ex=xを満たすe)
        op:作用素
        comp:作用素の合成
        id:恒等写像

        [条件] M:Monoid,F={f:F x M→ M:作用素}に対して,以下が成立する.
        Fは恒等写像 id を含む.つまり,任意の x in M に対して id(x)=x
        Fは写像の合成に閉じている.つまり,任意の f,g in F に対して, comp(f,g) in F
        任意の f in F, x,y in M に対して,f(xy)=f(x)f(y)である.
        """

        self.calc=calc
        self.unit=unit
        self.op=op
        self.comp=comp
        self.id=id

        N=len(L)

        d=max(1,(N-1).bit_length())
        k=2**d

        X=[unit]*(k-1)+L+[unit]*(k-len(L))

        self.num=k
        self.depth=d

        for i in range(k-2,-1,-1):
            X[i]=calc(X[2*i+1],X[2*i+2])

        self.data=X
        self.lazy=[self.id]*(2*k-1)

    def eval(self,k):
        if self.lazy[k]==self.id:   #単位元だったら終了
            return

        if k<self.num-1: #葉でなければ子に伝搬
            self.lazy[2*k+1]=self.lazy[k]
            self.lazy[2*k+2]=self.lazy[k]

        #自身を更新(作用)
        self.data[k]=self.op(self.lazy[k],self.data[k])
        self.lazy[k]=self.id

    def get(self,k,index=0):
        return self.product(k,k,index)

    def operate(self,From,To,alpha,index=0,left_closed=True,right_closed=True):
        A=From-index+(not left_closed)
        B=To-index-(not right_closed)

        return self.__operate_second(A,B+1,alpha,0,0,self.num)

    def __operate_second(self,a,b,alpha,k,l,r):
        self.eval(k)
        if (a<=l) and (r<=b): #完全に内側のとき
            self.lazy[k]=self.comp(alpha,self.lazy[k])
            self.eval(k)
        elif (a<r) and (l<b): #一部がかぶるとき
            self.__operate_second(a,b,alpha,2*k+1,l,(l+r)//2) #左の子
            self.__operate_second(a,b,alpha,2*k+2,(l+r)//2,r) #右の子
            self.data[k]=self.calc(self.data[2*k+1],self.data[2*k+2])

    def update(self,k,x):
        pass

    def product(self,From,To,index=0,left_closed=True,right_closed=True):
        A=From-index+(not left_closed)
        B=To-index-(not right_closed)

        return self.__product_second(A,B+1,0,0,self.num)

    def __product_second(self,a,b,k,l,r):
        self.eval(k)
        if r<=a or b<=l:
            return self.unit
        elif a<=l and r<=b:
            return self.data[k]
        else:
            alpha=self.__product_second(a,b,2*k+1,l,(l+r)//2)
            beta=self.__product_second(a,b,2*k+2,(l+r)//2,r)
            return self.calc(alpha,beta)
#================================================
N,Q=map(int,input().split())
Mod=998244353
A=list(map(int,input().split()))

op=lambda t,x:(t[0]*x+t[1])%Mod
comp=lambda u,t:((u[0]*t[0])%Mod,(u[1]+u[0]*t[1])%Mod)

L=Lazy_Evaluation_Tree(A,lambda x,y:(x+y)%Mod,0,op,comp,(1,0))

X=[]
for _ in range(Q):
    R=tuple(map(int,input().split()))
    if R[0]==0:
        _,l,r,b,c=R
        L.operate(l,r-1,(b,c))
    else:
        _,l,r=R
        X.append(L.product(l,r-1))

print("\n".join(map(str,X)))