GCC Code Coverage Report

Directory: ./
Coverage: low: ≥ 0% medium: ≥ 75.0% high: ≥ 90.0%
Coverage Exec / Excl / Total
Lines: 97.5% 119 / 0 / 122
Functions: 96.4% 27 / 0 / 28
Branches: 91.7% 33 / 0 / 36
src/ds/bst/fhq_w/lib.hpp
Line Branch Exec Source
1 #pragma once
2
3 #include "../../../util/alias/others/lib.hpp"
4 #include "../../../util/rand/lib.hpp"
5
6 namespace tifa_libs {
7
8 template <class T, auto op, auto e, class F, auto mapping, auto composition, auto id,
9 bool reverse_ = false, bool recovery = false>
10 requires requires(T val, T val_l, T val_r, F tag, F tag_l, F tag_r) {
11 { e() } -> std::same_as<T>;
12 { id() } -> std::same_as<F>;
13 { op(val_l, val_r) } -> std::same_as<T>;
14 { mapping(tag, val) } -> std::same_as<T>;
15 { composition(tag_l, tag_r) } -> std::same_as<F>;
16 }
17 class fhq_treap_w {
18 //! initial cnt = 1;
19 struct TIFA {
20 T w, val;
21 F sign;
22 u32 sz;
23 arr<u32, 2> son{};
24 i32 rad;
25 bool rev{false};
26 39750757 CEXP TIFA(T W = e(), T VAL = e(), u32 SZ = 0, i32 RAD = 0, F SIGN = id()) NE : w(W), val(VAL), sign(SIGN), sz(SZ), rad(RAD) {}
27 };
28 rand_gen<i32> gen;
29 vec<TIFA> t;
30 vecu sta;
31 u32 cnt{0};
32
33 14820801 CEXP u32 newnode(T val) NE {
34 u32 ret;
35
2/4
tifa_libs::fhq_treap_w<long, &(op(long, long)), &(e()), long, &(mapping(long, long)), &(composition(long, long)), &(id()), true, false>::newnode(long):
✗ Branch 1 not taken.
✓ Branch 2 taken 4639492 times.
tifa_libs::fhq_treap_w<std::pair<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> >, unsigned long>, &(op(std::pair<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> >, unsigned long>, std::pair<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> >, unsigned long>)), &(e()), std::pair<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> >, tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> > >, &(mapping(std::pair<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> >, tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> > >, std::pair<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> >, unsigned long>)), &(composition(std::pair<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> >, tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> > >, std::pair<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> >, tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> > >)), &(id()), true, false>::newnode(std::pair<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> >, unsigned long>):
✗ Branch 1 not taken.
✓ Branch 2 taken 10181309 times.
 14820801 if (sta.size()) ret = *sta.rbegin(), sta.pop_back(), t[ret] = TIFA(val, val, 1, gen());
36 14820801 else ret = ++cnt, t[ret] = TIFA(val, val, 1, gen());
37 14820801 return ret;
38 }
39 CEXP void rm(u32 u) NE { sta.push_back(u); }
40 1242940691 CEXP void update(u32 u) NE {
41 1242940691 t[u].w = op(t[t[u].son[0]].w, op(t[u].val, t[t[u].son[1]].w));
42 1242940691 t[u].sz = t[t[u].son[0]].sz + t[t[u].son[1]].sz + 1;
43 1242940691 }
44 144317650 CEXP void reverse__(u32 u) NE {
45 static_assert(reverse_);
46 144317650 swap(t[u].son[0], t[u].son[1]), t[u].rev ^= 1;
47 144317650 }
48 3784449575 CEXP void all_update(u32 u, F f) NE {
49
4/4
tifa_libs::fhq_treap_w<long, &(op(long, long)), &(e()), long, &(mapping(long, long)), &(composition(long, long)), &(id()), true, false>::all_update(unsigned int, long):
✓ Branch 0 taken 1332571977 times.
✓ Branch 1 taken 267754821 times.
tifa_libs::fhq_treap_w<std::pair<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> >, unsigned long>, &(op(std::pair<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> >, unsigned long>, std::pair<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> >, unsigned long>)), &(e()), std::pair<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> >, tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> > >, &(mapping(std::pair<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> >, tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> > >, std::pair<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> >, unsigned long>)), &(composition(std::pair<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> >, tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> > >, std::pair<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> >, tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> > >)), &(id()), true, false>::all_update(unsigned int, std::pair<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> >, tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> > >):
✓ Branch 0 taken 1779993867 times.
✓ Branch 1 taken 404128910 times.
 3784449575 if (u) {
50 3112565844 t[u].val = mapping(f, t[u].val);
51 3112565844 t[u].w = mapping(f, t[u].w);
52 3112565844 t[u].sign = composition(f, t[u].sign);
53 }
54 3784449575 }
55 1939274411 CEXP void pushdown(u32 u) NE {
56
4/4
tifa_libs::fhq_treap_w<long, &(op(long, long)), &(e()), long, &(mapping(long, long)), &(composition(long, long)), &(id()), true, false>::pushdown(unsigned int):
✓ Branch 0 taken 798953166 times.
✓ Branch 1 taken 18963418 times.
tifa_libs::fhq_treap_w<std::pair<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> >, unsigned long>, &(op(std::pair<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> >, unsigned long>, std::pair<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> >, unsigned long>)), &(e()), std::pair<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> >, tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> > >, &(mapping(std::pair<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> >, tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> > >, std::pair<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> >, unsigned long>)), &(composition(std::pair<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> >, tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> > >, std::pair<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> >, tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> > >)), &(id()), true, false>::pushdown(unsigned int):
✓ Branch 0 taken 1091527693 times.
✓ Branch 1 taken 29830134 times.
 1939274411 if (u) {
57 1890480859 all_update(t[u].son[0], t[u].sign);
58 1890480859 all_update(t[u].son[1], t[u].sign);
59 1890480859 t[u].sign = id();
60 if CEXP (reverse_)
61
3/4
tifa_libs::fhq_treap_w<long, &(op(long, long)), &(e()), long, &(mapping(long, long)), &(composition(long, long)), &(id()), true, false>::pushdown(unsigned int):
✗ Branch 1 not taken.
✓ Branch 2 taken 798953166 times.
tifa_libs::fhq_treap_w<std::pair<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> >, unsigned long>, &(op(std::pair<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> >, unsigned long>, std::pair<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> >, unsigned long>)), &(e()), std::pair<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> >, tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> > >, &(mapping(std::pair<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> >, tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> > >, std::pair<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> >, unsigned long>)), &(composition(std::pair<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> >, tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> > >, std::pair<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> >, tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> > >)), &(id()), true, false>::pushdown(unsigned int):
✓ Branch 1 taken 71625458 times.
✓ Branch 2 taken 1019902235 times.
 1890480859 if (t[u].rev) reverse__(t[u].son[0]), reverse__(t[u].son[1]), t[u].rev = 0;
62 }
63 1939274411 }
64
65 public:
66 u32 root{0};
67
68 168 CEXPE fhq_treap_w(u32 MAX_N) NE : gen(), t(MAX_N + 1), sta() {
69 if CEXP (recovery) sta.reserve(MAX_N + 1);
70 56 }
71
72 679233072 CEXP void split(u32 u, u32 k, u32& x, u32& y) NE {
73
4/4
tifa_libs::fhq_treap_w<long, &(op(long, long)), &(e()), long, &(mapping(long, long)), &(composition(long, long)), &(id()), true, false>::split(unsigned int, unsigned int, unsigned int&, unsigned int&):
✓ Branch 0 taken 14323926 times.
✓ Branch 1 taken 277620508 times.
tifa_libs::fhq_treap_w<std::pair<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> >, unsigned long>, &(op(std::pair<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> >, unsigned long>, std::pair<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> >, unsigned long>)), &(e()), std::pair<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> >, tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> > >, &(mapping(std::pair<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> >, tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> > >, std::pair<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> >, unsigned long>)), &(composition(std::pair<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> >, tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> > >, std::pair<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> >, tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> > >)), &(id()), true, false>::split(unsigned int, unsigned int, unsigned int&, unsigned int&):
✓ Branch 0 taken 20715073 times.
✓ Branch 1 taken 366573565 times.
 679233072 if (!u) x = y = 0;
74
4/4
tifa_libs::fhq_treap_w<long, &(op(long, long)), &(e()), long, &(mapping(long, long)), &(composition(long, long)), &(id()), true, false>::split(unsigned int, unsigned int, unsigned int&, unsigned int&):
✓ Branch 4 taken 176104652 times.
✓ Branch 5 taken 101515856 times.
tifa_libs::fhq_treap_w<std::pair<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> >, unsigned long>, &(op(std::pair<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> >, unsigned long>, std::pair<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> >, unsigned long>)), &(e()), std::pair<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> >, tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> > >, &(mapping(std::pair<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> >, tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> > >, std::pair<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> >, unsigned long>)), &(composition(std::pair<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> >, tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> > >, std::pair<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> >, tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> > >)), &(id()), true, false>::split(unsigned int, unsigned int, unsigned int&, unsigned int&):
✓ Branch 4 taken 199553641 times.
✓ Branch 5 taken 167019924 times.
 644194073 else if (pushdown(u); t[t[u].son[0]].sz < k) {
75 375658293 x = u;
76 375658293 split(t[u].son[1], k - t[t[u].son[0]].sz - 1, t[x].son[1], y);
77 375658293 update(x);
78 268535780 } else y = u, split(t[u].son[0], k, x, t[y].son[0]), update(y);
79 679233072 }
80 647540169 CEXP u32 merge(u32 x, u32 y) NE {
81 647540169 pushdown(x), pushdown(y);
82
8/8
tifa_libs::fhq_treap_w<long, &(op(long, long)), &(e()), long, &(mapping(long, long)), &(composition(long, long)), &(id()), true, false>::merge(unsigned int, unsigned int):
✓ Branch 0 taken 262237536 times.
✓ Branch 1 taken 7910502 times.
✓ Branch 2 taken 251184620 times.
✓ Branch 3 taken 11052916 times.
tifa_libs::fhq_treap_w<std::pair<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> >, unsigned long>, &(op(std::pair<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> >, unsigned long>, std::pair<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> >, unsigned long>)), &(e()), std::pair<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> >, tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> > >, &(mapping(std::pair<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> >, tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> > >, std::pair<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> >, unsigned long>)), &(composition(std::pair<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> >, tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> > >, std::pair<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> >, tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> > >)), &(id()), true, false>::merge(unsigned int, unsigned int):
✓ Branch 0 taken 364681277 times.
✓ Branch 1 taken 12710854 times.
✓ Branch 2 taken 347561998 times.
✓ Branch 3 taken 17119279 times.
 647540169 if (x && y) {
83
4/4
tifa_libs::fhq_treap_w<long, &(op(long, long)), &(e()), long, &(mapping(long, long)), &(composition(long, long)), &(id()), true, false>::merge(unsigned int, unsigned int):
✓ Branch 2 taken 159525284 times.
✓ Branch 3 taken 91659336 times.
tifa_libs::fhq_treap_w<std::pair<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> >, unsigned long>, &(op(std::pair<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> >, unsigned long>, std::pair<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> >, unsigned long>)), &(e()), std::pair<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> >, tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> > >, &(mapping(std::pair<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> >, tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> > >, std::pair<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> >, unsigned long>)), &(composition(std::pair<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> >, tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> > >, std::pair<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> >, tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> > >)), &(id()), true, false>::merge(unsigned int, unsigned int):
✓ Branch 2 taken 204465918 times.
✓ Branch 3 taken 143096080 times.
 598746618 if (t[x].rad <= t[y].rad) {
84 363991202 t[x].son[1] = merge(t[x].son[1], y), update(x);
85 363991202 return x;
86 }
87 234755416 t[y].son[0] = merge(x, t[y].son[0]), update(y);
88 234755416 return y;
89 48793551 } else return x + y;
90 }
91 14820801 CEXP void insert(T w, u32 id_) NE {
92 u32 x, y;
93 14820801 split(root, id_, x, y), root = merge(merge(x, newnode(w)), y);
94 14820801 }
95 10254858 CEXP void insert(T w) NE { insert(w, cnt); }
96 1066249 CEXP void erase(u32 id_) NE {
97 u32 x, y, z;
98 1066249 split(root, id_, x, y), split(y, 1, z, y);
99 if CEXP (recovery) rm(z);
100 1066249 root = merge(x, y);
101 1066249 }
102 3487857 CEXP void update(u32 l, u32 r, F f) NE {
103 u32 x, y, z;
104 3487857 split(root, r + 1, x, z), split(x, l, x, y);
105 3487857 all_update(y, f), root = merge(merge(x, y), z);
106 3487857 }
107 1066734 CEXP void reverse(u32 l, u32 r) NE {
108 static_assert(reverse_);
109 u32 x, y, z;
110 1066734 split(root, r + 1, x, z), split(x, l, x, y);
111 1066734 reverse__(y), root = merge(merge(x, y), z);
112 1066734 }
113 4488259 ND CEXP T query(u32 l, u32 r) NE {
114 u32 x, y, z;
115 4488259 split(root, r + 1, x, z), split(x, l, x, y);
116 4488259 T ret = t[y].w;
117 4488259 root = merge(merge(x, y), z);
118 4488259 return ret;
119 }
120 };
121
122 } // namespace tifa_libs
123