Struct nekolib::ds::decremental_usize_set::DecrementalUsizeSet

pub struct DecrementalUsizeSet { /* private fields */ }

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

impl DecrementalUsizeSet

pub fn new(u: usize) -> Self

$S\gets\{0, 1, \dots, u-1\}$ で初期化。

pub fn universe_len(&self) -> usize

$u$ を返す。

pub fn len(&self) -> usize

$|S|$ を返す。

pub fn is_empty(&self) -> bool

$S=\emptyset$ を返す。

pub fn contains(&self, i: usize) -> bool

$i\in S$ を返す。

pub fn less(&self, i: usize) -> Option<usize>

$\max_{j\lt i}\text{ s.t. }j\in S$ を返す。

pub fn less_equal(&self, i: usize) -> Option<usize>

$\max_{j\le i}\text{ s.t. }j\in S$ を返す。

pub fn greater(&self, i: usize) -> Option<usize>

$\min_{j\gt i}\text{ s.t. }j\in S$ を返す。

pub fn greater_equal(&self, i: usize) -> Option<usize>

$\min_{j\ge i}\text{ s.t. }j\in S$ を返す。

pub fn remove(&mut self, i: usize) -> bool

$S\gets S\setminus\{i\}$ で更新する。