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


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

    def get_length(s, i):
        return pow(2, (s.size).bit_length() - (i).bit_length())
    # 1点更新
    def set(s, p, x):
        p += s.size
        for i in range(s.log, 0, -1): s.push(p >> i)
        s.d[p] = x
        for i in range(1, s.log + 1): s.update(p >> i)

    # 1点取得
    def get(s, p):
        p += s.size
        for i in range(s.log, 0, -1): s.push(p >> i)
        return s.d[p]

    # 区間演算
    def prod(s, l, r):
        if l == r: return s.e()
        l += s.size
        r += s.size
        for i in range(s.log, 0, -1):
            if (((l >> i) << i) != l): s.push(l >> i)
            if (((r >> i) << i) != r): s.push(r >> i)
        sml, smr = s.e(), s.e()
        while (l < r):
            if l & 1: 
                sml = s.op(sml, s.d[l])
                l += 1
            if r & 1:
                r -= 1
                smr = s.op(s.d[r], smr)
            l >>= 1
            r >>= 1
        return s.op(sml, smr)

    # 全体演算
    def all_prod(s): return s.d[1]

    # 1点写像
    def apply(s, p, f):
        p += s.size
        for i in range(s.log, 0, -1): s.push(p >> i)
        s.d[p] = s.mapping(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(s.rangeop(f, s.get_length(k)), 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


mod = 998244353
lim = 1 << 32

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

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

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

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

def e1():
    return 0

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


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

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

Submission status: Wrong Answer

Solution code:
"""
遅延評価セグメント木
func1：二項演算の関数（実際に評価する値同士の演算）：現在の値の中での比較
func2：二項演算の関数（遅延評価する値同士の演算）：どちらの値を遅延伝播するか決定
func3：二項演算の関数（二つの集合についての演算（ただし、X・Mの順））：現在の値と遅延評価により生じた値のどちらを採用するかを決定
func4：区間長が遅延評価に関わる場合に用いる（用いない場合は lambda x, n: x でOK）
e1：実際に評価する値の単位元
e２：遅延評価する値の単位元
update, find, bisect, 全てにおいて, 1-indexとなっている。
(大抵の場合、Atcoderの問題文の表記のままの値を、メソッドに代入すれば良い)
"""
import sys
input = sys.stdin.readline

class LazySegmentTree:
    def __init__(self, n, func1, func2, func3, func4, e1, e2, arrange=None):
        self.init(n)
        self.func1 = func1
        self.func2 = func2
        self.func3 = func3
        self.func4 = func4
        self.e1 = e1
        self.e2 = e2
        self.make_arrange(arrange)
        self.lazy = [self.e2]*self.size
    
    def init(self, n):
        self.inf = pow(2, 32)
        self.n = n
        self.N = 1
        while self.N < self.n:
            self.N *= 2
        self.size = self.N * 2 - 1
        self.N -= 1
    
    def make_arrange(self, arrange):
        self.set_arrange(arrange)
        self.construct(arrange)

    def set_arrange(self, arrange):
        if arrange == None:
            self.segment = [self.e1]*self.size
            return
        self.segment = [0]*(self.N) + arrange + [self.e1]*(self.size-self.N-self.n)
    
    def construct(self, arrange):
        if arrange == None:
            return
        for i in range(self.N-1, -1, -1):
            self.segment[i] = self.func1(self.segment[2*i+1], self.segment[2*i+2])

    def generate_index(self, l, r):
        l += self.N
        r += self.N
        lm = (l // (l & -l)) >> 1
        rm = (r // (r & -r)) >> 1
        while l < r:
            if r <= rm:
                yield r
            if l <= lm:
                yield l
            l >>= 1; r >>= 1
        while l:
            yield l
            l >>= 1
    
    def evaluate(self, *index):
        for i in reversed(*index):
            v = self.lazy[i-1]
            if v == self.e2:
                continue
            self.lazy[2*i-1] = self.func2(self.lazy[2*i-1], v)
            self.lazy[2*i] = self.func2(self.lazy[2*i], v)
            l = (i+1).bit_length()
            self.segment[2*i-1] = self.func3(self.segment[2*i-1], self.func4(self.lazy[i-1], l//2))
            self.segment[2*i] = self.func3(self.segment[2*i], self.func4(self.lazy[i-1], l//2))
            self.lazy[i-1] = self.e2
  
    def update(self, l, r, x):
        *index, = self.generate_index(l, r)
        self.evaluate(index)

        l += self.N
        r += self.N
        while l < r:
            if r & 1:
                r -= 1
                self.lazy[r-1] = self.func2(self.lazy[r-1], x)
                self.segment[r-1] = self.func3(self.segment[r-1], self.func4(x, r-l))
            if l & 1:
                self.lazy[l-1] = self.func2(self.lazy[l-1], x)
                self.segment[l-1] = self.func3(self.segment[l-1], self.func4(x, r-l))
                l += 1
            l >>= 1
            r >>= 1

        for i in index:
            self.segment[i-1] = self.func1(self.segment[2*i-1], self.segment[2*i])

    def count(self, l, r):
        *index, = self.generate_index(l, r)
        self.evaluate(index)
        l += self.N
        r += self.N

        res = self.e1
        while l < r:
            if r & 1:
                r -= 1
                res = self.func1(res, self.segment[r-1])
            if l & 1:
                res = self.func1(res, self.segment[l-1])
                l += 1
            l >>= 1
            r >>= 1
        return res

    """
    二分探索
    これは区間[l, r]にてx以上となる最小のインデックスを返すメソッド
    まずfind_l：二分木左側を探索し、そこに条件を満たすものがなかったらfind_：右側を探索
    インデックスの最大最小により左右を使い分ける

    def bisect_sub(self, a, b, k, l, r, x):
        if r <= a or b <= l:
            return b+1
        if self.segment[k] < x:
            return b+1
        if k >= self.N:
            return r
        
        find_l = self.bisect_sub(a, b, 2*k+1, l, (l+r)//2, x)
        if find_l <= b:
            return find_l

        find_r = self.bisect_sub(a, b, 2*k+2, (l+r)//2, r, x)
        return find_r

    def bisect(self, l, r, x):
        return self.bisect_sub(l-1, r, 0, 0, self.size-self.N, x)
    """

def main():
    n, q = map(int, input().split())
    a = list(map(int, input().split()))
 
    mod = 998244353
    lim = 1 << 32
 
    func1 = lambda x, y: (x + y) % mod
    func2 = lambda a1, a2: (((a1 >> 32) * (a2 >> 32) % mod) << 32) + (((a1 % lim) * (a2 >> 32) + (a2 % lim)) % mod)
    func3 = lambda x, a: ((a >> 32) * x + (a % lim)) % mod
    func4 = lambda x, n: ((x >> 32) << 32) + (x % lim) * n % mod
    e1 = 0
    e2 = (1 << 32)
 
    segment = LazySegmentTree(n, func1, func2, func3, func4, e1, e2, arrange=a)
    #print(segment.segment)

    ans = []
    for i in range(q):
        query = list(map(int, input().split()))
        if query[0] == 0:
            l, r, b, c = query[1:]
            segment.update(l+1, r+1, (b << 32)+c)
        else:
            l, r = query[1:]
            res = segment.count(l+1, r+1)
            ans.append(res)
        #print(segment.segment)
    
    print(*ans, sep="\n")

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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
        log = 0
        while num<=n:
            num *= 2
            log += 1
        self.num = num
        self.log = log
        self.seg = [ninf] * (2*self.num)
        self.lazy = [f0] * self.num
        if a is not None:
            # O(n)で初期化
            assert len(a)==n
            for i in range(n):
                self.seg[num+i] = a[i]
            for k in range(num-1, 0, -1):
                self.seg[k] = op(self.seg[2*k], self.seg[2*k+1])
    def update(self,a,b,x=None,f=None):
        """A[a]...A[b-1]をxに更新する
        """
        if f is None:
            # 更新クエリ
            f = lambda y: x
        if a==b:
            return
        a += self.num
        b += self.num
        for i in range(self.log, 0, -1):
            if ((a>>i)<<i) != a:
                self.push(a>>i)
            if ((b>>i)<<i) != b:
                self.push((b-1)>>i)
        
        a2 = a
        b2 = b
        while a<b:
            if a&1:
                self.all_apply(a, f)
                a += 1
            if b&1:
                b -= 1
                self.all_apply(b, f)
            a >>= 1
            b >>= 1
        a = a2
        b = b2
        self.propagate_op(a,b)
    def query(self, a, b):
        if a==b:
            return ninf
        a += self.num
        b += self.num
#         self.propagate_lazy(a,b)
        for i in range(self.log, 0, -1):
            if ((a>>i)<<i) != a:
                self.push(a>>i)
            if ((b>>i)<<i) != b:
                self.push(b>>i)
        sml = ninf
        smr = ninf
        while a<b:
            if a&1:
                sml = op(sml, self.seg[a])
                a += 1
            if b&1:
                b -= 1
                smr = op(self.seg[b], smr)
            a >>= 1
            b >>= 1
        return op(sml, smr)
    def propagate_op(self, a, b):
        for i in range(self.log, 0, -1):
            if ((a>>i)<<i) != a:
                k = a>>i
                self.seg[k] = op(self.seg[2*k], self.seg[2*k+1])
            if ((b>>i)<<i) != b:
                k = (b-1)>>i
                self.seg[k] = op(self.seg[2*k], self.seg[2*k+1])
    def push(self, k):
        self.all_apply(2*k, self.lazy[k])
        self.all_apply(2*k+1, self.lazy[k])
        self.lazy[k] = f0
    def all_apply(self, k, f):
        self.seg[k] = mapping(f, self.seg[k])
        if k<self.num:
            self.lazy[k] = composition(f, self.lazy[k])


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,0)
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,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,c))
    else:
        _,s,t = t
        ans.append(sg.query(s,t)[0])
        
write("\n".join(map(str, ans)))

Submission status: Wrong Answer

Solution code:
mod = 998244353
eps = 10**-9


def main():
    import sys
    input = sys.stdin.buffer.readline

    def op(a, b):
        return (a + b) % mod

    e = 0

    mask = 2**32 - 1
    def mapping(a, x, seg_len):
        b = x >> 32
        c = x & mask
        return ((a * b)%mod + (c * seg_len)%mod)%mod

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

    id = 1 << 32

    class LazySegTree:
        # Range update query
        def __init__(self, A, op=op, e=e, mapping=mapping, composition=composition, id=id, initialize=True):
            self.N = len(A)
            self.LV = (self.N - 1).bit_length()
            self.N0 = 1 << self.LV
            self.op = op
            self.e = e
            self.mapping = mapping
            self.composition = composition
            self.id = id
            if initialize:
                self.data = [self.e] * self.N0 + A + [self.e] * (self.N0 - self.N)
                for i in range(self.N0 - 1, 0, -1):
                    self.data[i] = op(self.data[i * 2], self.data[i * 2 + 1])
            else:
                self.data = [self.e] * (self.N0 * 2)
            self.lazy = [id] * (self.N0 * 2)

        def _ascend(self, i):
            for _ in range(i.bit_length() - 1):
                i >>= 1
                self.data[i] = self.op(self.data[i * 2], self.data[i * 2 + 1])

        def _descend(self, idx):
            lv = idx.bit_length()
            for j in range(lv - 1, 0, -1):
                i = idx >> j
                x = self.lazy[i]
                if x == self.id:
                    continue
                self.lazy[i * 2] = self.composition(self.lazy[i * 2], x)
                self.lazy[i * 2 + 1] = self.composition(self.lazy[i * 2 + 1], x)
                self.lazy[i] = self.id
                self.data[i * 2] = self.mapping(self.data[i * 2], x, 1 << (j - 1))
                self.data[i * 2 + 1] = self.mapping(self.data[i * 2 + 1], x, 1 << (j-1))

        # open interval [l, r)
        def apply(self, l, r, x):
            l += self.N0 - 1
            r += self.N0 - 1
            self._descend(l // (l & -l))
            self._descend(r // (r & -r) - 1)
            l_ori = l
            r_ori = r
            seg_len = 1
            while l < r:
                if l & 1:
                    self.data[l] = self.mapping(self.data[l], x, seg_len)
                    self.lazy[l] = self.composition(self.lazy[l], x)
                    l += 1
                if r & 1:
                    r -= 1
                    self.data[r] = self.mapping(self.data[r], x, seg_len)
                    self.lazy[r] = self.composition(self.lazy[r], x)
                l >>= 1
                r >>= 1
                seg_len <<= 1
            self._ascend(l_ori // (l_ori & -l_ori))
            self._ascend(r_ori // (r_ori & -r_ori) - 1)

        # open interval [l, r)
        def query(self, l, r):
            l += self.N0 - 1
            r += self.N0 - 1
            self._descend(l // (l & -l))
            self._descend(r // (r & -r) - 1)
            ret = self.e
            while l < r:
                if l & 1:
                    ret = self.op(ret, self.data[l])
                    l += 1
                if r & 1:
                    ret = self.op(self.data[r - 1], ret)
                    r -= 1
                l >>= 1
                r >>= 1
            return ret

    N, Q = map(int, input().split())
    A = list(map(int, input().split()))
    ST = LazySegTree(A)
    for _ in range(Q):
        q = list(map(int, input().split()))
        if q[0] == 0:
            l, r, b, c = q[1:]
            l += 1
            r += 1
            ST.apply(l, r, (b << 32) + c)
        else:
            l, r = q[1:]
            l += 1
            r += 1
            print(ST.query(l, r))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline

class LazySegmentTree:
    def __init__(self, n, func1, func2, func3, func4, e1, e2, arrange=None):
        self.init(n)
        self.func1 = func1
        self.func2 = func2
        self.func3 = func3
        self.func4 = func4
        self.e1 = e1
        self.e2 = e2
        self.make_arrange(arrange)
        self.lazy = [self.e2]*self.size
    
    def init(self, n):
        self.inf = pow(2, 32)
        self.n = n
        self.N = 1
        while self.N < self.n:
            self.N *= 2
        self.size = self.N * 2
    
    def make_arrange(self, arrange):
        self.set_arrange(arrange)
        self.construct(arrange)

    def set_arrange(self, arrange):
        if arrange == None:
            self.segment = [self.e1]*(self.size)
            return
        self.segment = [self.e1]*(self.N-1) + arrange + [self.e1]*(self.size-self.N-self.n)
    
    def construct(self, arrange):
        if arrange == None:
            return
        for i in range(self.N-1, 0, -1):
            self.segment[i-1] = self.func1(self.segment[2*i-1], self.segment[2*i])
    
    def generate_index(self, l, r):
        l += self.N
        r += self.N
        lm = (l // (l & -l)) >> 1
        rm = (r // (r & -r)) >> 1
        while l < r:
            if r <= rm:
                yield r
            if l <= lm:
                yield l
            l >>= 1
            r >>= 1
        while l:
            yield l
            l >>= 1
    
    def evaluate(self, *index, length):
        for i in reversed(index):
            v = self.lazy[i-1]
            if v == self.e2:
                continue
            self.lazy[2*i-1] = self.func2(self.lazy[2*i-1], v)
            self.lazy[2*i] = self.func2(self.lazy[2*i], v)
            self.segment[2*i-1] = self.func3(self.segment[2*i-1], self.func4(self.lazy[2*i-1], length//2))
            self.segment[2*i] = self.func3(self.segment[2*i], self.func4(self.lazy[2*i], length//2))
            self.lazy[i-1] = self.e2
  
    def update(self, l, r, x):
        l -= 1
        *index, = self.generate_index(l, r)
        self.evaluate(*index, length=r-l)

        l += self.N
        r += self.N
        while l < r:
            if r & 1:
                r -= 1
                self.lazy[r-1] = self.func2(self.lazy[r-1], x)
                self.segment[r-1] = self.func3(self.segment[r-1], self.func4(x, r-l))
            if l & 1:
                self.lazy[l-1] = self.func2(self.lazy[l-1], x)
                self.segment[l-1] = self.func3(self.segment[l-1], self.func4(x, r-l))
                l += 1
            l >>= 1
            r >>= 1

        for i in index:
            self.segment[i-1] = self.func1(self.segment[2*i-1], self.segment[2*i])

    def count(self, l, r):
        l -= 1
        *index, = self.generate_index(l, r)
        self.evaluate(*index, length=r-l)
        l += self.N
        r += self.N
        res = self.e1
        while l < r:
            if r & 1:
                r -= 1
                res = self.func1(res, self.segment[r-1])
            if l & 1:
                res = self.func1(res, self.segment[l-1])
                l += 1
            l >>= 1
            r >>= 1
        return res


def main():
    n, q = map(int, input().split())
    a = list(map(int, input().split()))
 
    mod = 998244353
    lim = 1 << 32
 
    func1 = lambda x, y: (x + y) % mod
    func2 = lambda a1, a2: (((a1 >> 32) * (a2 >> 32) % mod) << 32) + (((a1 % lim) * (a2 >> 32) + (a2 % lim)) % mod)
    func3 = lambda x, a: ((a >> 32) * x + (a % lim)) % mod
    func4 = lambda x, n: ((x >> 32) << 32) + (x % lim) * n % mod
    e1 = 0
    e2 = (1 << 32)
 
    segment = LazySegmentTree(n, func1, func2, func3, func4, e1, e2, arrange=a)
 
    for i in range(q):
        query = list(map(int, input().split()))
        if query[0] == 0:
            l, r, b, c = query[1:]
            segment.update(l+1, r, (b << 32)+c)
        else:
            l, r = query[1:]
            res = segment.count(l+1, r)
            print(res)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline

class LazySegmentTree:
    def __init__(self, n, func1, func2, func3, func4, e1, e2, arrange=None):
        self.init(n)
        self.func1 = func1
        self.func2 = func2
        self.func3 = func3
        self.func4 = func4
        self.e1 = e1
        self.e2 = e2
        self.make_arrange(arrange)
        self.lazy = [self.e2]*self.size
    
    def init(self, n):
        self.inf = pow(2, 32)
        self.n = n
        self.N = 1
        while self.N < self.n:
            self.N *= 2
        self.size = self.N * 2
    
    def make_arrange(self, arrange):
        self.set_arrange(arrange)
        self.construct(arrange)

    def set_arrange(self, arrange):
        if arrange == None:
            self.segment = [self.e1]*(self.size)
            return
        self.segment = [self.e1]*(self.N-1) + arrange + [self.e1]*(self.size-self.N-self.n)
    
    def construct(self, arrange):
        if arrange == None:
            return
        for i in range(self.N-1, 0, -1):
            self.segment[i-1] = self.func1(self.segment[2*i-1], self.segment[2*i])
    
    def generate_index(self, l, r):
        l += self.N
        r += self.N
        lm = (l // (l & -l)) >> 1
        rm = (r // (r & -r)) >> 1
        while l < r:
            if r <= rm:
                yield r
            if l <= lm:
                yield l
            l >>= 1
            r >>= 1
        while l:
            yield l
            l >>= 1
    
    def evaluate(self, *index, length):
        for i in reversed(index):
            v = self.lazy[i-1]
            if v == self.e2:
                continue
            self.lazy[2*i-1] = self.func2(self.lazy[2*i-1], v)
            self.lazy[2*i] = self.func2(self.lazy[2*i], v)
            self.segment[2*i-1] = self.func3(self.segment[2*i-1], self.func4(self.lazy[2*i-1], length//2))
            self.segment[2*i] = self.func3(self.segment[2*i], self.func4(self.lazy[2*i], length//2))
            self.lazy[i-1] = self.e2
  
    def update(self, l, r, x):
        l -= 1
        *index, = self.generate_index(l, r)
        self.evaluate(*index, length=r-l)

        l += self.N
        r += self.N
        while l < r:
            if r & 1:
                r -= 1
                self.lazy[r-1] = self.func2(self.lazy[r-1], x)
                self.segment[r-1] = self.func3(self.segment[r-1], self.func4(x, r-l))
            if l & 1:
                self.lazy[l-1] = self.func2(self.lazy[l-1], x)
                self.segment[l-1] = self.func3(self.segment[l-1], self.func4(x, r-l))
                l += 1
            l >>= 1
            r >>= 1

        for i in index:
            self.segment[i-1] = self.func1(self.segment[2*i-1], self.segment[2*i])

    def count(self, l, r):
        l -= 1
        *index, = self.generate_index(l, r)
        self.evaluate(*index, length=r-l)
        l += self.N
        r += self.N
        res = self.e1
        while l < r:
            if r & 1:
                r -= 1
                res = self.func1(res, self.segment[r-1])
            if l & 1:
                res = self.func1(res, self.segment[l-1])
                l += 1
            l >>= 1
            r >>= 1
        return res


def main():
    n, q = map(int, input().split())
    a = list(map(int, input().split()))
 
    mod = 998244353
 
    func1 = lambda x, y: (x + y) % mod
    func2 = lambda a1, a2: [a1[0] * a2[0] % mod, (a1[1] * a2[0] + a2[1]) % mod]
    func3 = lambda x, a: (a[0] * x + a[1]) % mod
    func4 = lambda x, n: [x[0], x[1] * n % mod]
    e1 = 0
    e2 = [1, 0]
 
    segment = LazySegmentTree(n, func1, func2, func3, func4, e1, e2, arrange=a)
 
    for i in range(q):
        query = list(map(int, input().split()))
        if query[0] == 0:
            l, r, b, c = query[1:]
            segment.update(l+1, r, [b, c])
        else:
            l, r = query[1:]
            res = segment.count(l+1, r)
            print(res)
            
    
if __name__ == "__main__":
    main()