Language: C++

#include <iostream>
#include <vector>
#include <functional>

long long modinv(long long n, long long MOD) {
	long long a = MOD, u = 1, v = 0;
	while (a) {
		long long t = n / a;
		n -= t * a; std::swap(n, a);
		u -= t * v; std::swap(u, v);
	}
	u %= MOD;
	if (u < 0) u += MOD;
	return u;
}

template<long long MOD> struct modint {
	long long value = 0;
	void f() {
		value %= MOD;
		if (value < 0) value += MOD;
	}
	modint(long long n) : value(n) {f();}
	modint() : value(0) {}
	modint<MOD> operator+(modint<MOD> right) {modint<MOD> ret = (this -> value) + right.value; return ret;}
	modint<MOD> operator-(modint<MOD> right) {modint<MOD> ret = (this -> value) - right.value; return ret;}
	modint<MOD> operator*(modint<MOD> right) {modint<MOD> ret = (this -> value) * right.value; return ret;}
	modint<MOD> operator/(modint<MOD> right) {modint<MOD> ret = (this -> value) * modinv(right.value, MOD); return ret;}
	modint<MOD> operator+=(modint<MOD> right) {return *this = *this + right;}
	modint<MOD> operator-=(modint<MOD> right) {return *this = *this - right;}
	modint<MOD> operator*=(modint<MOD> right) {return *this = *this * right;}
	modint<MOD> operator/=(modint<MOD> right) {return *this = *this / right;}
	bool operator<(modint<MOD> right) {return ((this -> value) < right.value);}
	bool operator>(modint<MOD> right) {return ((this -> value) > right.value);}
	bool operator==(modint<MOD> right) {return ((this -> value) == right.value);}
	bool operator!=(modint<MOD> right) {return ((this -> value) != right.value);}
	bool operator<=(modint<MOD> right) {return ((this -> value) <= right.value);}
	bool operator>=(modint<MOD> right) {return ((this -> value) >= right.value);}
	modint<MOD>& operator++() {*this += 1; return *this;}
	modint<MOD> operator++(int) {*this += 1; return *this - 1;}
	modint<MOD>& operator--() {*this -= 1; return *this;}
	modint<MOD> operator--(int) {*this -= 1; return *this + 1;}
};
template<long long MOD> modint<MOD> operator+(long long left, modint<MOD> right) {return right + left;}
template<long long MOD> modint<MOD> operator-(long long left, modint<MOD> right) {return right * -1 + left;}
template<long long MOD> modint<MOD> operator*(long long left, modint<MOD> right) {return right * left;}
template<long long MOD> modint<MOD> operator/(long long left, modint<MOD> right) {
	return modinv(right.value, MOD) * (left % MOD);
}
//template<long long MOD> bool operator==(modint<MOD> left, modint<MOD> right) {return (left.value == right.value);}

template<long long MOD> modint<MOD> modpow(modint<MOD> a, long long n) {
	if (n == 0) return 1;
	if (a == 0) return 0;
	modint<MOD> ret = a;
	long long cnt = 1;
	while (cnt * 2 <= n) {
		ret *= ret;
		cnt *= 2;
	}
	return ret * modpow<MOD>(a, n - cnt);
}

long long modpow(long long a, long long n, long long MOD) {
	if (n == 0) return 1;
	if (a == 0) return 0;
	long long ret = a % MOD, cnt = 1;
	while (cnt * 2 <= n) {
		ret *= ret; ret %= MOD;
		cnt *= 2;
	}
	return ret * modpow(a, n - cnt, MOD) % MOD;
}

std::vector<long long> factorial;
std::vector<long long> factorial_inv;

template<long long P> void make_table(int n) {
	factorial.resize(n + 1, 1);
	factorial_inv.resize(n + 1, 1);
	for (int i = 1; i <= n; i++) factorial[i] = factorial[i - 1] * i % P;
	factorial_inv[n] = modinv(factorial[n], P);
	for (int i = n - 1; i >= 0; i--) factorial_inv[i] = factorial_inv[i + 1] * (i + 1) % P;
}

