-
Notifications
You must be signed in to change notification settings - Fork 0
/
yosupo-range-affine-range-sum.test.cpp
59 lines (49 loc) · 1.18 KB
/
yosupo-range-affine-range-sum.test.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#define PROBLEM "https://judge.yosupo.jp/problem/range_affine_range_sum"
#include <bits/stdc++.h>
using namespace std;
#include "../segtree/lazy-segment-tree.cpp"
constexpr int mod = 998244353;
struct S {
int64_t sum;
int sz;
};
S op(S l, S r) {
l.sum += r.sum;
l.sz += r.sz;
if(l.sum >= mod) l.sum -= mod;
return l;
}
S e() { return S{0, 0}; }
struct F {
int64_t a, b;
};
S mapping(F f, S s) { return S{(s.sum * f.a + f.b * s.sz) % mod, s.sz}; }
F composition(F f, F g) { return F{f.a * g.a % mod, (f.a * g.b + f.b) % mod}; }
F id() { return F{1, 0}; }
int main() {
cin.tie(nullptr);
ios::sync_with_stdio(false);
int n, q;
cin >> n >> q;
vector<S> v(n);
for(int i = 0; i < n; i++) {
int a;
cin >> a;
v[i] = S{a, 1};
}
LazySegmentTree<S, op, e, F, mapping, composition, id> seg(v);
for(int i = 0; i < q; i++) {
int c;
cin >> c;
if(c) {
int l, r;
cin >> l >> r;
cout << seg.prod(l, r).sum << "\n";
} else {
int l, r, a, b;
cin >> l >> r >> a >> b;
seg.apply(l, r, F{a, b});
}
}
return 0;
}