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:
import sys; input = sys.stdin.buffer.readline
sys.setrecursionlimit(10**7)
from collections import defaultdict
mod = 998244353; INF = float("inf")
sec = pow(2, mod - 2, mod)

def getlist():
	return list(map(int, input().split()))

class lazySegTree(object):
	# N:処理する区間の長さ
	def __init__(self, N):
		self.N = N
		self.LV = (N - 1).bit_length()
		self.N0 = 2 ** self.LV
		self.initVal = 0
		self.data = [0] * (2 * self.N0)
		self.lazybeta = [1] * (2 * self.N0)
		self.lazy = [0] * (2 * self.N0)

	def calc(self, a, b):
		return a + b

	def initialize(self, A):
		for i in range(self.N):
			self.data[self.N0 - 1 + i] = A[i]
		for i in range(self.N0 - 2, -1, -1):
			self.data[i] = self.calc(self.data[2 * i + 1], self.data[2 * i + 2])

	def gindex(self, l, r):
		L = (l + self.N0) >> 1; R = (r + self.N0) >> 1
		lc = 0 if l & 1 else (L & -L).bit_length()
		rc = 0 if r & 1 else (R & -R).bit_length()
		for i in range(self.LV):
			if rc <= i:
				yield R
			if L < R and lc <= i:
				yield L
			L >>= 1; R >>= 1

	def propagates(self, *ids):
		for i in reversed(ids):
			w = self.lazybeta[i - 1]
			v = self.lazy[i - 1]
			if w == 1 and (not v):
				continue
			val = (v * sec) % mod
			self.lazybeta[2 * i - 1] = (self.lazybeta[2 * i - 1] * w) % mod
			self.lazybeta[2 * i] = (self.lazybeta[2 * i] * w) % mod
			# self.lazy[2 * i - 1] = (self.lazy[2 * i - 1] * w + val) % mod
			# self.lazy[2 * i] = (self.lazy[2 * i] * w + val) % mod
			self.lazy[2 * i - 1] += val
			self.lazy[2 * i] += val
			self.data[2 * i - 1] = (self.data[2 * i - 1] * w + val) % mod
			self.data[2 * i] = (self.data[2 * i] * w + val) % mod
			self.lazybeta[i - 1] = 1; self.lazy[i - 1] = 0

	def update(self, l, r, b, c):
		# 1行にまとめてよい？
		*ids, = self.gindex(l, r + 1)
		self.propagates(*ids)

		L = self.N0 + l; R = self.N0 + r + 1
		v = c
		w = b
		while L < R:
			if R & 1:
				R -= 1
				self.lazybeta[R - 1] *= w; self.lazy[R - 1] += v
				self.data[R - 1] = (self.data[R - 1] * w + v) % mod
			if L & 1:
				self.lazybeta[L - 1] *= w; self.lazy[L - 1] += v
				self.data[L - 1] = (self.data[L - 1] * w + v) % mod
				L += 1
			L >>= 1; R >>= 1; v <<= 1
		for i in ids:
			self.data[i - 1] = self.calc(self.data[2 * i - 1], self.data[2 * i])

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

		s = self.initVal
		while L < R:
			if R & 1:
				R -= 1
				s = self.calc(s, self.data[R - 1])
			if L & 1:
				s = self.calc(s, self.data[L - 1])
				L += 1
			L >>= 1; R >>= 1
		return s

def main():
	N, Q = getlist()
	A = getlist()
	lSeg = lazySegTree(N)
	lSeg.initialize(A)

	for _ in range(Q):
		q = getlist()
		if q[0] == 0:
			null, l, r, b, c = q
			lSeg.update(l, r - 1, b, c)
		else:
			null, l, r = q
			res = lSeg.query(l, r - 1)
			print(res % mod)

if __name__ == '__main__':
	main()

Submission status: Wrong Answer

Solution code:
import sys; input = sys.stdin.buffer.readline
sys.setrecursionlimit(10**7)
from collections import defaultdict
mod = 998244353; INF = float("inf")
sec = pow(2, mod - 2, mod)

def getlist():
	return list(map(int, input().split()))

