src/ds/heap/skew/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, class C = std::less<T>> | ||
| 8 | class skew_heap { | ||
| 9 | static CEXP C comp_{}; | ||
| 10 | struct TIFA { | ||
| 11 | T k, lz; | ||
| 12 | u32 l, r, idx; | ||
| 13 | TIFA() = default; | ||
| 14 | 1804364 | TIFA(cT_(T) key, u32 i = -1_u32) | |
| 15 | 1804364 | NE : k(key), lz(0), l{-1_u32}, r{-1_u32}, idx{i} {} | |
| 16 | }; | ||
| 17 | |||
| 18 | 548953 | ND CEXP bool comp(u32 idxl, u32 idxr) CNE { return comp_(weight(idxl), weight(idxr)); } | |
| 19 | 2077802 | CEXP void pd(u32 idx) NE { | |
| 20 |
2/2✓ Branch 1 taken 1970896 times.
✓ Branch 2 taken 106906 times.
|
2077802 | if (d[idx].lz == 0) return; |
| 21 |
2/2✓ Branch 1 taken 102163 times.
✓ Branch 2 taken 4743 times.
|
106906 | if (~d[idx].l) d[d[idx].l].lz += d[idx].lz; |
| 22 |
2/2✓ Branch 1 taken 94208 times.
✓ Branch 2 taken 12698 times.
|
106906 | if (~d[idx].r) d[d[idx].r].lz += d[idx].lz; |
| 23 | 106906 | d[idx].k += d[idx].lz, d[idx].lz = 0; | |
| 24 | } | ||
| 25 | |||
| 26 | public: | ||
| 27 | vec<TIFA> d; | ||
| 28 | |||
| 29 | 2615556 | CEXP T weight(u32 idx) CNE { return d[idx].k + d[idx].lz; } | |
| 30 | 1804364 | CEXP u32 newheap(cT_(T) key, u32 idx = -1_u32) NE { | |
| 31 | 1804364 | d.emplace_back(key, idx); | |
| 32 | 1804364 | return u32(d.size() - 1); | |
| 33 | } | ||
| 34 | 3880492 | CEXP u32 merge(u32 x, u32 y) NE { | |
| 35 |
4/4✓ Branch 0 taken 632831 times.
✓ Branch 1 taken 3247661 times.
✓ Branch 2 taken 83878 times.
✓ Branch 3 taken 548953 times.
|
3880492 | if (!~x || !~y) return ~(x ^ y); |
| 36 |
2/2✓ Branch 1 taken 276275 times.
✓ Branch 2 taken 272678 times.
|
548953 | if (!comp(x, y)) swap(x, y); |
| 37 | 548953 | pd(x), swap(d[x].l, d[x].r = merge(d[x].r, y)); | |
| 38 | 548953 | return x; | |
| 39 | } | ||
| 40 | 11199 | CEXP void apply(u32 x, cT_(T) lz) NE { d[x].lz += lz, pd(x); } | |
| 41 | 1804364 | CEXP u32 push(u32 x, cT_(T) key, u32 idx = -1_u32) NE { return merge(x, newheap(key, idx)); } | |
| 42 | 1517650 | CEXP u32 pop(u32 x) NE { | |
| 43 | 1517650 | pd(x); | |
| 44 | 1517650 | return merge(d[x].l, d[x].r); | |
| 45 | } | ||
| 46 | }; | ||
| 47 | |||
| 48 | } // namespace tifa_libs | ||
| 49 |