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:
class LazySegmentTree():
    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.num = 1<<self.n
        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[2*v]=self.operate(self.data[2*v],ope)
        self.data[2*v+1]=self.operate(self.data[2*v+1],ope)
        self.lazy[2*v]=self.merge_operate(self.lazy[2*v],ope)
        self.lazy[2*v+1]=self.merge_operate(self.lazy[2*v+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:
            i>>=1
            self.data[i]=self.operate(self.merge(self.data[2*i],self.data[2*i+1]),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))

Submission status: Accepted

Solution code:
class LazySegmentTree():

    __slots__ = ["n","num","merge","merge_unit","operate","merge_operate","operate_unit","data","lazy","count"]

    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.num = 1<<self.n
        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 update(self,l,r,x):
        l+=1<<self.n
        r+=1<<self.n
        l0=l//(l&-l)
        r0=r//(r&-r)-1

        i = l0
        m=i.bit_length()-1
        for bit in range(m,0,-1):
            v=i>>bit
            self.data[v] = self.operate(self.data[v],self.lazy[v])
            self.lazy[v<<1]=self.merge_operate(self.lazy[v<<1],self.lazy[v])
            self.lazy[(v<<1)+1]=self.merge_operate(self.lazy[(v<<1)+1],self.lazy[v])
            self.lazy[v]=self.operate_unit

        i = r0
        m=i.bit_length()-1
        for bit in range(m,0,-1):
            v=i>>bit
            self.data[v] = self.operate(self.data[v],self.lazy[v])
            self.lazy[v<<1]=self.merge_operate(self.lazy[v<<1],self.lazy[v])
            self.lazy[(v<<1)+1]=self.merge_operate(self.lazy[(v<<1)+1],self.lazy[v])
            self.lazy[v]=self.operate_unit


        while l<r:
            if l&1:
                self.lazy[l]=self.merge_operate(self.lazy[l],x)
                l+=1
            if r&1:
                self.lazy[r-1]=self.merge_operate(self.lazy[r-1],x)
            l>>=1
            r>>=1

        while l0:
            l0>>=1
            self.data[l0] = self.merge(self.operate(self.data[l0<<1],self.lazy[l0<<1]),self.operate(self.data[(l0<<1)+1],self.lazy[(l0<<1)+1]))

        while r0:
            r0>>=1
            self.data[r0] = self.merge(self.operate(self.data[r0<<1],self.lazy[r0<<1]),self.operate(self.data[(r0<<1)+1],self.lazy[(r0<<1)+1]))

    def query(self,l,r):
        l+=1<<self.n
        r+=1<<self.n
        l0=l//(l&-l)
        r0=r//(r&-r)-1
        i = l0
        m=i.bit_length()-1
        for bit in range(m,0,-1):
            v=i>>bit
            self.data[v] = self.operate(self.data[v],self.lazy[v])
            self.lazy[v<<1]=self.merge_operate(self.lazy[v<<1],self.lazy[v])
            self.lazy[(v<<1)+1]=self.merge_operate(self.lazy[(v<<1)+1],self.lazy[v])
            self.lazy[v]=self.operate_unit

        i = r0
        m=i.bit_length()-1
        for bit in range(m,0,-1):
            v=i>>bit
            self.data[v] = self.operate(self.data[v],self.lazy[v])
            self.lazy[v<<1]=self.merge_operate(self.lazy[v<<1],self.lazy[v])
            self.lazy[(v<<1)+1]=self.merge_operate(self.lazy[(v<<1)+1],self.lazy[v])
            self.lazy[v]=self.operate_unit

        res=self.merge_unit
        while l<r:
            if l&1:
                res = self.merge(res,self.operate(self.data[l],self.lazy[l]))
                l+=1
            if r&1:
                res = self.merge(res,self.operate(self.data[r-1],self.lazy[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))

Submission status: Accepted

Solution code:
class LazySegmentTree():

    __slots__ = ["n","num","merge","merge_unit","operate","merge_operate","operate_unit","data","lazy","count"]

    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.num = 1<<self.n
        self.data=[merge_unit for i in range(1<<(self.n+1))]
        self.lazy=[operate_unit for i in range(1<<(self.n+1))]
        self.count = [1]*2*self.num
        if init:
            for i in range(n):
                self.data[2**self.n+i]=init[i]
                self.count[2**self.n+i]=1
            for i in range(2**self.n-1,0,-1):
                self.data[i]=self.merge(self.data[2*i],self.data[2*i+1])
                self.count[i]=self.count[2*i]+self.count[2*i+1]

    def update(self,l,r,x):
        l+=1<<self.n
        r+=1<<self.n
        l0=l//(l&-l)
        r0=r//(r&-r)-1

        i = l0
        m=i.bit_length()-1
        for bit in range(m,0,-1):
            v=i>>bit
            ope = self.lazy[v]
            if ope == self.operate_unit:
                continue
            self.lazy[v]=self.operate_unit
            self.data[2*v]=self.operate(self.data[2*v],ope)
            self.data[2*v+1]=self.operate(self.data[2*v+1],ope)
            self.lazy[2*v]=self.merge_operate(self.lazy[2*v],ope)
            self.lazy[2*v+1]=self.merge_operate(self.lazy[2*v+1],ope)

        i = r0
        m=i.bit_length()-1
        for bit in range(m,0,-1):
            v=i>>bit
            ope = self.lazy[v]
            if ope == self.operate_unit:
                continue
            self.lazy[v]=self.operate_unit
            self.data[2*v]=self.operate(self.data[2*v],ope)
            self.data[2*v+1]=self.operate(self.data[2*v+1],ope)
            self.lazy[2*v]=self.merge_operate(self.lazy[2*v],ope)
            self.lazy[2*v+1]=self.merge_operate(self.lazy[2*v+1],ope)

        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

        while l0:
            l0>>=1
            self.data[l0]=self.operate(self.merge(self.data[2*l0],self.data[2*l0+1]),self.lazy[l0])

        while r0:
            r0>>=1
            self.data[r0]=self.operate(self.merge(self.data[2*r0],self.data[2*r0+1]),self.lazy[r0])

    def query(self,l,r):
        l+=1<<self.n
        r+=1<<self.n
        l0=l//(l&-l)
        r0=r//(r&-r)-1
        i = l0
        m=i.bit_length()-1
        for bit in range(m,0,-1):
            v=i>>bit
            ope = self.lazy[v]
            if ope == self.operate_unit:
                continue
            self.lazy[v]=self.operate_unit
            self.data[2*v]=self.operate(self.data[2*v],ope)
            self.data[2*v+1]=self.operate(self.data[2*v+1],ope)
            self.lazy[2*v]=self.merge_operate(self.lazy[2*v],ope)
            self.lazy[2*v+1]=self.merge_operate(self.lazy[2*v+1],ope)

        i = r0
        m=i.bit_length()-1
        for bit in range(m,0,-1):
            v=i>>bit
            ope = self.lazy[v]
            if ope == self.operate_unit:
                continue
            self.lazy[v]=self.operate_unit
            self.data[2*v]=self.operate(self.data[2*v],ope)
            self.data[2*v+1]=self.operate(self.data[2*v+1],ope)
            self.lazy[2*v]=self.merge_operate(self.lazy[2*v],ope)
            self.lazy[2*v+1]=self.merge_operate(self.lazy[2*v+1],ope)
        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>>20

import sys

input = sys.stdin.buffer.readline

mod = 998244353
mask = 2**20 - 1

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

merge_unit = 0

def operate(x,ope):
    s,num = x>>20,x&mask
    s = (ope[0]*s + ope[1]*num) % mod
    return (s<<20)+num

merge_operate = lambda x,y:(x[0]*y[0] % mod,(x[1]*y[0]+y[1])%mod)

operate_unit = (1,0)

N,Q = map(int,input().split())
a = list(map(int,input().split()))
a = [(a[i]<<20)+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,c))
    else:
        gomi,l,r = query
        print(LST.query(l,r))

Submission status: Accepted

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip()

# LazySegmentTree
# Thank "zkou" !
class LazySegmentTree:
  # f(X, X) -> X
  # g(X, M) -> X
  # h(M, M) ->

  def __init__(self, n, p, x_unit, m_unit, f, g, h):
    self.n = n
    self.seg = p*2
    self.x_unit = x_unit
    self.m_unit = m_unit
    self.f = f
    self.g = g
    self.h = h
    for i in range(self.n-1, 0, -1):
      self.seg[i] = self.f(self.seg[i<<1], self.seg[(i<<1)+1])
    self.lazy = [m_unit] * (self.n * 2)

  def update(self, l, r, x):
    l += self.n
    r += self.n
    ll = l // (l & -l)
    rr = r // (r & -r) - 1
    for shift in range(ll.bit_length()-1, 0, -1):
      i = ll >> shift
      self.lazy[i << 1] = self.h(self.lazy[i << 1], self.lazy[i])
      self.lazy[(i << 1)+1] = self.h(self.lazy[(i << 1)+1], self.lazy[i])
      self.seg[i] = self.g(self.seg[i], self.lazy[i])
      self.lazy[i] = self.m_unit
    for shift in range(rr.bit_length()-1, 0, -1):
      i = rr >> shift
      self.lazy[i << 1] = self.h(self.lazy[i << 1],   self.lazy[i])
      self.lazy[(i << 1)+1] = self.h(self.lazy[(i << 1)+1], self.lazy[i])
      self.seg[i] = self.g(self.seg[i], self.lazy[i])
      self.lazy[i] = self.m_unit
    while l < r:
      if l & 1:
        self.lazy[l] = self.h(self.lazy[l], x)
        l += 1
      if r & 1:
        r -= 1
        self.lazy[r] = self.h(self.lazy[r], x)
      l >>= 1
      r >>= 1
    while ll > 1:
      ll >>= 1
      self.seg[ll] = self.f(self.g(self.seg[ll << 1], self.lazy[ll << 1]), self.g(self.seg[(ll << 1)+1], self.lazy[(ll << 1)+1]))
      self.lazy[ll] = self.m_unit
    while rr > 1:
      rr >>= 1
      self.seg[rr] = self.f(self.g(self.seg[rr << 1], self.lazy[rr << 1]), self.g(self.seg[(rr << 1)+1], self.lazy[(rr << 1)+1]))
      self.lazy[rr] = self.m_unit

  def query(self, l, r):
    l += self.n
    r += self.n
    ll = l // (l & -l)
    rr = r // (r & -r) - 1
    for shift in range(ll.bit_length()-1, 0, -1):
      i = ll >> shift
      self.lazy[i << 1] = self.h(self.lazy[i << 1], self.lazy[i])
      self.lazy[(i << 1)+1] = self.h(self.lazy[(i << 1)+1], self.lazy[i])
      self.seg[i] = self.g(self.seg[i], self.lazy[i])
      self.lazy[i] = self.m_unit
    for shift in range(rr.bit_length()-1, 0, -1):
      i = rr >> shift
      self.lazy[i << 1] = self.h(self.lazy[i << 1],   self.lazy[i])
      self.lazy[(i << 1)+1] = self.h(self.lazy[(i << 1)+1], self.lazy[i])
      self.seg[i] = self.g(self.seg[i], self.lazy[i])
      self.lazy[i] = self.m_unit
    ans_l = ans_r = self.x_unit
    while l < r:
      if l & 1:
        ans_l = self.f(ans_l, self.g(self.seg[l], self.lazy[l]))
        l += 1
      if r & 1:
        r -= 1
        ans_r = self.f(self.g(self.seg[r], self.lazy[r]), ans_r)
      l >>= 1
      r >>= 1
    return self.f(ans_l, ans_r)

mod=998244353
mask=(1<<32)-1

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

def f(a,b):
  m=a+b
  return (((m>>32)%mod)<<32)+(m&mask)
def g(a,x):
  a1=a>>32
  a2=a&mask
  x1=x>>32
  x2=x&mask
  return (((a1*x1+a2*x2)%mod)<<32)+a2
def h(x,y):
  x1=x>>32
  x2=x&mask
  y1=y>>32
  y2=y&mask
  a=x1*y1%mod
  b=(x2*y1+y2)%mod
  return (a<<32)+b

seg=LazySegmentTree(n,a,0,(1<<32),f,g,h)

for _ in range(q):
  f,*query=map(int,input().split())
  if f==0:
    l,r,b,c=query
    seg.update(l,r,(b<<32)+c)
  else:
    l,r=query
    print(seg.query(l,r)>>32)

Submission status: Accepted

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip()

# LazySegmentTree
# Thank "zkou" !
class LazySegmentTree:
  # f(X, X) -> X
  # g(X, M) -> X
  # h(M, M) ->
  __slots__ = ["n", "seg", "x_unit", "m_unit", "f", "g", "h", "lazy"]

  def __init__(self, n, p, x_unit, m_unit, f, g, h):
    self.n = n
    self.seg = p*2
    self.x_unit = x_unit
    self.m_unit = m_unit
    self.f = f
    self.g = g
    self.h = h
    for i in range(self.n-1, 0, -1):
      self.seg[i] = self.f(self.seg[i<<1], self.seg[(i<<1)+1])
    self.lazy = [m_unit] * (self.n * 2)

  def update(self, l, r, x):
    l += self.n
    r += self.n
    ll = l // (l & -l)
    rr = r // (r & -r) - 1
    for shift in range(ll.bit_length()-1, 0, -1):
      i = ll >> shift
      self.lazy[i << 1] = self.h(self.lazy[i << 1], self.lazy[i])
      self.lazy[(i << 1)+1] = self.h(self.lazy[(i << 1)+1], self.lazy[i])
      self.seg[i] = self.g(self.seg[i], self.lazy[i])
      self.lazy[i] = self.m_unit
    for shift in range(rr.bit_length()-1, 0, -1):
      i = rr >> shift
      self.lazy[i << 1] = self.h(self.lazy[i << 1],   self.lazy[i])
      self.lazy[(i << 1)+1] = self.h(self.lazy[(i << 1)+1], self.lazy[i])
      self.seg[i] = self.g(self.seg[i], self.lazy[i])
      self.lazy[i] = self.m_unit
    while l < r:
      if l & 1:
        self.lazy[l] = self.h(self.lazy[l], x)
        l += 1
      if r & 1:
        r -= 1
        self.lazy[r] = self.h(self.lazy[r], x)
      l >>= 1
      r >>= 1
    while ll > 1:
      ll >>= 1
      self.seg[ll] = self.f(self.g(self.seg[ll << 1], self.lazy[ll << 1]), self.g(self.seg[(ll << 1)+1], self.lazy[(ll << 1)+1]))
      self.lazy[ll] = self.m_unit
    while rr > 1:
      rr >>= 1
      self.seg[rr] = self.f(self.g(self.seg[rr << 1], self.lazy[rr << 1]), self.g(self.seg[(rr << 1)+1], self.lazy[(rr << 1)+1]))
      self.lazy[rr] = self.m_unit

  def query(self, l, r):
    l += self.n
    r += self.n
    ll = l // (l & -l)
    rr = r // (r & -r) - 1
    for shift in range(ll.bit_length()-1, 0, -1):
      i = ll >> shift
      self.lazy[i << 1] = self.h(self.lazy[i << 1], self.lazy[i])
      self.lazy[(i << 1)+1] = self.h(self.lazy[(i << 1)+1], self.lazy[i])
      self.seg[i] = self.g(self.seg[i], self.lazy[i])
      self.lazy[i] = self.m_unit
    for shift in range(rr.bit_length()-1, 0, -1):
      i = rr >> shift
      self.lazy[i << 1] = self.h(self.lazy[i << 1],   self.lazy[i])
      self.lazy[(i << 1)+1] = self.h(self.lazy[(i << 1)+1], self.lazy[i])
      self.seg[i] = self.g(self.seg[i], self.lazy[i])
      self.lazy[i] = self.m_unit
    ans_l = ans_r = self.x_unit
    while l < r:
      if l & 1:
        ans_l = self.f(ans_l, self.g(self.seg[l], self.lazy[l]))
        l += 1
      if r & 1:
        r -= 1
        ans_r = self.f(self.g(self.seg[r], self.lazy[r]), ans_r)
      l >>= 1
      r >>= 1
    return self.f(ans_l, ans_r)

mod=998244353
mask=(1<<32)-1

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

def f(a,b):
  m=a+b
  return (((m>>32)%mod)<<32)+(m&mask)
def g(a,x):
  a1=a>>32
  a2=a&mask
  x1=x>>32
  x2=x&mask
  return (((a1*x1+a2*x2)%mod)<<32)+a2
def h(x,y):
  x1=x>>32
  x2=x&mask
  y1=y>>32
  y2=y&mask
  a=x1*y1%mod
  b=(x2*y1+y2)%mod
  return (a<<32)+b

seg=LazySegmentTree(n,a,0,(1<<32),f,g,h)

for _ in range(q):
  f,*query=map(int,input().split())
  if f==0:
    l,r,b,c=query
    seg.update(l,r,(b<<32)+c)
  else:
    l,r=query
    print(seg.query(l,r)>>32)

Submission status: Accepted

Solution code:
class LazySegmentTree():

    __slots__ = ["n","num","merge","merge_unit","operate","merge_operate","operate_unit","data","lazy","count"]

    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.num = 1<<self.n
        self.data=[merge_unit for i in range(1<<(self.n+1))]
        self.lazy=[operate_unit for i in range(1<<(self.n+1))]
        self.count = [1]*2*self.num
        if init:
            for i in range(n):
                self.data[2**self.n+i]=init[i]
                self.count[2**self.n+i]=1
            for i in range(2**self.n-1,0,-1):
                self.data[i]=self.merge(self.data[2*i],self.data[2*i+1])
                self.count[i]=self.count[2*i]+self.count[2*i+1]

    def update(self,l,r,x):
        l+=1<<self.n
        r+=1<<self.n
        l0=l//(l&-l)
        r0=r//(r&-r)-1

        i = l0
        m=i.bit_length()-1
        for bit in range(m,0,-1):
            v=i>>bit
            ope = self.lazy[v]
            if ope == self.operate_unit:
                continue
            self.lazy[v]=self.operate_unit
            self.data[2*v]=self.operate(self.count[2*v],self.data[2*v],ope)
            self.data[2*v+1]=self.operate(self.count[2*v+1],self.data[2*v+1],ope)
            self.lazy[2*v]=self.merge_operate(self.lazy[2*v],ope)
            self.lazy[2*v+1]=self.merge_operate(self.lazy[2*v+1],ope)

        i = r0
        m=i.bit_length()-1
        for bit in range(m,0,-1):
            v=i>>bit
            ope = self.lazy[v]
            if ope == self.operate_unit:
                continue
            self.lazy[v]=self.operate_unit
            self.data[2*v]=self.operate(self.count[2*v],self.data[2*v],ope)
            self.data[2*v+1]=self.operate(self.count[2*v+1],self.data[2*v+1],ope)
            self.lazy[2*v]=self.merge_operate(self.lazy[2*v],ope)
            self.lazy[2*v+1]=self.merge_operate(self.lazy[2*v+1],ope)

        while l<r:
            if l&1:
                self.data[l]=self.operate(self.count[l],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.count[r-1],self.data[r-1],x)
                self.lazy[r-1]=self.merge_operate(self.lazy[r-1],x)
            l>>=1
            r>>=1

        while l0:
            l0>>=1
            self.data[l0]=self.operate(self.count[l0],self.merge(self.data[2*l0],self.data[2*l0+1]),self.lazy[l0])

        while r0:
            r0>>=1
            self.data[r0]=self.operate(self.count[r0],self.merge(self.data[2*r0],self.data[2*r0+1]),self.lazy[r0])

    def query(self,l,r):
        l+=1<<self.n
        r+=1<<self.n
        l0=l//(l&-l)
        r0=r//(r&-r)-1
        i = l0
        m=i.bit_length()-1
        for bit in range(m,0,-1):
            v=i>>bit
            ope = self.lazy[v]
            if ope == self.operate_unit:
                continue
            self.lazy[v]=self.operate_unit
            self.data[2*v]=self.operate(self.count[2*v],self.data[2*v],ope)
            self.data[2*v+1]=self.operate(self.count[2*v+1],self.data[2*v+1],ope)
            self.lazy[2*v]=self.merge_operate(self.lazy[2*v],ope)
            self.lazy[2*v+1]=self.merge_operate(self.lazy[2*v+1],ope)

        i = r0
        m=i.bit_length()-1
        for bit in range(m,0,-1):
            v=i>>bit
            ope = self.lazy[v]
            if ope == self.operate_unit:
                continue
            self.lazy[v]=self.operate_unit
            self.data[2*v]=self.operate(self.count[2*v],self.data[2*v],ope)
            self.data[2*v+1]=self.operate(self.count[2*v+1],self.data[2*v+1],ope)
            self.lazy[2*v]=self.merge_operate(self.lazy[2*v],ope)
            self.lazy[2*v+1]=self.merge_operate(self.lazy[2*v+1],ope)
        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

import sys

input = sys.stdin.readline

mod = 998244353

merge = lambda x,y:(x+y) % mod
merge_unit = 0
operate = lambda L,x,y:(y[0]*x+y[1]*L) % mod
merge_operate = lambda x,y:(x[0]*y[0] % mod,(x[1]*y[0]+y[1])%mod)

operate_unit = (1,0)

N,Q = map(int,input().split())
a = list(map(int,input().split()))

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,c))
    else:
        gomi,l,r = query
        print(LST.query(l,r))