class lazySegTree(object):
	# N:処理する区間の長さ
	def __init__(self, N):
		self.N = N
		self.LV = (N - 1).bit_length()
		self.N0 = 2 ** self.LV
		self.initVal = 0
		self.data = [0] * (2 * self.N0)
		self.lazybeta = [1] * (2 * self.N0)
		self.lazy = [0] * (2 * self.N0)

	def calc(self, a, b):
		return a + b

	def initialize(self, A):
		for i in range(self.N):
			self.data[self.N0 - 1 + i] = A[i]
		for i in range(self.N0 - 2, -1, -1):
			self.data[i] = self.calc(self.data[2 * i + 1], self.data[2 * i + 2])

	def gindex(self, l, r):
		L = (l + self.N0) >> 1; R = (r + self.N0) >> 1
		lc = 0 if l & 1 else (L & -L).bit_length()
		rc = 0 if r & 1 else (R & -R).bit_length()
		for i in range(self.LV):
			if rc <= i:
				yield R
			if L < R and lc <= i:
				yield L
			L >>= 1; R >>= 1

	def propagates(self, *ids):
		for i in reversed(ids):
			w = self.lazybeta[i - 1]
			v = self.lazy[i - 1]
			if w == 1 and (not v):
				continue
			val = (v * sec) % mod
			self.lazybeta[2 * i - 1] = (self.lazybeta[2 * i - 1] * w) % mod
			self.lazybeta[2 * i] = (self.lazybeta[2 * i] * w) % mod
			self.lazy[2 * i - 1] = (self.lazy[2 * i - 1] * w + val) % mod
			self.lazy[2 * i] = (self.lazy[2 * i] * w + val) % mod
			self.lazy[2 * i - 1] += val
			self.lazy[2 * i] += val
			# self.data[2 * i - 1] += val
			# self.data[2 * i] += val
			self.data[2 * i - 1] = (self.data[2 * i - 1] * w + val) % mod
			self.data[2 * i] = (self.data[2 * i] * w + val) % mod
			self.lazybeta[i - 1] = 1; self.lazy[i - 1] = 0

	def update(self, l, r, b, c):
		# 1行にまとめてよい？
		*ids, = self.gindex(l, r + 1)
		self.propagates(*ids)

		L = self.N0 + l; R = self.N0 + r + 1
		v = c
		w = b
		while L < R:
			if R & 1:
				R -= 1
				self.lazybeta[R - 1] *= w; self.lazy[R - 1] += v
				self.data[R - 1] = (self.data[R - 1] * w + v) % mod
			if L & 1:
				self.lazybeta[L - 1] *= w; self.lazy[L - 1] += v
				self.data[L - 1] = (self.data[L - 1] * w + v) % mod
				L += 1
			L >>= 1; R >>= 1; v <<= 1
		for i in ids:
			self.data[i - 1] = self.calc(self.data[2 * i - 1], self.data[2 * i])

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

		s = self.initVal
		while L < R:
			if R & 1:
				R -= 1
				s = self.calc(s, self.data[R - 1])
			if L & 1:
				s = self.calc(s, self.data[L - 1])
				L += 1
			L >>= 1; R >>= 1
		return s

def main():
	N, Q = getlist()
	A = getlist()
	lSeg = lazySegTree(N)
	lSeg.initialize(A)

	for _ in range(Q):
		q = getlist()
		if q[0] == 0:
			null, l, r, b, c = q
			lSeg.update(l, r - 1, b, c)
		else:
			null, l, r = q
			res = lSeg.query(l, r - 1)
			print(res % mod)

if __name__ == '__main__':
	main()

Submission status: Wrong Answer

Solution code:
import sys; input = sys.stdin.buffer.readline
sys.setrecursionlimit(10**7)
from collections import defaultdict
mod = 998244353; INF = float("inf")

sec = pow(2, mod - 2, mod)

def getlist():
	return list(map(int, input().split()))

