test/cpv/library-checker-datastructure/dynamic_sequence_range_affine_range_sum.cpp
| Line | Branch | Exec | Source |
|---|---|---|---|
| 1 | // competitive-verifier: PROBLEM https://judge.yosupo.jp/problem/dynamic_sequence_range_affine_range_sum | ||
| 2 | #include "../../../src/ds/bst/fhq_w/lib.hpp" | ||
| 3 | #include "../../../src/io/fastin/lib.hpp" | ||
| 4 | #include "../../../src/io/fastout/lib.hpp" | ||
| 5 | #include "../../../src/math/ds/mint/ms/lib.hpp" | ||
| 6 | |||
| 7 | using namespace tifa_libs; | ||
| 8 | using mint = mint_ms<998244353>; | ||
| 9 | using T = std::pair<mint, usz>; // sum len | ||
| 10 | using F = std::pair<mint, mint>; // mul add | ||
| 11 | |||
| 12 | 1428271126 | auto op(T a, T b) { return T{a.first + b.first, a.second + b.second}; } | |
| 13 | 30896448 | auto e() { return T{0, 0}; } | |
| 14 | 3559987734 | auto mapping(F f, T a) { | |
| 15 | 3559987734 | return T{f.first * a.first + f.second * a.second, a.second}; | |
| 16 | } | ||
| 17 | 1779993867 | auto composition(F f, F g) { | |
| 18 | 1779993867 | return F{f.first * g.first, f.first * g.second + f.second}; | |
| 19 | // g(x) = g.mul * x + g.add | ||
| 20 | // f(g(x)) = f.mul * (g.mul * x + g.add) + f.add = f.mul * g.mul * x + f.mul * g.add + f.add | ||
| 21 | } | ||
| 22 | 1117157226 | auto id() { return F(1, 0); } | |
| 23 | |||
| 24 | 33 | int main() { | |
| 25 | u32 n, q; | ||
| 26 | 33 | mint x, y; | |
| 27 | 33 | fin_uint >> n >> q; | |
| 28 | 33 | fhq_treap_w<T, op, e, F, mapping, composition, id, true> tr(n + q); | |
| 29 |
2/2✓ Branch 0 taken 5615366 times.
✓ Branch 1 taken 33 times.
|
5615399 | flt_ (u32, i, 0, n) |
| 30 | 5615366 | fin_uint >> x, tr.insert(T{x, 1}); | |
| 31 |
2/2✓ Branch 0 taken 9832825 times.
✓ Branch 1 taken 33 times.
|
9832858 | for (u32 i = 0, opt, l, r; i < q; ++i) { |
| 32 | 9832825 | fin_uint >> opt >> l; | |
| 33 |
2/2✓ Branch 0 taken 4565943 times.
✓ Branch 1 taken 5266882 times.
|
9832825 | if (opt == 0) fin_uint >> x, tr.insert(T{x, 1}, l); |
| 34 |
2/2✓ Branch 0 taken 1066249 times.
✓ Branch 1 taken 4200633 times.
|
5266882 | else if (opt == 1) tr.erase(l); |
| 35 |
2/2✓ Branch 0 taken 1066734 times.
✓ Branch 1 taken 3133899 times.
|
4200633 | else if (opt == 2) fin_uint >> r, tr.reverse(l, r - 1); |
| 36 |
2/2✓ Branch 0 taken 1067391 times.
✓ Branch 1 taken 2066508 times.
|
3133899 | else if (opt == 3) fin_uint >> r >> x >> y, tr.update(l, r - 1, T(x, y)); |
| 37 | 2066508 | else fin_uint >> r, fout << tr.query(l, r - 1).first << '\n'; | |
| 38 | } | ||
| 39 | 33 | return 0; | |
| 40 | 33 | } | |
| 41 |