Submission status: Accepted

Solution code:
class LazySegmentTree():

    __solts__ = ["n","num","merge","merge_unit","operate","merge_operate","operate_unit","data","lazy","count"]

    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.num = 1<<self.n
        self.data=[merge_unit for i in range(1<<(self.n+1))]
        self.lazy=[operate_unit for i in range(1<<(self.n+1))]
        self.count = [1]*2*self.num
        if init:
            for i in range(n):
                self.data[2**self.n+i]=init[i]
                self.count[2**self.n+i]=1
            for i in range(2**self.n-1,0,-1):
                self.data[i]=self.merge(self.data[2*i],self.data[2*i+1])
                self.count[i]=self.count[2*i]+self.count[2*i+1]

    def update(self,l,r,x):
        l+=1<<self.n
        r+=1<<self.n
        l0=l//(l&-l)
        r0=r//(r&-r)-1

        i = l0
        m=i.bit_length()-1
        for bit in range(m,0,-1):
            v=i>>bit
            ope = self.lazy[v]
            if ope == self.operate_unit:
                continue
            self.lazy[v]=self.operate_unit
            self.data[2*v]=self.operate(self.count[2*v],self.data[2*v],ope)
            self.data[2*v+1]=self.operate(self.count[2*v+1],self.data[2*v+1],ope)
            self.lazy[2*v]=self.merge_operate(self.lazy[2*v],ope)
            self.lazy[2*v+1]=self.merge_operate(self.lazy[2*v+1],ope)

        i = r0
        m=i.bit_length()-1
        for bit in range(m,0,-1):
            v=i>>bit
            ope = self.lazy[v]
            if ope == self.operate_unit:
                continue
            self.lazy[v]=self.operate_unit
            self.data[2*v]=self.operate(self.count[2*v],self.data[2*v],ope)
            self.data[2*v+1]=self.operate(self.count[2*v+1],self.data[2*v+1],ope)
            self.lazy[2*v]=self.merge_operate(self.lazy[2*v],ope)
            self.lazy[2*v+1]=self.merge_operate(self.lazy[2*v+1],ope)

        while l<r:
            if l&1:
                self.data[l]=self.operate(self.count[l],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.count[r-1],self.data[r-1],x)
                self.lazy[r-1]=self.merge_operate(self.lazy[r-1],x)
            l>>=1
            r>>=1

        while l0:
            l0>>=1
            self.data[l0]=self.operate(self.count[l0],self.merge(self.data[2*l0],self.data[2*l0+1]),self.lazy[l0])

        while r0:
            r0>>=1
            self.data[r0]=self.operate(self.count[r0],self.merge(self.data[2*r0],self.data[2*r0+1]),self.lazy[r0])

    def query(self,l,r):
        l+=1<<self.n
        r+=1<<self.n
        l0=l//(l&-l)
        r0=r//(r&-r)-1
        i = l0
        m=i.bit_length()-1
        for bit in range(m,0,-1):
            v=i>>bit
            ope = self.lazy[v]
            if ope == self.operate_unit:
                continue
            self.lazy[v]=self.operate_unit
            self.data[2*v]=self.operate(self.count[2*v],self.data[2*v],ope)
            self.data[2*v+1]=self.operate(self.count[2*v+1],self.data[2*v+1],ope)
            self.lazy[2*v]=self.merge_operate(self.lazy[2*v],ope)
            self.lazy[2*v+1]=self.merge_operate(self.lazy[2*v+1],ope)

        i = r0
        m=i.bit_length()-1
        for bit in range(m,0,-1):
            v=i>>bit
            ope = self.lazy[v]
            if ope == self.operate_unit:
                continue
            self.lazy[v]=self.operate_unit
            self.data[2*v]=self.operate(self.count[2*v],self.data[2*v],ope)
            self.data[2*v+1]=self.operate(self.count[2*v+1],self.data[2*v+1],ope)
            self.lazy[2*v]=self.merge_operate(self.lazy[2*v],ope)
            self.lazy[2*v+1]=self.merge_operate(self.lazy[2*v+1],ope)
        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

import sys

input = sys.stdin.readline

mod = 998244353

merge = lambda x,y:(x+y) % mod
merge_unit = 0
operate = lambda L,x,y:(y[0]*x+y[1]*L) % mod
merge_operate = lambda x,y:(x[0]*y[0] % mod,(x[1]*y[0]+y[1])%mod)

operate_unit = (1,0)

N,Q = map(int,input().split())
a = list(map(int,input().split()))

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,c))
    else:
        gomi,l,r = query
        print(LST.query(l,r))