class lazySegTree(object):
	# N:処理する区間の長さ
	def __init__(self, N):
		self.N = N
		self.LV = (N - 1).bit_length()
		self.N0 = 2 ** self.LV
		self.initVal = 0
		self.data = [0] * (2 * self.N0)
		self.lazybeta = [1] * (2 * self.N0)
		self.lazy = [0] * (2 * self.N0)

	def calc(self, a, b):
		return a + b

	def initialize(self, A):
		for i in range(self.N):
			self.data[self.N0 - 1 + i] = A[i]
		for i in range(self.N0 - 2, -1, -1):
			self.data[i] = self.calc(self.data[2 * i + 1], self.data[2 * i + 2])

	def gindex(self, l, r):
		L = (l + self.N0) >> 1; R = (r + self.N0) >> 1
		lc = 0 if l & 1 else (L & -L).bit_length()
		rc = 0 if r & 1 else (R & -R).bit_length()
		for i in range(self.LV):
			if rc <= i:
				yield R
			if L < R and lc <= i:
				yield L
			L >>= 1; R >>= 1

	def propagates(self, *ids):
		for i in reversed(ids):
			w = self.lazybeta[i - 1]
			v = self.lazy[i - 1]
			if w == 1 and (not v):
				continue
			val = (v * sec) % mod
			self.lazybeta[2 * i - 1] = (self.lazybeta[2 * i - 1] * w) % mod
			self.lazybeta[2 * i] = (self.lazybeta[2 * i] * w) % mod
			self.lazy[2 * i - 1] = (self.lazy[2 * i - 1] * w + val) % mod
			self.lazy[2 * i] = (self.lazy[2 * i] * w + val) % mod
			self.data[2 * i - 1] = (self.data[2 * i - 1] * w + val) % mod
			self.data[2 * i] = (self.data[2 * i] * w + val) % mod
			self.lazybeta[i - 1] = 1; self.lazy[i - 1] = 0

	def update(self, l, r, b, c):
		# 1行にまとめてよい？
		*ids, = self.gindex(l, r + 1)
		self.propagates(*ids)

		L = self.N0 + l; R = self.N0 + r + 1
		v = c
		w = b
		while L < R:
			if R & 1:
				R -= 1
				self.lazybeta[R - 1] *= w; self.lazy[R - 1] += v
				self.data[R - 1] = (self.data[R - 1] * w + v) % mod
			if L & 1:
				self.lazybeta[L - 1] *= w; self.lazy[L - 1] += v
				self.data[L - 1] = (self.data[L - 1] * w + v) % mod
				L += 1
			L >>= 1; R >>= 1; v <<= 1
		for i in ids:
			self.data[i - 1] = self.calc(self.data[2 * i - 1], self.data[2 * i])

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

		s = self.initVal
		while L < R:
			if R & 1:
				R -= 1
				s = self.calc(s, self.data[R - 1])
			if L & 1:
				s = self.calc(s, self.data[L - 1])
				L += 1
			L >>= 1; R >>= 1
		return s

def main():
	N, Q = getlist()
	A = getlist()
	lSeg = lazySegTree(N)
	lSeg.initialize(A)

	for _ in range(Q):
		q = getlist()
		if q[0] == 0:
			null, l, r, b, c = q
			lSeg.update(l, r - 1, b, c)
		else:
			null, l, r = q
			res = lSeg.query(l, r - 1)
			print(res % mod)

if __name__ == '__main__':
	main()

Submission status: Wrong Answer

Solution code:
import sys; input = sys.stdin.buffer.readline
sys.setrecursionlimit(10**7)
from collections import defaultdict
mod = 998244353; INF = float("inf")

sec = pow(2, mod - 2, mod)

def getlist():
	return list(map(int, input().split()))

class lazySegTree(object):
	# N:処理する区間の長さ
	def __init__(self, N):
		self.N = N
		self.LV = (N - 1).bit_length()
		self.N0 = 2 ** self.LV
		self.initVal = 0
		self.data = [0] * (2 * self.N0)
		self.lazybeta = [1] * (2 * self.N0)
		self.lazy = [0] * (2 * self.N0)

	def calc(self, a, b):
		return a + b

	def initialize(self, A):
		for i in range(self.N):
			self.data[self.N0 - 1 + i] = A[i]
		for i in range(self.N0 - 2, -1, -1):
			self.data[i] = self.calc(self.data[2 * i + 1], self.data[2 * i + 2])

	def gindex(self, l, r):
		L = (l + self.N0) >> 1; R = (r + self.N0) >> 1
		lc = 0 if l & 1 else (L & -L).bit_length()
		rc = 0 if r & 1 else (R & -R).bit_length()
		for i in range(self.LV):
			if rc <= i:
				yield R
			if L < R and lc <= i:
				yield L
			L >>= 1; R >>= 1

	def propagates(self, *ids):
		for i in reversed(ids):
			w = self.lazybeta[i - 1]
			v = self.lazy[i - 1]
			if w == 1 and (not v):
				continue
			val = (v * sec) % mod
			self.lazybeta[2 * i - 1] = (self.lazybeta[2 * i - 1] * w) % mod
			self.lazybeta[2 * i] = (self.lazybeta[2 * i] * w) % mod
			self.lazy[2 * i - 1] = (self.lazy[2 * i - 1] * w + val) % mod
			self.lazy[2 * i] = (self.lazy[2 * i] * w + val) % mod
			self.data[2 * i - 1] = (self.data[2 * i - 1] * w + val) % mod
			self.data[2 * i] = (self.data[2 * i] * w + val) % mod
			self.lazy[2 * i - 1] += val; self.lazy[2 * i] += val
			self.lazybeta[i - 1] = 1; self.lazy[i - 1] = 0

	def update(self, l, r, b, c):
		# 1行にまとめてよい？
		*ids, = self.gindex(l, r + 1)
		self.propagates(*ids)

		L = self.N0 + l; R = self.N0 + r + 1
		v = c
		w = b
		while L < R:
			if R & 1:
				R -= 1
				self.lazybeta[R - 1] *= w; self.lazy[R - 1] += v
				self.data[R - 1] = (self.data[R - 1] * w + v) % mod
			if L & 1:
				self.lazybeta[L - 1] *= w; self.lazy[L - 1] += v
				self.data[L - 1] = (self.data[L - 1] * w + v) % mod
				L += 1
			L >>= 1; R >>= 1; v <<= 1
		for i in ids:
			self.data[i - 1] = self.calc(self.data[2 * i - 1], self.data[2 * i])

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

		s = self.initVal
		while L < R:
			if R & 1:
				R -= 1
				s = self.calc(s, self.data[R - 1])
			if L & 1:
				s = self.calc(s, self.data[L - 1])
				L += 1
			L >>= 1; R >>= 1
		return s

