src/ds/rmq/linear/lib.hpp
| Line | Branch | Exec | Source |
|---|---|---|---|
| 1 | #pragma once | ||
| 2 | |||
| 3 | #include "../../../bit/lowbit/lib.hpp" | ||
| 4 | #include "../../../util/alias/others/lib.hpp" | ||
| 5 | |||
| 6 | namespace tifa_libs { | ||
| 7 | |||
| 8 | template <class T, class F> | ||
| 9 | class rmq_linear { | ||
| 10 | F cmp{}; // std::less<> -> min, std::greater<> -> max | ||
| 11 | u32 n; | ||
| 12 | vec<T> a; | ||
| 13 | vecu in, asc, head; | ||
| 14 | 6841143 | ND CEXP u32 idx(u32 l, u32 r) CNE { | |
| 15 |
2/2✓ Branch 2 taken 6782637 times.
✓ Branch 3 taken 58506 times.
|
6841143 | if (u32 j = in[l] ^ in[r]) { |
| 16 |
2/2✓ Branch 5 taken 6581544 times.
✓ Branch 6 taken 201093 times.
|
6782637 | if (j = asc[l] & asc[r] & -std::bit_floor(j); auto k = std::bit_floor(asc[l] ^ j)) l = head[(in[l] & -k) | k]; |
| 17 |
2/2✓ Branch 2 taken 6548736 times.
✓ Branch 3 taken 233901 times.
|
6782637 | if (auto k = std::bit_floor(asc[r] ^ j)) r = head[(in[r] & -k) | k]; |
| 18 | } | ||
| 19 |
2/2✓ Branch 3 taken 3432711 times.
✓ Branch 4 taken 3408432 times.
|
6841143 | retif_((cmp(a[l], a[r])), l, r); |
| 20 | } | ||
| 21 | |||
| 22 | public: | ||
| 23 | 216 | CEXP rmq_linear(spn<T> a) NE : n{(u32)a.size()}, a{a.begin(), a.end()}, in(n), asc(n), head(n + 1) { | |
| 24 | 54 | vecu st{-1_u32}; | |
| 25 |
2/2✓ Branch 0 taken 7112542 times.
✓ Branch 1 taken 27 times.
|
7112569 | flt_ (u32, i, 0, n + 1) { |
| 26 | 7112542 | u32 prev = 0; | |
| 27 |
8/8✓ Branch 1 taken 14179196 times.
✓ Branch 2 taken 45861 times.
✓ Branch 3 taken 14178952 times.
✓ Branch 4 taken 244 times.
✓ Branch 9 taken 7112271 times.
✓ Branch 10 taken 7066681 times.
✓ Branch 11 taken 7112515 times.
✓ Branch 12 taken 7112542 times.
|
14225057 | while (st.size() > 1 && (i == n || !cmp(a[st.back()], a[i]))) { |
| 28 | 7112515 | head[prev] = st.back(); | |
| 29 | 7112515 | auto j = st[st.size() - 2] + 1, k = std::bit_floor(i ^ j); | |
| 30 | 7112515 | in[st.back()] = prev = i & -k, asc[j] |= k, st.pop_back(); | |
| 31 | } | ||
| 32 | 7112542 | st.push_back(head[prev] = i); | |
| 33 | } | ||
| 34 |
2/2✓ Branch 5 taken 7112488 times.
✓ Branch 6 taken 27 times.
|
7112515 | flt_ (u32, i, 1, n) asc[i] = (asc[i] | asc[i - 1]) & -lowbit(in[i]); |
| 35 | 27 | } | |
| 36 | //! [l, r] | ||
| 37 | 6841143 | CEXP T query(u32 l, u32 r) CNE { return a[idx(l, r)]; } | |
| 38 | }; | ||
| 39 | |||
| 40 | } // namespace tifa_libs | ||
| 41 |