template<long long P> modint<P> permutation(int n, int r) {
	if (n <= factorial.size()) return factorial[n] * factorial_inv[n - r];
	std::cerr << "attention : factorial table is not constructed" << std::endl;
	r = std::min(r, n - r);
	modint<P> ret = 1;
	for (int i = 0; i < r; i++) ret *= n - i;
	return ret;
}

template<long long P> modint<P> combination(int n, int r) {
	if (n <= factorial.size()) return permutation<P>(n, r) * factorial_inv[r];
	std::cerr << "attention : factorial table is not constructed" << std::endl;
	r = std::min(r, n - r);
	modint<P> ret = 1;
	for (int i = 0; i < r; i++) {
		ret *= n - i;
		ret /= i + 1;
	}
	return ret;
}

template<long long MOD> std::ostream& operator<<(std::ostream& os, const modint<MOD>& target) {
	os << target.value;
	return os;
}

template<typename T, typename E> struct lazy_segment_tree {
	#define F std::function
	int N, M;
	std::vector<T> value;
	std::vector<E> lazy;
	std::vector<bool> flag;
	F<T(T, T)> op_val;
	F<E(E, E)> op_lz;
	F<T(T, E, int)> lz_to_val;
	T id_val;
	E id_lz;

	lazy_segment_tree(std::vector<T>& a, F<T(T, T)> f, F<E(E, E)> g, F<T(T, E, int)> h, T t, E e) {
		op_val = f; op_lz = g; lz_to_val = h; id_val = t; id_lz = e;
		int m = a.size(), x = 1;
		while (x < m) x *= 2;
		N = (M = x) * 2;
		value.resize(N, id_val);
		lazy.resize(N, id_lz);
		flag.resize(N, false);
		for (int i = 0; i < m; i++) value[M + i] = a[i];
		for (int i = M - 1; i > 0; i--) value[i] = op_val(value[i * 2], value[i * 2 + 1]);
	}

	lazy_segment_tree(int m, F<T(T, T)> f, F<E(E, E)> g, F<T(T, E, int)> h, T t, E e) {
		op_val = f; op_lz = g; lz_to_val = h; id_val = t; id_lz = e;
		int x = 1;
		while (x < m) x *= 2;
		N = (M = x) * 2;
		value.resize(N, id_val);
		lazy.resize(N, id_lz);
		flag.resize(N, false);
	}

	void lazy_eval(int i, int l, int r) {
		if (lazy[i] == id_lz) return;
		value[i] = lz_to_val(value[i], lazy[i], r - l);
		if (r - l > 1) {
			lazy[i * 2] = op_lz(lazy[i * 2], lazy[i]);
			lazy[i * 2 + 1] = op_lz(lazy[i * 2 + 1], lazy[i]);
		}
		lazy[i] = id_lz;
	}

	void range_update(int L, int R, E e, int i = 1, int l = 0, int r = -1) {
		if (r == -1) r = M;
		if (r <= L || R <= l) return;
		if (L <= l && r <= R) {
			lazy[i] = op_lz(lazy[i], e);
			return;
		}
		lazy_eval(i, l, r);
		flag[i] = true;
		range_update(L, R, e, i * 2, l, (l + r) / 2);
		range_update(L, R, e, i * 2 + 1, (l + r) / 2, r);
	}

	T range_fold(int L, int R, int i = 1, int l = 0, int r = -1) {
		if (r == -1) r = M;
		if (r <= L || R <= l) return id_val;
		lazy_eval(i, l, r);
		if (L <= l && r <= R && !flag[i]) return value[i];
		if (L <= l && r <= R) flag[i] = false;
		T ret = op_val(
			range_fold(L, R, i * 2, l, (l + r) / 2),
			range_fold(L, R, i * 2 + 1, (l + r) / 2, r)
		);
		if (L <= l && r <= R) value[i] = ret;
		return ret;
	}
	#undef F
};