def main():
	N, Q = getlist()
	A = getlist()
	lSeg = lazySegTree(N)
	lSeg.initialize(A)

	for _ in range(Q):
		q = getlist()
		if q[0] == 0:
			null, l, r, b, c = q
			lSeg.update(l, r - 1, b, c)
		else:
			null, l, r = q
			res = lSeg.query(l, r - 1)
			print(res % mod)

if __name__ == '__main__':
	main()

Submission status: Wrong Answer

Solution code:
import sys; input = sys.stdin.buffer.readline
sys.setrecursionlimit(10**7)
from collections import defaultdict
mod = 998244353; INF = float("inf")

sec = pow(2, mod - 2, mod)

def getlist():
	return list(map(int, input().split()))

class lazySegTree(object):
	# N:処理する区間の長さ
	def __init__(self, N):
		self.N = N
		self.LV = (N - 1).bit_length()
		self.N0 = 2 ** self.LV
		self.initVal = 0
		self.data = [0] * (2 * self.N0)
		self.lazybeta = [1] * (2 * self.N0)
		self.lazy = [0] * (2 * self.N0)

	def calc(self, a, b):
		return a + b

	def initialize(self, A):
		for i in range(self.N):
			self.data[self.N0 - 1 + i] = A[i]
		for i in range(self.N0 - 2, -1, -1):
			self.data[i] = self.calc(self.data[2 * i + 1], self.data[2 * i + 2])

	def gindex(self, l, r):
		L = (l + self.N0) >> 1; R = (r + self.N0) >> 1
		lc = 0 if l & 1 else (L & -L).bit_length()
		rc = 0 if r & 1 else (R & -R).bit_length()
		for i in range(self.LV):
			if rc <= i:
				yield R
			if L < R and lc <= i:
				yield L
			L >>= 1; R >>= 1

	def propagates(self, *ids):
		for i in reversed(ids):
			w = self.lazybeta[i - 1]
			v = self.lazy[i - 1]
			if w == 1 or (not v):
				continue
			val = (v * sec) % mod
			self.lazybeta[2 * i - 1] = (self.lazybeta[2 * i - 1] * w) % mod
			self.lazybeta[2 * i] = (self.lazybeta[2 * i] * w) % mod
			self.lazy[2 * i - 1] = (self.lazy[2 * i - 1] * w + val) % mod
			self.lazy[2 * i] = (self.lazy[2 * i] * w + val) % mod
			self.data[2 * i - 1] = (self.data[2 * i - 1] * w + val) % mod
			self.data[2 * i] = (self.data[2 * i] * w + val) % mod
			self.lazy[2 * i - 1] += val; self.lazy[2 * i] += val
			self.lazybeta[i - 1] = 0; self.lazy[i - 1] = 0

	def update(self, l, r, b, c):
		# 1行にまとめてよい？
		*ids, = self.gindex(l, r + 1)
		self.propagates(*ids)

		L = self.N0 + l; R = self.N0 + r + 1
		v = c
		w = b
		while L < R:
			if R & 1:
				R -= 1
				self.lazybeta[R - 1] *= w; self.data[R - 1] = (self.data[R - 1] * w) % mod
				self.lazy[R - 1] += v; self.data[R - 1] += v
			if L & 1:
				self.lazybeta[L - 1] *= w; self.data[L - 1] = (self.data[L - 1] * w) % mod
				self.lazy[L - 1] += v; self.data[L - 1] += v
				L += 1
			L >>= 1; R >>= 1; v <<= 1
		for i in ids:
			self.data[i - 1] = self.calc(self.data[2 * i - 1], self.data[2 * i])

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

		s = self.initVal
		while L < R:
			if R & 1:
				R -= 1
				s = self.calc(s, self.data[R - 1])
			if L & 1:
				s = self.calc(s, self.data[L - 1])
				L += 1
			L >>= 1; R >>= 1
		return s

