src/ds/segtree/lichao/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, T (*op)(T, T)> | ||
| 8 | class lichao_segtree { | ||
| 9 | struct seg { | ||
| 10 | u32 id; | ||
| 11 | T a, b, l, r; | ||
| 12 | 144908083 | CEXP T w(T x) CNE { return a * x + b; } | |
| 13 | }; | ||
| 14 | u32 sz; | ||
| 15 | vec<T> lsh; | ||
| 16 | vec<seg> t; | ||
| 17 | |||
| 18 | public: | ||
| 19 | 65 | CEXPE lichao_segtree(spn<T> lsh) NE : lsh(begin(lsh), end(lsh)), t(lsh.size() * 4) { sz = (u32)lsh.size(); } | |
| 20 | |||
| 21 | // $y = ax + b~(x \in [l, r])$ | ||
| 22 | 2440422 | CEXP void add(T a, T b, T l, T r, u32 id = 1) NE { add(1, 0, sz - 1, u32(lower_bound(lsh, l) - begin(lsh)), u32(lower_bound(lsh, r) - begin(lsh)), {id, a, b, l, r}); } | |
| 23 | 709127 | T query(T pos) NE { return query(1, 0, sz - 1, pos); } | |
| 24 | |||
| 25 | private: | ||
| 26 | // min: <= max: >= | ||
| 27 | 82467407 | CEXP bool pd(T a, T b) CNE { return op(a, b) == a; } | |
| 28 | 114009214 | CEXP void add(u32 x, u32 l, u32 r, u32 L, u32 R, seg CR k) NE { | |
| 29 | 114009214 | u32 mid = l + (r - l) / 2; | |
| 30 |
4/4✓ Branch 0 taken 73339673 times.
✓ Branch 1 taken 40669541 times.
✓ Branch 2 taken 39434493 times.
✓ Branch 3 taken 33905180 times.
|
114009214 | if (L <= l && R >= r) { |
| 31 |
2/2✓ Branch 1 taken 5621562 times.
✓ Branch 2 taken 33812931 times.
|
39434493 | if (!t[x].id) return void(t[x] = k); |
| 32 | 33812931 | T tl = t[x].w(lsh[l]), tr = t[x].w(lsh[r]), kl = k.w(lsh[l]), kr = k.w(lsh[r]); | |
| 33 |
6/6✓ Branch 1 taken 26787688 times.
✓ Branch 2 taken 7025243 times.
✓ Branch 4 taken 26783682 times.
✓ Branch 5 taken 4006 times.
✓ Branch 6 taken 26783682 times.
✓ Branch 7 taken 7029249 times.
|
33812931 | if (pd(tl, kl) && pd(tr, kr)) return; |
| 34 |
6/6✓ Branch 1 taken 7025243 times.
✓ Branch 2 taken 4006 times.
✓ Branch 4 taken 3827278 times.
✓ Branch 5 taken 3197965 times.
✓ Branch 6 taken 3827278 times.
✓ Branch 7 taken 3201971 times.
|
7029249 | if (!pd(tl, kl) && !pd(tr, kr)) return void(t[x] = k); |
| 35 |
2/2✓ Branch 3 taken 3197965 times.
✓ Branch 4 taken 4006 times.
|
3201971 | if (T in = (t[x].b - k.b) / (k.a - t[x].a); pd(kl, tl)) { |
| 36 |
2/2✓ Branch 1 taken 1528473 times.
✓ Branch 2 taken 1669492 times.
|
3197965 | if (in <= lsh[mid]) add(x << 1, l, mid, L, R, k); |
| 37 | 1669492 | else add(x << 1 | 1, mid + 1, r, L, R, t[x]), t[x] = k; | |
| 38 |
2/2✓ Branch 1 taken 3413 times.
✓ Branch 2 taken 593 times.
|
4006 | } else if (in > lsh[mid]) add(x << 1 | 1, mid + 1, r, L, R, k); |
| 39 | 593 | else add(x << 1, l, mid, L, R, t[x]), t[x] = k; | |
| 40 | 3201971 | return; | |
| 41 | } | ||
| 42 |
2/2✓ Branch 0 taken 54616025 times.
✓ Branch 1 taken 19958696 times.
|
74574721 | if (L <= mid) add(x << 1, l, mid, L, R, k); |
| 43 |
2/2✓ Branch 0 taken 53750796 times.
✓ Branch 1 taken 20823925 times.
|
74574721 | if (R > mid) add(x << 1 | 1, mid + 1, r, L, R, k); |
| 44 | } | ||
| 45 | 14266684 | CEXP T query(u32 x, u32 l, u32 r, T pos) NE { | |
| 46 | 14266684 | T MIN = std::numeric_limits<T>::lowest(), MAX = std::numeric_limits<T>::max(); | |
| 47 |
3/4✓ Branch 1 taken 9656359 times.
✓ Branch 2 taken 4610325 times.
✓ Branch 6 taken 4610325 times.
✗ Branch 7 not taken.
|
14266684 | T ret = t[x].id ? t[x].w(pos) : (pd(MIN, MAX) ? MAX : MIN); |
| 48 |
2/2✓ Branch 0 taken 709127 times.
✓ Branch 1 taken 13557557 times.
|
14266684 | if (l == r) return ret; |
| 49 |
2/2✓ Branch 1 taken 6923280 times.
✓ Branch 2 taken 6634277 times.
|
13557557 | if (u32 mid = l + (r - l) / 2; pos <= lsh[mid]) return op(ret, query(x << 1, l, mid, pos)); |
| 50 | 6634277 | else return op(ret, query(x << 1 | 1, mid + 1, r, pos)); | |
| 51 | } | ||
| 52 | }; | ||
| 53 | } // namespace tifa_libs | ||
| 54 |