src/ds/segtree/ctor/lib.hpp
| Line | Branch | Exec | Source |
|---|---|---|---|
| 1 | #pragma once | ||
| 2 | |||
| 3 | #include "../hp/lib.hpp" | ||
| 4 | |||
| 5 | namespace tifa_libs { | ||
| 6 | namespace segtree_ctor_impl_ { | ||
| 7 | template <class T> | ||
| 8 | struct P { | ||
| 9 | T v; | ||
| 10 | u32 l; | ||
| 11 | 57191848 | friend CEXP P operator+(P CR l, P CR r) NE { return {l.v + r.v, l.l + r.l}; } | |
| 12 | 1677221 | friend std::ostream& operator<<(std::ostream& os, P CR p) NE { return os << p.v; } | |
| 13 | }; | ||
| 14 | template <class T> | ||
| 15 | 62839554 | CEXP void set_(T& x, cT_(T) y) NE { x = y; } | |
| 16 | template <class T> | ||
| 17 | 57191848 | CEXP T add_op_(cT_(T) x, cT_(T) y) NE { return x + y; } | |
| 18 | template <class T> | ||
| 19 | 831139412 | CEXP void add_(T& x, cT_(T) y) NE { x += y; } | |
| 20 | template <class T> | ||
| 21 | 171772787 | CEXP T min_(cT_(T) x, cT_(T) y) NE { return min(x, y); } | |
| 22 | template <class T> | ||
| 23 | 171772787 | CEXP T max_(cT_(T) x, cT_(T) y) NE { return max(x, y); } | |
| 24 | template <class T> | ||
| 25 | 28401194 | CEXP void pset_(P<T>& x, cT_(T) y) NE { x.v = x.l * y; } | |
| 26 | template <class T> | ||
| 27 | 32271364 | CEXP void padd_(P<T>& x, cT_(T) y) NE { x.v += x.l * y; } | |
| 28 | template <class T> | ||
| 29 | 55 | CEXP auto segtl_addmax_ctor(cT_(T) ninf, spn<T> a) NE { return segtree<T, max_<T>, T, add_<T>, add_<T>>(ninf, T(0), a); } | |
| 30 | template <class T> | ||
| 31 | 55 | CEXP auto segtl_addmin_ctor(cT_(T) inf, spn<T> a) NE { return segtree<T, min_<T>, T, add_<T>, add_<T>>(inf, T(0), a); } | |
| 32 | template <class T> | ||
| 33 | 44 | CEXP auto segtl_addsum_ctor(vec<T> CR a) NE { | |
| 34 | 44 | vec<P<T>> b(a.size()); | |
| 35 |
2/2✓ Branch 3 taken 1680450 times.
✓ Branch 4 taken 44 times.
|
1680494 | flt_ (u32, i, 0, (u32)a.size()) b[i] = {a[i], 1}; |
| 36 | 44 | return segtree<P<T>, add_op_<P<T>>, T, padd_<T>, add_<T>>(P<T>{0, 0}, T(0), b); | |
| 37 | 44 | } | |
| 38 | template <class T> | ||
| 39 | 22 | CEXP auto segtl_setmax_ctor(cT_(T) ninf, spn<T> a) NE { return segtree<T, max_<T>, T, set_<T>, set_<T>>(ninf, ninf, a); } | |
| 40 | template <class T> | ||
| 41 | 22 | CEXP auto segtl_setmin_ctor(cT_(T) inf, spn<T> a) NE { return segtree<T, min_<T>, T, set_<T>, set_<T>>(inf, inf, a); } | |
| 42 | template <class T> | ||
| 43 | 50 | CEXP auto segtl_setsum_ctor(cT_(T) def_val, spn<T> a) NE { | |
| 44 | 50 | vec<P<T>> b(a.size()); | |
| 45 |
2/2✓ Branch 3 taken 1780788 times.
✓ Branch 4 taken 50 times.
|
1780838 | flt_ (u32, i, 0, (u32)a.size()) b[i] = {a[i], 1}; |
| 46 | 50 | return segtree<P<T>, add_op_<P<T>>, T, pset_<T>, set_<T>>(P<T>{0, 0}, def_val, b); | |
| 47 | 50 | } | |
| 48 | } // namespace segtree_ctor_impl_ | ||
| 49 | |||
| 50 | using segtree_ctor_impl_::segtl_addmax_ctor, segtree_ctor_impl_::segtl_addmin_ctor, | ||
| 51 | segtree_ctor_impl_::segtl_addsum_ctor, segtree_ctor_impl_::segtl_setmax_ctor, | ||
| 52 | segtree_ctor_impl_::segtl_setmin_ctor, segtree_ctor_impl_::segtl_setsum_ctor; | ||
| 53 | |||
| 54 | } // namespace tifa_libs | ||
| 55 |