def main():
	N, Q = getlist()
	A = getlist()
	lSeg = lazySegTree(N)
	lSeg.initialize(A)

	for _ in range(Q):
		q = getlist()
		if q[0] == 0:
			null, l, r, b, c = q
			lSeg.update(l, r - 1, b, c)
		else:
			null, l, r = q
			res = lSeg.query(l, r - 1)
			print(res % mod)

if __name__ == '__main__':
	main()

Submission status: Wrong Answer

Solution code:
import sys; input = sys.stdin.buffer.readline
sys.setrecursionlimit(10**7)
from collections import defaultdict
mod = 998244353; INF = float("inf")

sec = pow(2, mod - 2, mod)

def getlist():
	return list(map(int, input().split()))

class lazySegTree(object):
	# N:処理する区間の長さ
	def __init__(self, N):
		self.N = N
		self.LV = (N - 1).bit_length()
		self.N0 = 2 ** self.LV
		self.initVal = 0
		self.data = [0] * (2 * self.N0)
		self.lazybeta = [0] * (2 * self.N0)
		self.lazy = [0] * (2 * self.N0)

	def calc(self, a, b):
		return a + b

	def initialize(self, A):
		for i in range(self.N):
			self.data[self.N0 - 1 + i] = A[i]
		for i in range(self.N0 - 2, -1, -1):
			self.data[i] = self.calc(self.data[2 * i + 1], self.data[2 * i + 2])

	def gindex(self, l, r):
		L = (l + self.N0) >> 1; R = (r + self.N0) >> 1
		lc = 0 if l & 1 else (L & -L).bit_length()
		rc = 0 if r & 1 else (R & -R).bit_length()
		for i in range(self.LV):
			if rc <= i:
				yield R
			if L < R and lc <= i:
				yield L
			L >>= 1; R >>= 1

	def propagates(self, *ids):
		for i in reversed(ids):
			w = self.lazybeta[i - 1]
			v = self.lazy[i - 1]
			if not w:
				continue
			val = (v * sec) % mod
			self.lazybeta[2 * i - 1] = (self.lazybeta[2 * i - 1] * w) % mod
			self.lazybeta[2 * i] = (self.lazybeta[2 * i] * w) % mod
			self.lazy[2 * i - 1] = (self.lazy[2 * i - 1] * w + val) % mod
			self.lazy[2 * i] = (self.lazy[2 * i] * w + val) % mod
			self.data[2 * i - 1] = (self.data[2 * i - 1] * w + val) % mod
			self.data[2 * i] = (self.data[2 * i] * w + val) % mod
			self.lazy[2 * i - 1] += val; self.lazy[2 * i] += val
			self.lazybeta[i - 1] = 0; self.lazy[i - 1] = 0

	def update(self, l, r, b, c):
		# 1行にまとめてよい？
		*ids, = self.gindex(l, r + 1)
		self.propagates(*ids)

		L = self.N0 + l; R = self.N0 + r + 1
		v = c
		w = b
		while L < R:
			if R & 1:
				R -= 1
				self.lazybeta[R - 1] += w; self.data[R - 1] = (self.data[R - 1] * w) % mod
				self.lazy[R - 1] += v; self.data[R - 1] += v
			if L & 1:
				self.lazybeta[L - 1] += w; self.data[L - 1] = (self.data[L - 1] * w) % mod
				self.lazy[L - 1] += v; self.data[L - 1] += v
				L += 1
			L >>= 1; R >>= 1; v <<= 1
		for i in ids:
			self.data[i - 1] = self.calc(self.data[2 * i - 1], self.data[2 * i])

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

		s = self.initVal
		while L < R:
			if R & 1:
				R -= 1
				s = self.calc(s, self.data[R - 1])
			if L & 1:
				s = self.calc(s, self.data[L - 1])
				L += 1
			L >>= 1; R >>= 1
		return s

def main():
	N, Q = getlist()
	A = getlist()
	lSeg = lazySegTree(N)
	lSeg.initialize(A)

	for _ in range(Q):
		q = getlist()
		if q[0] == 0:
			null, l, r, b, c = q
			lSeg.update(l, r - 1, b, c)
		else:
			null, l, r = q
			res = lSeg.query(l, r - 1)
			print(res % mod)

if __name__ == '__main__':
	main()

Submission status: Wrong Answer

Solution code:
import sys; input = sys.stdin.buffer.readline
sys.setrecursionlimit(10**7)
from collections import defaultdict
mod = 998244353; INF = float("inf")

sec = pow(2, mod - 2, mod)

def getlist():
	return list(map(int, input().split()))

