use std::{
collections::BTreeSet,
ops::{Bound::*, RangeBounds},
};
#[derive(Debug)]
pub struct MexSet {
pub ranges: BTreeSet<(isize, isize)>,
}
impl Default for MexSet {
fn default() -> Self {
Self::new()
}
}
impl MexSet {
const INF: isize = isize::MIN;
const SUP: isize = isize::MAX;
pub fn new() -> Self {
let ranges = [(Self::INF, Self::INF), (Self::SUP, Self::SUP)]
.into_iter()
.collect();
Self { ranges }
}
pub fn insert(&mut self, x: isize) -> bool {
if self.ranges.len() == 1 {
return false;
}
let &(ll, l) = self.ranges.range(..(x + 1, x + 1)).next_back().unwrap();
let &(r, rr) = self.ranges.range((x + 1, x + 1)..).next().unwrap();
if x <= l {
return false;
}
match (l == x - 1, x + 1 == r) {
(false, false) => {
self.ranges.insert((x, x));
}
(false, true) => {
self.ranges.remove(&(r, rr));
self.ranges.insert((x, rr));
}
(true, false) => {
self.ranges.remove(&(ll, l));
self.ranges.insert((ll, x));
}
(true, true) => {
self.ranges.remove(&(ll, l));
self.ranges.remove(&(r, rr));
self.ranges.insert((ll, rr));
}
}
true
}
pub fn delete(&mut self, x: isize) -> bool {
let &(ll, l) = self.ranges.range(..(x + 1, x + 1)).next_back().unwrap();
if l < x {
return false;
}
self.ranges.remove(&(ll, l));
match (ll == x, x == l) {
(false, false) => {
self.ranges.insert((ll, x - 1));
self.ranges.insert((x + 1, l));
}
(false, true) => {
self.ranges.insert((ll, x - 1));
}
(true, false) => {
self.ranges.insert((x + 1, l));
}
(true, true) => (),
}
true
}
#[inline]
fn parse_range<R: RangeBounds<isize>>(range: R) -> (isize, isize) {
let start = match range.start_bound() {
Unbounded => Self::INF,
Included(&s) => s,
Excluded(&s) => s + 1,
};
let end = match range.end_bound() {
Unbounded => Self::SUP,
Included(&e) => e,
Excluded(&e) => e - 1,
};
(start, end)
}
pub fn insert_range<R: RangeBounds<isize>>(&mut self, range: R) -> bool {
let (start, end) = Self::parse_range(range);
if start > end {
return false;
}
if self.ranges.len() == 1 {
return false;
}
if (start, end) == (Self::INF, Self::SUP) {
let len = self.ranges.len();
self.ranges.clear();
self.ranges.insert((Self::INF, Self::SUP));
return len != self.ranges.len();
}
if start == end {
return self.insert(start);
}
while let Some(&(l, r)) = self
.ranges
.range((Excluded((start, start)), Excluded((end, end))))
.next()
{
if r < end {
self.ranges.remove(&(l, r));
} else {
break;
}
}
let &(ll, l) = self
.ranges
.range(..(start + 1, start + 1))
.next_back()
.unwrap();
let &(r, rr) = self.ranges.range((end, end)..).next().unwrap();
if ll <= start && end <= l {
return false;
}
match (start <= l + 1, r - 1 <= end) {
(false, false) => {
self.ranges.insert((start, end));
}
(false, true) => {
self.ranges.remove(&(r, rr));
self.ranges.insert((start, rr));
}
(true, false) => {
self.ranges.remove(&(ll, l));
self.ranges.insert((ll, end));
}
(true, true) => {
self.ranges.remove(&(ll, l));
self.ranges.remove(&(r, rr));
self.ranges.insert((ll, rr));
}
}
true
}
pub fn delete_range<R: RangeBounds<isize>>(&mut self, range: R) -> bool {
let (start, end) = Self::parse_range(range);
if start > end {
return false;
}
if (start, end) == (Self::INF, Self::SUP) {
let len = self.ranges.len();
self.ranges.clear();
self.ranges.insert((Self::INF, Self::INF));
self.ranges.insert((Self::SUP, Self::SUP));
return len != self.ranges.len();
}
if start == end {
return self.delete(start);
}
while let Some(&(l, r)) = self
.ranges
.range((Excluded((start, start)), Excluded((end, end))))
.next()
{
if r < end {
self.ranges.remove(&(l, r));
} else {
break;
}
}
let &(ll, l) = self
.ranges
.range((Unbounded, Included((start, start))))
.next_back()
.unwrap();
let &(r, rr) = self
.ranges
.range((Unbounded, Included((end, end))))
.next_back()
.unwrap();
if l < start && end < r {
return false;
}
if start <= l {
self.ranges.remove(&(ll, l));
match (ll < start, end < l) {
(false, false) => {}
(false, true) => {
self.ranges.insert((end.saturating_add(1), l));
}
(true, false) => {
self.ranges.insert((ll, start.saturating_sub(1)));
}
(true, true) => {
self.ranges.insert((ll, start.saturating_sub(1)));
self.ranges.insert((end.saturating_add(1), l));
}
}
}
if r <= end && end <= rr {
self.ranges.remove(&(r, rr));
self.ranges.insert((end.saturating_add(1), rr));
}
true
}
pub fn mex(&self, x: isize) -> isize {
let &(ll, l) = self.ranges.range(..(x + 1, x + 1)).next_back().unwrap();
if ll <= x && x <= l {
l + 1
} else {
x
}
}
pub fn mex_rev(&self, x: isize) -> isize {
let &(l, r) = self.ranges.range(..(x, isize::MAX)).next_back().unwrap();
if l <= x && x <= r {
l - 1
} else {
x
}
}
}