src/ds/trie01/lib.hpp
| Line | Branch | Exec | Source |
|---|---|---|---|
| 1 | #pragma once | ||
| 2 | |||
| 3 | #include "../../util/alias/others/lib.hpp" | ||
| 4 | |||
| 5 | namespace tifa_libs { | ||
| 6 | |||
| 7 | template <class T = i32, bool persistent = false> | ||
| 8 | struct trie01 { | ||
| 9 | struct TIFA { | ||
| 10 | // NOLINTNEXTLINE(modernize-avoid-c-arrays) | ||
| 11 | u32 nxt[2]{0, 0}; | ||
| 12 | T val{0}; | ||
| 13 | vecu idxs{}; | ||
| 14 | }; | ||
| 15 | |||
| 16 | ci32 MAX_DEP; | ||
| 17 | vec<TIFA> data; | ||
| 18 | u32 root{1}; | ||
| 19 | |||
| 20 | 64 | CEXPE trie01(i32 max_depth = 32) NE : MAX_DEP(max_depth), data(2) { | |
| 21 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 32 times.
|
32 | assert(max_depth > 0); |
| 22 | 32 | data.reserve(1_u64 << (max_depth / 2)); | |
| 23 | 32 | } | |
| 24 | |||
| 25 | 2233180 | CEXP void add(u64 bit, T val = 1, int idx = -1, u64 xv = 0) NE { root = add_(root, bit, idx, MAX_DEP, val, xv); } | |
| 26 | 2354811 | ND CEXP u32 find(u64 bit, u64 xv = 0) CNE { return find_(root, bit, MAX_DEP, xv); } | |
| 27 | 2051392 | CEXP auto kth_element(T k, u64 xv = 0) CNE { | |
| 28 |
2/4✓ Branch 0 taken 2051392 times.
✗ Branch 1 not taken.
✓ Branch 3 taken 2051392 times.
✗ Branch 4 not taken.
|
2051392 | assert(0 <= k && k < data[root].val); |
| 29 | 2051392 | return kth_(root, k, MAX_DEP, xv); | |
| 30 | } | ||
| 31 | 622814 | CEXP T count_less(u64 bit, u64 xv = 0) CNE { return cntle_(root, bit, MAX_DEP, xv); } | |
| 32 | |||
| 33 | private: | ||
| 34 | 67748504 | CEXP u32 add_(u32 t, u64 bit, int idx, int dep, T x, u64 xv, bool need = true) NE { | |
| 35 | if CEXP (persistent) | ||
| 36 | if (need) t = (u32)data.size(), data.emplace_back(); | ||
| 37 |
2/2✓ Branch 0 taken 2233180 times.
✓ Branch 1 taken 65515324 times.
|
67748504 | if (!~dep) { |
| 38 |
1/2✗ Branch 1 not taken.
✓ Branch 2 taken 2233180 times.
|
2233180 | if (data[t].val += x; idx >= 0) data[t].idxs.push_back((u32)idx); |
| 39 | } else { | ||
| 40 |
2/2✓ Branch 1 taken 19572116 times.
✓ Branch 2 taken 45943208 times.
|
65515324 | if (auto& _ = data[t].nxt[(xv ^ bit) >> dep & 1]; !_) _ = (u32)data.size(), data.emplace_back(), need = false; |
| 41 | 65515324 | data[t].nxt[(xv ^ bit) >> dep & 1] = add_(data[t].nxt[(xv ^ bit) >> dep & 1], bit, idx, dep - 1, x, xv, need); | |
| 42 | 65515324 | data[t].val += x; | |
| 43 | } | ||
| 44 | 67748504 | return t; | |
| 45 | } | ||
| 46 | 50811277 | ND CEXP u32 find_(u32 t, u64 bit, int dep, u64 xv) CNE { | |
| 47 |
2/2✓ Branch 0 taken 535916 times.
✓ Branch 1 taken 50275361 times.
|
50811277 | if (!~dep) return t; |
| 48 | 50275361 | const auto to = data[t].nxt[(xv ^ bit) >> dep & 1]; | |
| 49 |
2/2✓ Branch 0 taken 48456466 times.
✓ Branch 1 taken 1818895 times.
|
50275361 | retif_((to), find_(to, bit, dep - 1, xv), 0); |
| 50 | } | ||
| 51 | 65644544 | CEXP std::pair<u64, u32> kth_(u32 t, T k, int idx, u64 xv) CNE { | |
| 52 |
2/2✓ Branch 0 taken 2051392 times.
✓ Branch 1 taken 63593152 times.
|
65644544 | if (!~idx) return {0, t}; |
| 53 | 63593152 | const bool f = xv >> idx & 1; | |
| 54 |
4/4✓ Branch 1 taken 49172361 times.
✓ Branch 2 taken 14420791 times.
✓ Branch 4 taken 15101433 times.
✓ Branch 5 taken 48491719 times.
|
63593152 | if (auto _ = data[t].nxt[f]; (_ ? data[_].val : 0) <= k) { |
| 55 |
2/2✓ Branch 0 taken 680642 times.
✓ Branch 1 taken 14420791 times.
|
15101433 | auto ret = kth_(data[t].nxt[f ^ 1], k - (_ ? data[_].val : 0), idx - 1, xv); |
| 56 | 15101433 | ret.first |= 1_u64 << idx; | |
| 57 | 15101433 | return ret; | |
| 58 | 48491719 | } else return kth_(_, k, idx - 1, xv); | |
| 59 | } | ||
| 60 | 13060962 | CEXP T cntle_(u32 t, u64 bit, int idx, u64 xv) CNE { | |
| 61 |
2/2✓ Branch 0 taken 164704 times.
✓ Branch 1 taken 12896258 times.
|
13060962 | if (!~idx) return 0; |
| 62 | 12896258 | T ret = 0; | |
| 63 |
6/6✓ Branch 0 taken 4164367 times.
✓ Branch 1 taken 8731891 times.
✓ Branch 3 taken 3910422 times.
✓ Branch 4 taken 253945 times.
✓ Branch 5 taken 3910422 times.
✓ Branch 6 taken 8985836 times.
|
12896258 | if (const bool f = xv >> idx & 1; (bit >> idx & 1) && data[t].nxt[f]) ret += data[data[t].nxt[f]].val; |
| 64 |
2/2✓ Branch 1 taken 12438148 times.
✓ Branch 2 taken 458110 times.
|
12896258 | if (auto _ = data[t].nxt[(xv ^ bit) >> idx & 1]; _) ret += cntle_(_, bit, idx - 1, xv); |
| 65 | 12896258 | return ret; | |
| 66 | } | ||
| 67 | }; | ||
| 68 | |||
| 69 | } // namespace tifa_libs | ||
| 70 |