src/ds/segtree/w/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 weighted_segtree { | ||
| 8 | cu32 n; | ||
| 9 | vecu t; | ||
| 10 | |||
| 11 | public: | ||
| 12 | 1184 | CEXPE weighted_segtree(u32 N) NE : n(N), t(N * 4) {} | |
| 13 | |||
| 14 | 613310 | CEXP void ins(u32 pos) NE { ins_(1, 0, n - 1, pos); } | |
| 15 | 613310 | CEXP void del(u32 pos) NE { del_(1, 0, n - 1, pos); } | |
| 16 | 613310 | CEXP u32 kth_min(u32 k) NE { return kth_min_(1, 0, n - 1, k); } | |
| 17 | CEXP u32 kth_max(u32 k) NE { return kth_max_(1, 0, n - 1, k); } | ||
| 18 | CEXP u32 frequency(u32 k) NE { return frequency_(1, 0, n - 1, k, k); } | ||
| 19 | CEXP u32 frequency(u32 l, u32 r) NE { return frequency_(1, 0, n - 1, l, r); } | ||
| 20 | |||
| 21 | private: | ||
| 22 | 8465073 | CEXP void ins_(u32 x, u32 l, u32 r, u32 pos) NE { | |
| 23 |
2/2✓ Branch 0 taken 613310 times.
✓ Branch 1 taken 7851763 times.
|
8465073 | if (l == r) return void(++t[x]); |
| 24 |
2/2✓ Branch 0 taken 4036522 times.
✓ Branch 1 taken 3815241 times.
|
7851763 | if (cu32 mid = l + (r - l) / 2; pos <= mid) ins_(x * 2, l, mid, pos); |
| 25 | 3815241 | else ins_(x * 2 + 1, mid + 1, r, pos); | |
| 26 | 7851763 | t[x] = t[x * 2] + t[x * 2 + 1]; | |
| 27 | } | ||
| 28 | 8465073 | CEXP void del_(u32 x, u32 l, u32 r, u32 pos) NE { | |
| 29 |
2/2✓ Branch 0 taken 613310 times.
✓ Branch 1 taken 7851763 times.
|
8465073 | if (l == r) return void(--t[x]); |
| 30 |
2/2✓ Branch 0 taken 4036522 times.
✓ Branch 1 taken 3815241 times.
|
7851763 | if (cu32 mid = l + (r - l) / 2; pos <= mid) del_(x * 2, l, mid, pos); |
| 31 | 3815241 | else del_(x * 2 + 1, mid + 1, r, pos); | |
| 32 | 7851763 | t[x] = t[x * 2] + t[x * 2 + 1]; | |
| 33 | } | ||
| 34 | 8465073 | ND CEXP u32 kth_min_(u32 x, u32 l, u32 r, u32 k) CNE { | |
| 35 |
2/2✓ Branch 0 taken 613310 times.
✓ Branch 1 taken 7851763 times.
|
8465073 | if (l == r) return l; |
| 36 |
2/2✓ Branch 1 taken 4036522 times.
✓ Branch 2 taken 3815241 times.
|
7851763 | if (cu32 mid = l + (r - l) / 2; k <= t[x * 2]) return kth_min_(x * 2, l, mid, k); |
| 37 | 3815241 | else return kth_min_(x * 2 + 1, mid + 1, r, k - t[x * 2]); | |
| 38 | } | ||
| 39 | ND CEXP u32 kth_max_(u32 x, u32 l, u32 r, u32 k) CNE { | ||
| 40 | if (l == r) return l; | ||
| 41 | if (cu32 mid = l + (r - l) / 2; k <= t[x * 2 + 1]) return kth_max_(x * 2 + 1, mid + 1, r, k); | ||
| 42 | else return kth_max_(x * 2, l, mid, k - t[x * 2 + 1]); | ||
| 43 | } | ||
| 44 | ND CEXP u32 frequency_(u32 x, u32 l, u32 r, u32 L, u32 R) CNE { | ||
| 45 | if (L <= l && R >= r) return t[x]; | ||
| 46 | cu32 mid = l + (r - l) / 2; | ||
| 47 | u32 ret = 0_u32; | ||
| 48 | if (L <= mid) ret = frequency_(x * 2, l, mid, L, R); | ||
| 49 | if (R > mid) ret += frequency_(x * 2 + 1, mid + 1, r, L, R); | ||
| 50 | return ret; | ||
| 51 | } | ||
| 52 | }; | ||
| 53 | |||
| 54 | } // namespace tifa_libs | ||
| 55 |