class lazySegTree(object):
	# N:処理する区間の長さ
	def __init__(self, N):
		self.N = N
		self.LV = (N - 1).bit_length()
		self.N0 = 2 ** self.LV
		self.initVal = 0
		self.data = [0] * (2 * self.N0)
		self.lazybeta = [0] * (2 * self.N0)
		self.lazy = [0] * (2 * self.N0)

	def calc(self, a, b):
		return a + b

	def initialize(self, A):
		for i in range(self.N):
			self.data[self.N0 - 1 + i] = A[i]
		for i in range(self.N0 - 2, -1, -1):
			self.data[i] = self.calc(self.data[2 * i + 1], self.data[2 * i + 2])

	def gindex(self, l, r):
		L = (l + self.N0) >> 1; R = (r + self.N0) >> 1
		lc = 0 if l & 1 else (L & -L).bit_length()
		rc = 0 if r & 1 else (R & -R).bit_length()
		for i in range(self.LV):
			if rc <= i:
				yield R
			if L < R and lc <= i:
				yield L
			L >>= 1; R >>= 1

	def propagates(self, *ids):
		for i in reversed(ids):
			w = self.lazybeta[i - 1]
			v = self.lazy[i - 1]
			if not w:
				continue
			val = (v * sec) % mod
			self.lazybeta[2 * i - 1] += w; self.lazybeta[2 * i] += w
			self.lazy[2 * i - 1] = (self.lazy[2 * i - 1] * w + val) % mod
			self.lazy[2 * i] = (self.lazy[2 * i] * w + val) % mod
			self.data[2 * i - 1] = (self.data[2 * i - 1] * w + val) % mod
			self.data[2 * i] = (self.data[2 * i] * w + val) % mod
			self.lazy[2 * i - 1] += val; self.lazy[2 * i] += val
			self.lazybeta[i - 1] = 0; self.lazy[i - 1] = 0

	def update(self, l, r, b, c):
		# 1行にまとめてよい？
		*ids, = self.gindex(l, r + 1)
		self.propagates(*ids)

		L = self.N0 + l; R = self.N0 + r + 1
		v = c
		w = b
		while L < R:
			if R & 1:
				R -= 1
				self.lazybeta[R - 1] += w; self.data[R - 1] = (self.data[R - 1] * w) % mod
				self.lazy[R - 1] += v; self.data[R - 1] += v
			if L & 1:
				self.lazybeta[L - 1] += w; self.data[L - 1] = (self.data[L - 1] * w) % mod
				self.lazy[L - 1] += v; self.data[L - 1] += v
				L += 1
			L >>= 1; R >>= 1; v <<= 1
		for i in ids:
			self.data[i - 1] = self.calc(self.data[2 * i - 1], self.data[2 * i])

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

		s = self.initVal
		while L < R:
			if R & 1:
				R -= 1
				s = self.calc(s, self.data[R - 1])
			if L & 1:
				s = self.calc(s, self.data[L - 1])
				L += 1
			# s %= mod
			L >>= 1; R >>= 1
		return s

def main():
	N, Q = getlist()
	A = getlist()
	lSeg = lazySegTree(N)
	lSeg.initialize(A)

	for _ in range(Q):
		q = getlist()
		if q[0] == 0:
			null, l, r, b, c = q
			lSeg.update(l, r - 1, b, c)
		else:
			null, l, r = q
			res = lSeg.query(l, r - 1)
			print(res % mod)

if __name__ == '__main__':
	main()

Submission status: Wrong Answer

Solution code:
import sys; input = sys.stdin.buffer.readline
sys.setrecursionlimit(10**7)
from collections import defaultdict
mod = 998244353; INF = float("inf")

def getlist():
	return list(map(int, input().split()))

