src/ds/segtree/persistent/lib.hpp
| Line | Branch | Exec | Source |
|---|---|---|---|
| 1 | #pragma once | ||
| 2 | |||
| 3 | #include "../../../util/alias/others/lib.hpp" | ||
| 4 | |||
| 5 | namespace tifa_libs { | ||
| 6 | |||
| 7 | class persistent_segtree { | ||
| 8 | //! initial cnt = 1; | ||
| 9 | u32 n, cnt{0}; | ||
| 10 | struct TIFA { | ||
| 11 | u32 w, ls, rs; | ||
| 12 | 24 | CEXP TIFA(u32 W = 0, u32 LS = 0, u32 RS = 0) NE : w(W), ls(LS), rs(RS) {} | |
| 13 | }; | ||
| 14 | vec<TIFA> t; | ||
| 15 | vecu root; | ||
| 16 | |||
| 17 | public: | ||
| 18 | 72 | CEXP persistent_segtree(spnu a, u32 N) NE : n{N}, t(a.size() * 24, TIFA()), root(a.size()) { | |
| 19 | 24 | build(root[0], 0, n - 1, a[0]); | |
| 20 |
2/2✓ Branch 5 taken 1528816 times.
✓ Branch 6 taken 24 times.
|
1528840 | flt_ (u32, i, 1, (u32)a.size()) add_(root[i - 1], root[i], 0, n - 1, a[i]); |
| 21 | 24 | } | |
| 22 | CEXP void add(u32 old_x, u32 x, u32 pos) NE { add_(root[old_x], root[x], 0, n - 1, pos); } | ||
| 23 |
2/2✓ Branch 0 taken 1932936 times.
✓ Branch 1 taken 11185 times.
|
1944121 | CEXP u32 kth_min(u32 x, u32 y, u32 k) NE { retif_((x), kth_min_(root[x - 1], root[y], 0, n - 1, k), kth_min_(root[y], 0, n - 1, k)); } |
| 24 | CEXP u32 kth_max(u32 x, u32 y, u32 k) NE { retif_((x), kth_max_(root[x - 1], root[y], 0, n - 1, k), kth_max_(root[y], 0, n - 1, k)); } | ||
| 25 | CEXP u32 frequency(u32 x, u32 y, u32 pos) NE { retif_((x), frequency_(root[x - 1], root[y], 0, n - 1, pos, pos), frequency_(root[y], 0, n - 1, pos, pos)); } | ||
| 26 | CEXP u32 frequency(u32 x, u32 y, u32 L, u32 R) NE { retif_((x), frequency_(root[x - 1], root[y], 0, n - 1, L, R), frequency_(root[y], 0, n - 1, L, R)); } | ||
| 27 | |||
| 28 | private: | ||
| 29 | 27990507 | CEXP void pushup(u32 x) NE { | |
| 30 |
1/2✓ Branch 2 taken 27990507 times.
✗ Branch 3 not taken.
|
27990507 | if (t[x].w = 0; t[x].ls) t[x].w = t[t[x].ls].w; |
| 31 |
1/2✓ Branch 1 taken 27990507 times.
✗ Branch 2 not taken.
|
27990507 | if (t[x].rs) t[x].w += t[t[x].rs].w; |
| 32 | 27990507 | } | |
| 33 | 3034646 | CEXP void build(u32& x, u32 l, u32 r, u32 pos) NE { | |
| 34 |
2/2✓ Branch 0 taken 1517335 times.
✓ Branch 1 taken 1517311 times.
|
3034646 | if (x = ++cnt; l == r) { |
| 35 |
2/2✓ Branch 0 taken 24 times.
✓ Branch 1 taken 1517311 times.
|
1517335 | if (l == pos) ++t[x].w; |
| 36 | 1517335 | return; | |
| 37 | } | ||
| 38 | 1517311 | cu32 mid = l + (r - l) / 2; | |
| 39 | 1517311 | build(t[x].ls, l, mid, pos), build(t[x].rs, mid + 1, r, pos), pushup(x); | |
| 40 | } | ||
| 41 | 28002012 | CEXP void add_(u32 old_x, u32& x, u32 l, u32 r, u32 pos) NE { | |
| 42 |
4/6✓ Branch 0 taken 28002012 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 28002012 times.
✗ Branch 3 not taken.
✓ Branch 7 taken 1528816 times.
✓ Branch 8 taken 26473196 times.
|
28002012 | if (assert(pos >= l && pos <= r), t[x = (++cnt)] = t[old_x]; l == r) return void(++t[x].w); |
| 43 |
2/2✓ Branch 0 taken 13526622 times.
✓ Branch 1 taken 12946574 times.
|
26473196 | if (cu32 mid = l + (r - l) / 2; pos <= mid) add_(t[old_x].ls, t[x].ls, l, mid, pos); |
| 44 | 12946574 | else add_(t[old_x].rs, t[x].rs, mid + 1, r, pos); | |
| 45 | 26473196 | pushup(x); | |
| 46 | } | ||
| 47 | 30569481 | CEXP u32 kth_min_(u32 x, u32 y, u32 l, u32 r, u32 k) NE { | |
| 48 |
2/2✓ Branch 0 taken 1932936 times.
✓ Branch 1 taken 28636545 times.
|
30569481 | if (l == r) return l; |
| 49 |
2/2✓ Branch 4 taken 14674883 times.
✓ Branch 5 taken 13961662 times.
|
28636545 | if (cu32 mid = l + (r - l) / 2, kk = t[t[y].ls].w - t[t[x].ls].w; k <= kk) return kth_min_(t[x].ls, t[y].ls, l, mid, k); |
| 50 | 13961662 | else return kth_min_(t[x].rs, t[y].rs, mid + 1, r, k - kk); | |
| 51 | } | ||
| 52 | CEXP u32 kth_max_(u32 x, u32 y, u32 l, u32 r, u32 k) NE { | ||
| 53 | if (l == r) return l; | ||
| 54 | if (cu32 mid = l + (r - l) / 2, kk = t[t[y].rs].w - t[t[x].rs].w; k <= kk) return kth_max_(t[x].rs, t[y].rs, mid + 1, r, k); | ||
| 55 | else return kth_max_(t[x].ls, t[y].ls, l, mid, k - kk); | ||
| 56 | } | ||
| 57 | CEXP u32 frequency_(u32 x, u32 y, u32 l, u32 r, u32 L, u32 R) NE { | ||
| 58 | if (assert(R >= l && L <= r); L <= l && R >= r) return t[y].w - t[x].w; | ||
| 59 | cu32 mid = l + (r - l) / 2; | ||
| 60 | u32 ret = 0_u32; | ||
| 61 | if (L <= mid) ret = frequency_(t[x].ls, t[y].rs, l, mid, L, R); | ||
| 62 | if (R > mid) ret += frequency_(t[x].rs, t[y].rs, mid + 1, r, L, R); | ||
| 63 | return ret; | ||
| 64 | } | ||
| 65 | 72592 | CEXP u32 kth_min_(u32 y, u32 l, u32 r, u32 k) NE { | |
| 66 |
2/2✓ Branch 0 taken 11185 times.
✓ Branch 1 taken 61407 times.
|
72592 | if (l == r) return l; |
| 67 |
2/2✓ Branch 2 taken 33170 times.
✓ Branch 3 taken 28237 times.
|
61407 | if (cu32 mid = l + (r - l) / 2, kk = t[t[y].ls].w; k <= kk) return kth_min_(t[y].ls, l, mid, k); |
| 68 | 28237 | else return kth_min_(t[y].rs, mid + 1, r, k - kk); | |
| 69 | } | ||
| 70 | CEXP u32 kth_max_(u32 y, u32 l, u32 r, u32 k) NE { | ||
| 71 | if (l == r) return l; | ||
| 72 | if (cu32 mid = l + (r - l) / 2, kk = t[t[y].rs].w; k <= kk) return kth_max_(t[y].rs, mid + 1, r, k); | ||
| 73 | else return kth_max_(t[y].ls, l, mid, k - kk); | ||
| 74 | } | ||
| 75 | CEXP u32 frequency_(u32 y, u32 l, u32 r, u32 L, u32 R) NE { | ||
| 76 | if (assert(R >= l && L <= r); L <= l && R >= r) return t[y].w; | ||
| 77 | cu32 mid = l + (r - l) / 2; | ||
| 78 | u32 ret = 0_u32; | ||
| 79 | if (L <= mid) ret = frequency_(t[y].rs, l, mid, L, R); | ||
| 80 | if (R > mid) ret += frequency_(t[y].rs, mid + 1, r, L, R); | ||
| 81 | return ret; | ||
| 82 | } | ||
| 83 | }; | ||
| 84 | |||
| 85 | } // namespace tifa_libs | ||
| 86 |