Struct nekolib::ds::decremental_usize_set::DecrementalUsizeSet
source · pub struct DecrementalUsizeSet { /* private fields */ }
Expand description
usize
の decremental set。
$\{0, 1, \dots, u-1\}$ で初期化し、要素を取り除く操作を行える。
Complexity
演算 | 時間計算量 |
---|---|
new | $\Theta(n/w)$ |
remove | amortized $O(1)$ |
less | amortized $O(1)$ |
less_equal | amortized $O(1)$ |
greater | amortized $O(1)$ |
greater_equal | amortized $O(1)$ |
空間:$O(n)$ bits.
References
- https://atcoder.jp/contests/abc228/editorial/2962
- https://twitter.com/noshi91/status/1389116169634795525
Examples
use nekolib::ds::DecrementalUsizeSet;
let mut set = DecrementalUsizeSet::new(6);
assert_eq!(set.universe_len(), 6);
assert_eq!(set.len(), 6);
set.remove(3);
assert_eq!(set.less(3), Some(2));
assert_eq!(set.less_equal(3), Some(2));
assert_eq!(set.greater(3), Some(4));
assert_eq!(set.greater_equal(3), Some(4));
assert_eq!(set.less(4), Some(2));
assert_eq!(set.less_equal(4), Some(4));
assert_eq!(set.greater(4), Some(5));
assert_eq!(set.greater_equal(4), Some(4));
assert_eq!(set.less(0), None);
assert_eq!(set.greater(5), None);
set.remove(0);
set.remove(5);
assert_eq!(set.less_equal(0), None);
assert_eq!(set.greater_equal(5), None);
assert!(set.contains(4));
assert!(!set.contains(3));
assert_eq!(set.universe_len(), 6);
assert_eq!(set.len(), 3);
Implementations§
source§impl DecrementalUsizeSet
impl DecrementalUsizeSet
sourcepub fn universe_len(&self) -> usize
pub fn universe_len(&self) -> usize
$u$ を返す。
sourcepub fn less_equal(&self, i: usize) -> Option<usize>
pub fn less_equal(&self, i: usize) -> Option<usize>
$\max_{j\le i}\text{ s.t. }j\in S$ を返す。
sourcepub fn greater_equal(&self, i: usize) -> Option<usize>
pub fn greater_equal(&self, i: usize) -> Option<usize>
$\min_{j\ge i}\text{ s.t. }j\in S$ を返す。
Auto Trait Implementations§
impl !RefUnwindSafe for DecrementalUsizeSet
impl Send for DecrementalUsizeSet
impl !Sync for DecrementalUsizeSet
impl Unpin for DecrementalUsizeSet
impl UnwindSafe for DecrementalUsizeSet
Blanket Implementations§
source§impl<T> BorrowMut<T> for Twhere
T: ?Sized,
impl<T> BorrowMut<T> for Twhere T: ?Sized,
source§fn borrow_mut(&mut self) -> &mut T
fn borrow_mut(&mut self) -> &mut T
Mutably borrows from an owned value. Read more