class lazySegTree(object):
	# N:処理する区間の長さ
	def __init__(self, N):
		self.N = N
		self.LV = (N - 1).bit_length()
		self.N0 = 2 ** self.LV
		self.initVal = 0
		self.data = [0] * (2 * self.N0)
		self.lazybeta = [0] * (2 * self.N0)
		self.lazy = [0] * (2 * self.N0)

	def calc(self, a, b):
		return a + b

	def initialize(self, A):
		for i in range(self.N):
			self.data[self.N0 - 1 + i] = A[i]
		for i in range(self.N0 - 2, -1, -1):
			self.data[i] = self.calc(self.data[2 * i + 1], self.data[2 * i + 2])

	def gindex(self, l, r):
		L = (l + self.N0) >> 1; R = (r + self.N0) >> 1
		lc = 0 if l & 1 else (L & -L).bit_length()
		rc = 0 if r & 1 else (R & -R).bit_length()
		for i in range(self.LV):
			if rc <= i:
				yield R
			if L < R and lc <= i:
				yield L
			L >>= 1; R >>= 1

	def propagates(self, *ids):
		for i in reversed(ids):
			w = self.lazybeta[i - 1]
			v = self.lazy[i - 1]
			if not w:
				continue
			val = v >> 1
			self.lazybeta[2 * i - 1] += w; self.lazybeta[2 * i] += w
			self.lazy[2 * i - 1] = (self.lazy[2 * i - 1] * w + val) % mod
			self.lazy[2 * i] = (self.lazy[2 * i] * w + val) % mod
			self.data[2 * i - 1] = (self.data[2 * i - 1] * w + val) % mod
			self.data[2 * i] = (self.data[2 * i] * w + val) % mod
			self.lazy[2 * i - 1] += val; self.lazy[2 * i] += val
			self.lazybeta[i - 1] = 0; self.lazy[i - 1] = 0

	def update(self, l, r, b, c):
		# 1行にまとめてよい？
		*ids, = self.gindex(l, r + 1)
		self.propagates(*ids)

		L = self.N0 + l; R = self.N0 + r + 1
		v = c
		w = b
		while L < R:
			if R & 1:
				R -= 1
				self.lazybeta[R - 1] += w; self.data[R - 1] = (self.data[R - 1] * w) % mod
				self.lazy[R - 1] += v; self.data[R - 1] += v
			if L & 1:
				self.lazybeta[L - 1] += w; self.data[L - 1] = (self.data[L - 1] * w) % mod
				self.lazy[L - 1] += v; self.data[L - 1] += v
				L += 1
			L >>= 1; R >>= 1; v <<= 1
		for i in ids:
			self.data[i - 1] = self.calc(self.data[2 * i - 1], self.data[2 * i])

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

		s = self.initVal
		while L < R:
			if R & 1:
				R -= 1
				s = self.calc(s, self.data[R - 1])
			if L & 1:
				s = self.calc(s, self.data[L - 1])
				L += 1
			# s %= mod
			L >>= 1; R >>= 1
		return s

def main():
	N, Q = getlist()
	A = getlist()
	lSeg = lazySegTree(N)
	lSeg.initialize(A)

	for _ in range(Q):
		q = getlist()
		if q[0] == 0:
			null, l, r, b, c = q
			lSeg.update(l, r - 1, b, c)
		else:
			null, l, r = q
			res = lSeg.query(l, r - 1)
			print(res % mod)

if __name__ == '__main__':
	main()

Submission status: Wrong Answer

Solution code:
import sys; input = sys.stdin.buffer.readline
sys.setrecursionlimit(10**7)
from collections import defaultdict
mod = 998244353; INF = float("inf")

def getlist():
	return list(map(int, input().split()))

class lazySegTree(object):
	# N:処理する区間の長さ
	def __init__(self, N):
		self.N = N
		self.LV = (N - 1).bit_length()
		self.N0 = 2 ** self.LV
		self.initVal = 0
		self.data = [0] * (2 * self.N0)
		self.lazybeta = [0] * (2 * self.N0)
		self.lazy = [0] * (2 * self.N0)

	def calc(self, a, b):
		return a + b

	def initialize(self, A):
		for i in range(self.N):
			self.data[self.N0 - 1 + i] = A[i]
		for i in range(self.N0 - 2, -1, -1):
			self.data[i] = self.calc(self.data[2 * i + 1], self.data[2 * i + 2])

	def gindex(self, l, r):
		L = (l + self.N0) >> 1; R = (r + self.N0) >> 1
		lc = 0 if l & 1 else (L & -L).bit_length()
		rc = 0 if r & 1 else (R & -R).bit_length()
		for i in range(self.LV):
			if rc <= i:
				yield R
			if L < R and lc <= i:
				yield L
			L >>= 1; R >>= 1

	def propagates(self, *ids):
		for i in reversed(ids):
			w = self.lazybeta[i - 1]
			v = self.lazy[i - 1]
			# if not w:
			# 	continue
			val = v >> 1
			self.lazybeta[2 * i - 1] += w; self.lazybeta[2 * i] += w
			self.data[2 * i - 1] = (self.data[2 * i - 1] * w) % mod
			self.data[2 * i] = (self.data[2 * i] * w) % mod
			self.lazy[2 * i - 1] += val; self.lazy[2 * i] += val
			self.data[2 * i - 1] += val; self.data[2 * i] += val
			self.lazybeta[i - 1] = 0; self.lazy[i - 1] = 0

	def update(self, l, r, b, c):
		# 1行にまとめてよい？
		*ids, = self.gindex(l, r + 1)
		self.propagates(*ids)

		L = self.N0 + l; R = self.N0 + r + 1
		v = c
		w = b
		while L < R:
			if R & 1:
				R -= 1
				self.lazybeta[R - 1] += w; self.data[R - 1] = (self.data[R - 1] * w) % mod
				self.lazy[R - 1] += v; self.data[R - 1] += v
			if L & 1:
				self.lazybeta[L - 1] += w; self.data[L - 1] = (self.data[L - 1] * w) % mod
				self.lazy[L - 1] += v; self.data[L - 1] += v
				L += 1
			L >>= 1; R >>= 1; v <<= 1
		for i in ids:
			self.data[i - 1] = self.calc(self.data[2 * i - 1], self.data[2 * i])

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

		s = self.initVal
		while L < R:
			if R & 1:
				R -= 1
				s = self.calc(s, self.data[R - 1])
			if L & 1:
				s = self.calc(s, self.data[L - 1])
				L += 1
			L >>= 1; R >>= 1
		return s

