/tmp/solutions/build/point_set_range_composite-slow.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| 52.1M| auto operator+(node t) -> node {
13| 52.1M| return {u32(u64(t.a) * a % P), u32((u64(t.a) * b + t.b) % P)};
14| 52.1M| }
15| 19.7M| 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) {
^4.11M
------------------
| Branch (25:19): [True: 100.00%, False: 0.00%]
------------------
26| 4.11M| int k = i * 2 + 1;
27| 4.11M| a[k] = {rd.uw(), rd.uw()};
28| 8.22M| for (int j = 1; k & (j * 2); k -= j, j *= 2) {
^4.11M
------------------
| Branch (28:21): [True: 50.00%, False: 50.00%]
------------------
29| 4.11M| a[k - j] = a[k - j * 2] + a[k];
30| 4.11M| }
31| 4.11M| }
32| 3.83M| while (q--) {
------------------
| Branch (32:10): [True: 100.00%, False: 0.00%]
------------------
33| 3.83M| let t = rd.u1();
34| 3.83M| if (t == 0) {
------------------
| Branch (34:9): [True: 49.96%, False: 50.04%]
------------------
35| 1.91M| int k = rd.uh() * 2 + 1;
36| 1.91M| a[k] = {rd.uw(), rd.uw()};
37| 34.3M| for (int j = 1;; j *= 2) {
^32.4M
38| 34.3M| if (k & (j * 2)) {
------------------
| Branch (38:13): [True: 47.21%, False: 52.79%]
------------------
39| 16.2M| a[k - j] = a[k - j * 2] + a[k];
40| 16.2M| k -= j;
41| 18.1M| } else {
42| 18.1M| if (k + j * 3 > n * 2) break;
^1.91M
------------------
| Branch (42:15): [True: 10.57%, False: 89.43%]
------------------
43| 16.2M| a[k + j] = a[k] + a[k + j * 2];
44| 16.2M| k += j;
45| 16.2M| }
46| 34.3M| }
47| 1.91M| }
48| 3.83M| if (t == 1) {
------------------
| Branch (48:9): [True: 50.04%, False: 49.96%]
------------------
49| 1.91M| int l = rd.uh() * 2 + 1;
50| 1.91M| int r = rd.uh() * 2 + 1;
51| 1.91M| u32 x = a[l] + rd.uw();
52| 1.91M| node f = {1, 0};
53| 1.91M| int k = (-1 << log(l ^ r)) & r;
54| 17.8M| for (++l; l < k; l += l & -l) {
^15.9M
------------------
| Branch (54:17): [True: 89.25%, False: 10.75%]
------------------
55| 15.9M| x = a[l + (l & -l) / 2] + x;
56| 15.9M| }
57| 17.5M| for (--r; r > k; r -= r & -r) {
^15.5M
------------------
| Branch (57:17): [True: 89.04%, False: 10.96%]
------------------
58| 15.5M| f = a[r - (r & -r) / 2] + f;
59| 15.5M| }
60| 1.91M| x = f + x;
61| 1.91M| wt.uw(x);
62| 1.91M| }
63| 3.83M| }
64| 16| return 0;
65| 16|}