This documentation is automatically generated by online-judge-tools/verification-helper
#define PROBLEM "https://judge.yosupo.jp/problem/point_set_range_composite"
#include <iostream>
#include "../../data_structure/DynamicSegmentTree.hpp"
#include "../../modint/modint.hpp"
using mint = ebi::modint998244353;
struct F {
mint a, b;
F(mint a, mint b) : a(a), b(b) {}
};
F op(F f1, F f2) {
return F(f2.a * f1.a, f2.a * f1.b + f2.b);
}
F e() {
return F(1, 0);
}
int main() {
int n, q;
std::cin >> n >> q;
ebi::DynamicSegmentTree<F, op, e> seg(n);
for (int i = 0; i < n; i++) {
int a, b;
std::cin >> a >> b;
seg.set(i, F(a, b));
}
while (q--) {
int t;
std::cin >> t;
if (t == 0) {
int p, c, d;
std::cin >> p >> c >> d;
seg.set(p, F(c, d));
} else {
int l, r, x;
std::cin >> l >> r >> x;
auto f = seg.prod(l, r);
std::cout << (f.a * x + f.b).value() << std::endl;
}
}
}
#line 1 "test/data_structure/Point_Set_Range_Composite.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/point_set_range_composite"
#include <iostream>
#line 2 "data_structure/DynamicSegmentTree.hpp"
#include <memory>
namespace ebi {
template <class Monoid, Monoid (*op)(Monoid, Monoid), Monoid (*e)()>
struct DynamicSegmentTree {
private:
struct Node;
using node_ptr = std::shared_ptr<Node>;
struct Node {
Monoid val;
node_ptr left, right, par;
Node(node_ptr _par = nullptr)
: val(e()), left(nullptr), right(nullptr), par(_par) {}
};
node_ptr root;
int n;
public:
DynamicSegmentTree(int _n = 0) : n(1) {
while (n < _n) {
n <<= 1;
}
root = std::make_shared<Node>();
}
void set(int i, Monoid x) {
int l = 0, r = n;
node_ptr now = root;
while (r - l > 1) {
int mid = (l + r) / 2;
if (i < mid) {
if (!now->left) {
now->left = std::make_shared<Node>(now);
}
now = now->left;
r = mid;
} else {
if (!now->right) {
now->right = std::make_shared<Node>(now);
}
now = now->right;
l = mid;
}
}
now->val = x;
while (now->par) {
now = now->par;
now->val = e();
if (now->left) now->val = now->left->val;
if (now->right) now->val = op(now->val, now->right->val);
}
}
Monoid prod(int tl, int tr, int l = 0, int r = -1, node_ptr now = nullptr) {
if (!now) now = root;
if (r < 0) r = n;
if (tr <= l || r <= tl) {
return e();
}
if (tl <= l && r <= tr) {
return now->val;
}
Monoid val = e();
if (now->left) {
val = prod(tl, tr, l, (l + r) / 2, now->left);
}
if (now->right) {
val = op(val, prod(tl, tr, (l + r) / 2, r, now->right));
}
return val;
}
Monoid all_prod() {
return root->val;
}
Monoid get(int i) {
int l = 0;
int r = n;
node_ptr now = root;
while (r - l > 1) {
int mid = (l + r) / 2;
if (i < mid) {
if (!now->left) return e();
now = now->left;
r = mid;
} else {
if (!now->right) return e();
now = now->right;
l = mid;
}
}
return now->val;
}
};
} // namespace ebi
#line 2 "modint/modint.hpp"
#include <cassert>
#line 5 "modint/modint.hpp"
#line 2 "modint/base.hpp"
#include <concepts>
#line 5 "modint/base.hpp"
#include <utility>
namespace ebi {
template <class T>
concept Modint = requires(T a, T b) {
a + b;
a - b;
a * b;
a / b;
a.inv();
a.val();
a.pow(std::declval<long long>());
T::mod();
};
template <Modint mint> std::istream &operator>>(std::istream &os, mint &a) {
long long x;
os >> x;
a = x;
return os;
}
template <Modint mint>
std::ostream &operator<<(std::ostream &os, const mint &a) {
return os << a.val();
}
} // namespace ebi
#line 7 "modint/modint.hpp"
namespace ebi {
template <int m> struct static_modint {
private:
using modint = static_modint;
public:
static constexpr int mod() {
return m;
}
static constexpr modint raw(int v) {
modint x;
x._v = v;
return x;
}
constexpr static_modint() : _v(0) {}
template <std::signed_integral T> constexpr static_modint(T v) {
long long x = (long long)(v % (long long)(umod()));
if (x < 0) x += umod();
_v = (unsigned int)(x);
}
template <std::unsigned_integral T> constexpr static_modint(T v) {
_v = (unsigned int)(v % umod());
}
constexpr unsigned int val() const {
return _v;
}
constexpr unsigned int value() const {
return val();
}
constexpr modint &operator++() {
_v++;
if (_v == umod()) _v = 0;
return *this;
}
constexpr modint &operator--() {
if (_v == 0) _v = umod();
_v--;
return *this;
}
constexpr modint operator++(int) {
modint res = *this;
++*this;
return res;
}
constexpr modint operator--(int) {
modint res = *this;
--*this;
return res;
}
constexpr modint &operator+=(const modint &rhs) {
_v += rhs._v;
if (_v >= umod()) _v -= umod();
return *this;
}
constexpr modint &operator-=(const modint &rhs) {
_v -= rhs._v;
if (_v >= umod()) _v += umod();
return *this;
}
constexpr modint &operator*=(const modint &rhs) {
unsigned long long x = _v;
x *= rhs._v;
_v = (unsigned int)(x % (unsigned long long)umod());
return *this;
}
constexpr modint &operator/=(const modint &rhs) {
return *this = *this * rhs.inv();
}
constexpr modint operator+() const {
return *this;
}
constexpr modint operator-() const {
return modint() - *this;
}
constexpr modint pow(long long n) const {
assert(0 <= n);
modint x = *this, res = 1;
while (n) {
if (n & 1) res *= x;
x *= x;
n >>= 1;
}
return res;
}
constexpr modint inv() const {
assert(_v);
return pow(umod() - 2);
}
friend modint operator+(const modint &lhs, const modint &rhs) {
return modint(lhs) += rhs;
}
friend modint operator-(const modint &lhs, const modint &rhs) {
return modint(lhs) -= rhs;
}
friend modint operator*(const modint &lhs, const modint &rhs) {
return modint(lhs) *= rhs;
}
friend modint operator/(const modint &lhs, const modint &rhs) {
return modint(lhs) /= rhs;
}
friend bool operator==(const modint &lhs, const modint &rhs) {
return lhs.val() == rhs.val();
}
friend bool operator!=(const modint &lhs, const modint &rhs) {
return !(lhs == rhs);
}
private:
unsigned int _v = 0;
static constexpr unsigned int umod() {
return m;
}
};
using modint998244353 = static_modint<998244353>;
using modint1000000007 = static_modint<1000000007>;
} // namespace ebi
#line 7 "test/data_structure/Point_Set_Range_Composite.test.cpp"
using mint = ebi::modint998244353;
struct F {
mint a, b;
F(mint a, mint b) : a(a), b(b) {}
};
F op(F f1, F f2) {
return F(f2.a * f1.a, f2.a * f1.b + f2.b);
}
F e() {
return F(1, 0);
}
int main() {
int n, q;
std::cin >> n >> q;
ebi::DynamicSegmentTree<F, op, e> seg(n);
for (int i = 0; i < n; i++) {
int a, b;
std::cin >> a >> b;
seg.set(i, F(a, b));
}
while (q--) {
int t;
std::cin >> t;
if (t == 0) {
int p, c, d;
std::cin >> p >> c >> d;
seg.set(p, F(c, d));
} else {
int l, r, x;
std::cin >> l >> r >> x;
auto f = seg.prod(l, r);
std::cout << (f.a * x + f.b).value() << std::endl;
}
}
}