src/ds/cartesian_tree/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> | ||
| 8 | class cartesian_tree { | ||
| 9 | struct TIFA { | ||
| 10 | u32 fa; | ||
| 11 | arr<u32, 2> son{-1u, -1u}; | ||
| 12 | }; | ||
| 13 | |||
| 14 | public: | ||
| 15 | u32 root{}; | ||
| 16 | vec<TIFA> t; | ||
| 17 | |||
| 18 | 75 | CEXPE cartesian_tree(vec<T> CR y) NE : t(y.size()) { | |
| 19 | 25 | vecu s(y.size() + 1); | |
| 20 | 25 | u32 top = 0; | |
| 21 |
2/2✓ Branch 1 taken 9123472 times.
✓ Branch 2 taken 25 times.
|
9123497 | flt_ (u32, i, 0, (u32)y.size()) { |
| 22 | 9123472 | u32 k = top; | |
| 23 |
6/6✓ Branch 0 taken 12400521 times.
✓ Branch 1 taken 2923198 times.
✓ Branch 5 taken 6200247 times.
✓ Branch 6 taken 6200274 times.
✓ Branch 7 taken 6200247 times.
✓ Branch 8 taken 9123472 times.
|
15323719 | while (k && y[s[k]] > y[i]) --k; |
| 24 |
2/2✓ Branch 0 taken 6200274 times.
✓ Branch 1 taken 2923198 times.
|
9123472 | if (k) t[s[k]].son[1] = i, t[i].fa = s[k]; |
| 25 |
2/2✓ Branch 0 taken 4561779 times.
✓ Branch 1 taken 4561693 times.
|
9123472 | if (k < top) t[i].son[0] = s[k + 1], t[s[k + 1]].fa = i; |
| 26 | 9123472 | s[top = ++k] = i; | |
| 27 | } | ||
| 28 | 25 | t[root = s[1]].fa = s[1]; | |
| 29 | 25 | } | |
| 30 | }; | ||
| 31 | |||
| 32 | } // namespace tifa_libs | ||
| 33 |