/tmp/solutions/build/point_set_range_composite-fast.cpp:
1| |#include <common.h>
2| |#include <toy/bit.h>
3| |prelude;
4| |
5| |namespace {
6| |
7| |constexpr int N = 1e6;
8| |constexpr int P = 998244353;
9| |
10| |struct node {
11| | u32 a, b;
12| 39.6M| auto operator+(node t) -> node {
13| 39.6M| return {u32(u64(a) * t.a % P), u32((u64(a) * t.b + b) % P)};
14| 39.6M| }
15| 31.2M| auto operator+(u32 x) -> u32 { return (u64(a) * x + b) % P; }
16| |} a[N];
17| |
18| |} // namespace
19| |
20| 16|int main() {
21| 16| rd rd;
22| 16| wt wt;
23| 16| int n = rd.uh();
24| 16| int q = rd.uh();
25| 4.11M| for (int i = 0; i < n; ++i) a[n + n - 1 - i] = {rd.uw(), rd.uw()};
^4.11M^4.11M
------------------
| Branch (25:19): [True: 100.00%, False: 0.00%]
------------------
26| 4.11M| for (int i = n - 1; i >= 1; --i) a[i] = a[i * 2] + a[i * 2 + 1];
^4.11M^4.11M
------------------
| Branch (26:23): [True: 100.00%, False: 0.00%]
------------------
27| 3.83M| while (q--) {
------------------
| Branch (27:10): [True: 100.00%, False: 0.00%]
------------------
28| 3.83M| let t = rd.u1();
29| 3.83M| if (t == 0) {
------------------
| Branch (29:9): [True: 49.96%, False: 50.04%]
------------------
30| 1.91M| int k = n + n - 1 - rd.uh();
31| 1.91M| a[k] = {rd.uw(), rd.uw()};
32| 37.4M| for (k /= 2; k > 0; k /= 2) a[k] = a[k * 2] + a[k * 2 + 1];
^35.5M ^35.5M
------------------
| Branch (32:20): [True: 94.88%, False: 5.12%]
------------------
33| 1.91M| }
34| 3.83M| if (t == 1) {
------------------
| Branch (34:9): [True: 50.04%, False: 49.96%]
------------------
35| 1.91M| int r = n + n - rd.uh();
36| 1.91M| int l = n + n - 1 - rd.uh();
37| 1.91M| u32 x = rd.uw();
38| 1.91M| int k = log(l ^ r);
39| 1.91M| int R = r >> k;
40| 17.6M| for (r = r >> __builtin_ctz(r) ^ 1; r > R; r = r >> __builtin_ctz(r) ^ 1)
^15.6M
------------------
| Branch (40:43): [True: 89.10%, False: 10.90%]
------------------
41| 15.6M| x = a[r] + x;
42| 17.5M| for (int t = ~l & ~(-1 << k), i; t > 0; t -= 1 << i) {
^15.6M
------------------
| Branch (42:40): [True: 89.05%, False: 10.95%]
------------------
43| 15.6M| i = log(t);
44| 15.6M| x = a[l >> i ^ 1] + x;
45| 15.6M| }
46| 1.91M| wt.uw(x);
47| 1.91M| }
48| 3.83M| }
49| 16| return 0;
50| 16|}