def main():
	N, Q = getlist()
	A = getlist()
	lSeg = lazySegTree(N)
	lSeg.initialize(A)

	for _ in range(Q):
		q = getlist()
		if q[0] == 0:
			null, l, r, b, c = q
			lSeg.update(l, r - 1, b, c)
		else:
			null, l, r = q
			res = lSeg.query(l, r - 1)
			print(res % mod)

if __name__ == '__main__':
	main()

Submission status: Wrong Answer

Solution code:
import sys; input = sys.stdin.buffer.readline
sys.setrecursionlimit(10**7)
from collections import defaultdict
mod = 998244353; INF = float("inf")

def getlist():
	return list(map(int, input().split()))

class lazySegTree(object):
	# N:処理する区間の長さ
	def __init__(self, N):
		self.N = N
		self.LV = (N - 1).bit_length()
		self.N0 = 2 ** self.LV
		self.initVal = 0
		self.data = [0] * (2 * self.N0)
		self.lazybeta = [0] * (2 * self.N0)
		self.lazy = [0] * (2 * self.N0)

	def calc(self, a, b):
		return a + b

	def initialize(self, A):
		for i in range(self.N):
			self.data[self.N0 - 1 + i] = A[i]
		for i in range(self.N0 - 2, -1, -1):
			self.data[i] = self.calc(self.data[2 * i + 1], self.data[2 * i + 2])

	def gindex(self, l, r):
		L = (l + self.N0) >> 1; R = (r + self.N0) >> 1
		lc = 0 if l & 1 else (L & -L).bit_length()
		rc = 0 if r & 1 else (R & -R).bit_length()
		for i in range(self.LV):
			if rc <= i:
				yield R
			if L < R and lc <= i:
				yield L
			L >>= 1; R >>= 1

	def propagates(self, *ids):
		for i in reversed(ids):
			w = self.lazybeta[i - 1]
			v = self.lazy[i - 1]
			if not w:
				continue
			val = v >> 1
			self.lazybeta[2 * i - 1] += w; self.lazybeta[2 * i] += w
			self.data[2 * i - 1] = (self.data[2 * i - 1] * w) % mod
			self.data[2 * i] = (self.data[2 * i] * w) % mod
			self.lazy[2 * i - 1] += val; self.lazy[2 * i] += val
			self.data[2 * i - 1] += val; self.data[2 * i] += val
			self.lazybeta[i - 1] = 0
			self.lazy[i - 1] = 0

	def update(self, l, r, b, c):
		# 1行にまとめてよい？
		*ids, = self.gindex(l, r + 1)
		self.propagates(*ids)

		L = self.N0 + l; R = self.N0 + r + 1
		v = c
		w = b
		while L < R:
			if R & 1:
				R -= 1
				self.lazybeta[R - 1] += w; self.data[R - 1] = (self.data[R - 1] * w) % mod
				self.lazy[R - 1] += v; self.data[R - 1] += v
			if L & 1:
				self.lazybeta[L - 1] += w; self.data[L - 1] = (self.data[L - 1] * w) % mod
				self.lazy[L - 1] += v; self.data[L - 1] += v
				L += 1
			L >>= 1; R >>= 1; v <<= 1
		for i in ids:
			self.data[i - 1] = self.calc(self.data[2 * i - 1], self.data[2 * i])

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

		s = self.initVal
		while L < R:
			if R & 1:
				R -= 1
				s = self.calc(s, self.data[R - 1])
			if L & 1:
				s = self.calc(s, self.data[L - 1])
				L += 1
			L >>= 1; R >>= 1
		return s

def main():
	N, Q = getlist()
	A = getlist()
	lSeg = lazySegTree(N)
	lSeg.initialize(A)

	for _ in range(Q):
		q = getlist()
		if q[0] == 0:
			null, l, r, b, c = q
			lSeg.update(l, r - 1, b, c)
		else:
			null, l, r = q
			res = lSeg.query(l, r - 1)
			print(res % mod)

if __name__ == '__main__':
	main()