int main() {
	constexpr int P = 998244353;

	int n, q;
	std::cin >> n >> q;
	std::vector<modint<P>> a(n);
	for (int i = 0; i < n; i++) std::cin >> a[i].value;

	lazy_segment_tree<modint<P>, std::pair<modint<P>, modint<P>>> sg(
		a,
		[](modint<P> a, modint<P> b){return a + b;},
		[](std::pair<modint<P>, modint<P>> a, std::pair<modint<P>, modint<P>> b){
			return (std::pair<modint<P>, modint<P>>){
				a.first * b.first,
				a.second * b.first + b.second
			};
		},
		[](modint<P> a, std::pair<modint<P>, modint<P>> b, int w) {return a * b.first + b.second * w;},
		0,
		{1, 0}
	);

	while (q--) {
		int op, l, r;
		std::cin >> op >> l >> r;
		if (op == 0) {
			modint<P> b, c;
			std::cin >> b.value >> c.value;
			sg.range_update(l, r, {b, c});
		} else std::cout << sg.range_fold(l, r) << '\n';
	}

	return 0;
}

Compiler output:
In file included from /usr/include/c++/14/bits/stl_algobase.h:64,
                 from /usr/include/c++/14/string:51,
                 from /usr/include/c++/14/bits/locale_classes.h:40,
                 from /usr/include/c++/14/bits/ios_base.h:41,
                 from /usr/include/c++/14/ios:44,
                 from /usr/include/c++/14/ostream:40,
                 from /usr/include/c++/14/iostream:41,
                 from a.cc:1:
/usr/include/c++/14/bits/stl_pair.h: In instantiation of 'constexpr bool std::operator==(const pair<_T1, _T2>&, const pair<_T1, _T2>&) [with _T1 = modint<998244353>; _T2 = modint<998244353>]':
a.cc:147:15:   required from 'void lazy_segment_tree<T, E>::lazy_eval(int, int, int) [with T = modint<998244353>; E = std::pair<modint<998244353>, modint<998244353> >]'
  147 |                 if (lazy[i] == id_lz) return;
      |                     ~~~~~~~~^~~~~~~~
a.cc:163:3:   required from 'void lazy_segment_tree<T, E>::range_update(int, int, E, int, int, int) [with T = modint<998244353>; E = std::pair<modint<998244353>, modint<998244353> >]'
  163 |                 lazy_eval(i, l, r);
      |                 ^~~~~~~~~
a.cc:213:19:   required from here
  213 |                         sg.range_update(l, r, {b, c});
      |                         ~~~~~~~~~~~~~~~^~~~~~~~~~~~~~
/usr/include/c++/14/bits/stl_pair.h:1034:24: error: no match for 'operator==' (operand types are 'const modint<998244353>' and 'const modint<998244353>')
 1034 |     { return __x.first == __y.first && __x.second == __y.second; }
      |              ~~~~~~~~~~^~~~~~~~~~~~
a.cc:35:14: note: candidate: 'bool modint<MOD>::operator==(modint<MOD>) [with long long int MOD = 998244353]' (near match)
   35 |         bool operator==(modint<MOD> right) {return ((this -> value) == right.value);}
      |              ^~~~~~~~
a.cc:35:14: note:   passing 'const modint<998244353>*' as 'this' argument discards qualifiers
In file included from /usr/include/c++/14/iosfwd:42,
                 from /usr/include/c++/14/ios:40:
/usr/include/c++/14/bits/postypes.h:192:5: note: candidate: 'template<class _StateT> bool std::operator==(const fpos<_StateT>&, const fpos<_StateT>&)'
  192 |     operator==(const fpos<_StateT>& __lhs, const fpos<_StateT>& __rhs)
      |     ^~~~~~~~
/usr/include/c++/14/bits/postypes.h:192:5: note:   template argument deduction/substitution failed:
/usr/include/c++/14/bits/stl_pair.h:1034:24: note:   'const modint<998244353>' is not derived from 'const std::fpos<_StateT>'
 1034 |     { return __x.first == __y.first && __x.second == __y.second; }
      |              ~~~~~~~~~~^~~~~~~~~~~~
In file included from /usr/include/c++/14/string:43:
/usr/include/c++/14/bits/allocator.h:235:5: note: candidate: 'template<class _T1, class _T2> bool std::operator==(const allocator<_CharT>&, const allocator<_T2>&)'
  235 |     operator==(const allocator<_T1>&, const allocator<_T2>&)
      |     ^~~~~~~~
