This documentation is automatically generated by online-judge-tools/verification-helper
#define PROBLEM "https://judge.yosupo.jp/problem/point_set_range_composite"
#include <bits/stdc++.h>
using namespace std;
#include "../segtree/segment-tree.cpp"
constexpr int mod = 998244353;
struct S {
int64_t a, b;
int64_t calc(int64_t x) { return (a * x + b) % mod; }
};
inline S op(S l, S r) { return S{r.a * l.a % mod, (r.a * l.b + r.b) % mod}; }
inline S e() { return S{1, 0}; }
int main() {
cin.tie(nullptr);
ios::sync_with_stdio(false);
int n, q;
cin >> n >> q;
vector<S> v;
v.reserve(n);
for(int i = 0; i < n; i++) {
int a, b;
cin >> a >> b;
v.push_back(S{a, b});
}
SegmentTree<S, op, e> seg(v);
for(int i = 0; i < q; i++) {
int a, b, c, d;
cin >> a >> b >> c >> d;
if(a)
cout << seg.prod(b, c).calc(d) << "\n";
else
seg.set(b, S{c, d});
}
return 0;
}
#line 1 "test/yosupo-point-set-range-composite.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/point_set_range_composite"
#include <bits/stdc++.h>
using namespace std;
#line 3 "segtree/segment-tree.cpp"
using namespace std;
// モノイド, 演算, 単位元
template <typename S, S (*op)(S, S), S (*e)()>
class SegmentTree {
private:
int _n, sz;
vector<S> data;
void calc(int k) { data[k] = op(data[k << 1], data[k << 1 | 1]); }
public:
SegmentTree() = default;
explicit SegmentTree(int n) : SegmentTree(vector<S>(n, e())) {}
explicit SegmentTree(const vector<S>& v) : _n(v.size()) {
sz = 1;
while(sz < _n) sz <<= 1;
data.assign(sz << 1, e());
for(int i = 0; i < _n; i++) data[sz + i] = v[i];
for(int i = sz - 1; i >= 1; i--) calc(i);
}
void set(int p, S x) {
assert(0 <= p && p < _n);
p += sz;
data[p] = x;
while(p >>= 1) calc(p);
}
S get(int p) {
assert(0 <= p && p < _n);
return data[p + sz];
}
S prod(int l, int r) {
assert(0 <= l && l <= r && r <= _n);
S sl = e(), sr = e();
l += sz;
r += sz;
while(l < r) {
if(l & 1) sl = op(sl, data[l++]);
if(r & 1) sr = op(data[--r], sr);
l >>= 1;
r >>= 1;
}
return op(sl, sr);
}
S all_prod() { return data[1]; }
};
/*
* @brief Segment-Tree
* @docs docs/segment-tree.md
*/
#line 7 "test/yosupo-point-set-range-composite.test.cpp"
constexpr int mod = 998244353;
struct S {
int64_t a, b;
int64_t calc(int64_t x) { return (a * x + b) % mod; }
};
inline S op(S l, S r) { return S{r.a * l.a % mod, (r.a * l.b + r.b) % mod}; }
inline S e() { return S{1, 0}; }
int main() {
cin.tie(nullptr);
ios::sync_with_stdio(false);
int n, q;
cin >> n >> q;
vector<S> v;
v.reserve(n);
for(int i = 0; i < n; i++) {
int a, b;
cin >> a >> b;
v.push_back(S{a, b});
}
SegmentTree<S, op, e> seg(v);
for(int i = 0; i < q; i++) {
int a, b, c, d;
cin >> a >> b >> c >> d;
if(a)
cout << seg.prod(b, c).calc(d) << "\n";
else
seg.set(b, S{c, d});
}
return 0;
}