/usr/include/c++/14/bits/allocator.h:235:5: note:   template argument deduction/substitution failed:
/usr/include/c++/14/bits/stl_pair.h:1034:24: note:   'const modint<998244353>' is not derived from 'const std::allocator<_CharT>'
 1034 |     { return __x.first == __y.first && __x.second == __y.second; }
      |              ~~~~~~~~~~^~~~~~~~~~~~
In file included from /usr/include/c++/14/string:48:
/usr/include/c++/14/bits/stl_iterator.h:441:5: note: candidate: 'template<class _Iterator> constexpr bool std::operator==(const reverse_iterator<_Iterator>&, const reverse_iterator<_Iterator>&)'
  441 |     operator==(const reverse_iterator<_Iterator>& __x,
      |     ^~~~~~~~
/usr/include/c++/14/bits/stl_iterator.h:441:5: note:   template argument deduction/substitution failed:
/usr/include/c++/14/bits/stl_pair.h:1034:24: note:   'const modint<998244353>' is not derived from 'const std::reverse_iterator<_Iterator>'
 1034 |     { return __x.first == __y.first && __x.second == __y.second; }
      |              ~~~~~~~~~~^~~~~~~~~~~~
/usr/include/c++/14/bits/stl_iterator.h:486:5: note: candidate: 'template<class _IteratorL, class _IteratorR> constexpr bool std::operator==(const reverse_iterator<_Iterator>&, const reverse_iterator<_IteratorR>&)'
  486 |     operator==(const reverse_iterator<_IteratorL>& __x,
      |     ^~~~~~~~
/usr/include/c++/14/bits/stl_iterator.h:486:5: note:   template argument deduction/substitution failed:
/usr/include/c++/14/bits/stl_pair.h:1034:24: note:   'const modint<998244353>' is not derived from 'const std::reverse_iterator<_Iterator>'
 1034 |     { return __x.first == __y.first && __x.second == __y.second; }
      |              ~~~~~~~~~~^~~~~~~~~~~~
/usr/include/c++/14/bits/stl_iterator.h:1667:5: note: candidate: 'template<class _IteratorL, class _IteratorR> constexpr bool std::operator==(const move_iterator<_IteratorL>&, const move_iterator<_IteratorR>&)'
 1667 |     operator==(const move_iterator<_IteratorL>& __x,
      |     ^~~~~~~~
/usr/include/c++/14/bits/stl_iterator.h:1667:5: note:   template argument deduction/substitution failed:
/usr/include/c++/14/bits/stl_pair.h:1034:24: note:   'const modint<998244353>' is not derived from 'const std::move_iterator<_IteratorL>'
 1034 |     { return __x.first == __y.first && __x.second == __y.second; }
      |              ~~~~~~~~~~^~~~~~~~~~~~
/usr/include/c++/14/bits/stl_iterator.h:1737:5: note: candidate: 'template<class _Iterator> constexpr bool std::operator==(const move_iterator<_IteratorL>&, const move_iterator<_IteratorL>&)'
 1737 |     operator==(const move_iterator<_Iterator>& __x,
      |     ^~~~~~~~
/usr/include/c++/14/bits/stl_iterator.h:1737:5: note:   template argument deduction/substitution failed:
/usr/include/c++/14/bits/stl_pair.h:1034:24: note:   'const modint<998244353>' is not derived from 'const std::move_iterator<_IteratorL>'
 1034 |     { return __x.first == __y.first && __x.second == __y.second; }
      |              ~~~~~~~~~~^~~~~~~~~~~~
/usr/include/c++/14/bits/stl_pair.h:1033:5: note: candidate: 'template<class _T1, class _T2> constexpr bool std::operator==(const pair<_T1, _T2>&, const pair<_T1, _T2>&)'
 1033 |     operator==(const pair<_T1, _T2>& __x, const pair<_T1, _T2>& __y)
      |     ^~~~~~~~
/usr/include/c++/14/bits/stl_pair.h:1033:5: note:   template argument deduction/substitution failed:
/usr/include/c++/14/bits/stl_pair.h:1034:24: note:   'const modint<998244353>' is not derived from 'const std::pair<_T1, _T2>'
 1034 |     { return __x.first == __y.first && __x.second == __y.second; }
      |              ~~~~~~~~~~^~~~~~~~~~~~
/usr/include/c++/14/bits/stl_pair.h:1034:51: error: no match for 'operator==' (operand types are 'const modint<998244353>' and 'const modint<998244353>')
 1034 |     { return __x.first == __y.first && __x.second == __y.second; }
      |                                        ~~~~~~~~~~~^~~~~~~~~~~~~
a.cc:35:14: note: candidate: 'bool modint<MOD>::operator==(modint<MOD>) [with long long int MOD = 998244353]' (near match)
   35 |         bool operator==(modint<MOD> right) {return ((this -> value) == right.value);}
      |              ^~~~~~~~
a.cc:35:14: note:   passing 'const modint<998244353>*' as 'this' argument discards qualifiers
/usr/include/c++/14/bits/postypes.h:192:5: note: candidate: 'template<class _StateT> bool std::operator==(const fpos<_StateT>&, const fpos<_StateT>&)'
  192 |     operator==(const fpos<_StateT>& __lhs, const fpos<_StateT>& __rhs)
      |     ^~~~~~~~
/usr/include/c++/14/bits/postypes.h:192:5: note:   template argument deduction/substitution failed:
/usr/include/c++/14/bits/stl_pair.h:1034:51: note:   'const modint<998244353>' is not derived from 'const std::fpos<_StateT>'
 1034 |     { return __x.first == __y.first && __x.second == __y.second; }
      |                                        ~~~~~~~~~~~^~~~~~~~~~~~~
/usr/include/c++/14/bits/allocator.h:235:5: note: candidate: 'template<class _T1, class _T2> bool std::operator==(const allocator<_CharT>&, const allocator<_T2>&)'
  235 |     operator==(const allocator<_T1>&, const allocator<_T2>&)
      |     ^~~~~~~~
/usr/include/c++/14/bits/allocator.h:235:5: note:   template argument deduction/substitution failed:
/usr/include/c++/14/bits/stl_pair.h:1034:51: note:   'const modint<998244353>' is not derived from 'const std::allocator<_CharT>'
 1034 |     { return __x.first == __y.first && __x.second == __y.second; }
      |                                        ~~~~~~~~~~~^~~~~~~~~~~~~
/usr/include/c++/14/bits/stl_iterator.h:441:5: note: candidate: 'template<class _Iterator> constexpr bool std::operator==(const reverse_iterator<_Iterator>&, const reverse_iterator<_Iterator>&)'
  441 |     operator==(const reverse_iterator<_Iterator>& __x,
      |     ^~~~~~~~
/usr/include/c++/14/bits/stl_iterator.h:441:5: note:   template argument deduction/substitution failed:
/usr/include/c++/14/bits/stl_pair.h:1034:51: note:   'const modint<998244353>' is not derived from 'const std::reverse_iterator<_Iterator>'
 1034 |     { return __x.first == __y.first && __x.second == __y.second; }
      |                                        ~~~~~~~~~~~^~~~~~~~~~~~~
/usr/include/c++/14/bits/stl_iterator.h:486:5: note: candidate: 'template<class _IteratorL, class _IteratorR> constexpr bool std::operator==(const reverse_iterator<_Iterator>&, const reverse_iterator<_IteratorR>&)'
  486 |     operator==(const reverse_iterator<_IteratorL>& __x,
      |     ^~~~~~~~
/usr/include/c++/14/bits/stl_iterator.h:486:5: note:   template argument deduction/substitution failed:
/usr/include/c++/14/bits/stl_pair.h:1034:51: note:   'const modint<998244353>' is not derived from 'const std::reverse_iterator<_Iterator>'
 1034 |     { return __x.first == __y.first && __x.second == __y.second; }
      |                                        ~~~~~~~~~~~^~~~~~~~~~~~~
/usr/include/c++/14/bits/stl_iterator.h:1667:5: note: candidate: 'template<class _IteratorL, class _IteratorR> constexpr bool std::operator==(const move_iterator<_IteratorL>&, const move_iterator<_IteratorR>&)'
 1667 |     operator==(const move_iterator<_IteratorL>& __x,
      |     ^~~~~~~~
/usr/include/c++/14/bits/stl_iterator.h:1667:5: note:   template argument deduction/substitution failed:
/usr/include/c++/14/bits/stl_p