Struct ImplicitTreap 

pub struct ImplicitTreap<T, A = MemoryPool<BstNode<ImplicitTreapData<T>>>>
where
    T: LazyMapMonoid,
    A: Allocator<BstNode<ImplicitTreapData<T>>>,
{
    root: Option<BstRoot<ImplicitTreapSpec<T>>>,
    length: usize,
    rng: Xorshift,
    allocator: ManuallyDrop<A>,
    _marker: PhantomData<fn() -> T>,
}

Fields

root: Option<BstRoot<ImplicitTreapSpec<T>>>

length: usize

rng: Xorshift

allocator: ManuallyDrop<A>

_marker: PhantomData<fn() -> T>

Implementations

impl<T> ImplicitTreap<T>

where T: LazyMapMonoid,

pub fn new() -> Self

pub fn with_capacity(capacity: usize) -> Self

Examples found in repository

crates/library_checker/src/data_structure/range_reverse_range_sum.rs (line 18)

pub fn range_reverse_range_sum(reader: impl Read, writer: impl Write) {
    prepare_io!(reader, writer);
    sc!(n, q, a: [i64; iter n]);
    let mut seq = ImplicitTreap::<RangeSumRangeAdd<i64>>::with_capacity(n);
    seq.extend(a);
    for _ in 0..q {
        sc!(query: Query);
        match query {
            Query::Reverse { l, r } => {
                seq.reverse(l..r);
            }
            Query::Sum { l, r } => {
                let ans = seq.fold(l..r).0;
                pp!(ans);
            }
        }
    }
}

crates/library_checker/src/data_structure/dynamic_sequence_range_affine_range_sum.rs (line 23)

pub fn dynamic_sequence_range_affine_range_sum(reader: impl Read, writer: impl Write) {
    prepare_io!(reader, writer);
    sc!(n, q, a: [M; iter n]);

    let mut seq = ImplicitTreap::<RangeSumRangeLinear<M>>::with_capacity(n + q);
    seq.extend(a);
    for _ in 0..q {
        sc!(query: Query);
        match query {
            Query::Insert { i, x } => {
                seq.insert(i, x);
            }
            Query::Remove { i } => {
                seq.remove(i);
            }
            Query::Reverse { l, r } => {
                seq.reverse(l..r);
            }
            Query::Update { l, r, bc } => {
                seq.update(l..r, bc);
            }
            Query::Fold { l, r } => {
                pp!(seq.fold(l..r).0);
            }
        }
    }
}

impl<T, A> ImplicitTreap<T, A>

where T: LazyMapMonoid, A: Allocator<BstNode<ImplicitTreapData<T>>>,

fn node(&mut self, key: T::Key) -> BstRoot<ImplicitTreapSpec<T>>

Examples found in repository

crates/competitive/src/data_structure/implicit_treap.rs (line 303)

    fn build<I>(&mut self, iter: I) -> (Option<ImplicitTreapRoot<T>>, usize)
    where
        I: IntoIterator<Item = T::Key>,
    {
        let mut stack = vec![];
        let mut len = 0;
        for key in iter {
            let mut cur = self.node(key).node;
            let mut left = None;
            unsafe {
                while stack
                    .last()
                    .is_some_and(|node: &NonNull<ImplicitTreapNode<T>>| {
                        node.as_ref().data.priority < cur.as_ref().data.priority
                    })
                {
                    left = stack.pop();
                }
                cur.as_mut().child[0] = left;
                if let Some(parent) = stack.last_mut() {
                    parent.as_mut().child[1] = Some(cur);
                }
            }
            stack.push(cur);
            len += 1;
        }
        let root = stack.first().copied().map(BstRoot::new);
        if let Some(mut root) = root {
            Self::build_bottom_up(root.borrow_datamut());
            (Some(root), len)
        } else {
            (None, len)
        }
    }

    fn build_bottom_up(mut node: BstDataMutRef<'_, ImplicitTreapSpec<T>>) {
        if let Ok(left) = node.reborrow_datamut().left().descend() {
            Self::build_bottom_up(left);
        }
        if let Ok(right) = node.reborrow_datamut().right().descend() {
            Self::build_bottom_up(right);
        }
        ImplicitTreapSpec::<T>::bottom_up(node);
    }

    pub fn len(&self) -> usize {
        self.length
    }

    pub fn is_empty(&self) -> bool {
        self.length == 0
    }

    pub fn update<R>(&mut self, range: R, x: T::Act)
    where
        R: RangeBounds<usize>,
    {
        let mut split = Split3::seek_by_size(&mut self.root, range);
        if let Some(root) = split.mid_datamut() {
            ImplicitTreapSpec::<T>::update_act(root, &x);
        }
    }

    pub fn fold<R>(&mut self, range: R) -> T::Agg
    where
        R: RangeBounds<usize>,
    {
        let split = Split3::seek_by_size(&mut self.root, range);
        split
            .mid()
            .map(|node| node.into_data().value.agg.clone())
            .unwrap_or_else(T::agg_unit)
    }

    pub fn reverse<R>(&mut self, range: R)
    where
        R: RangeBounds<usize>,
    {
        let mut split = Split3::seek_by_size(&mut self.root, range);
        if let Some(root) = split.mid_datamut() {
            ImplicitTreapSpec::<T>::reverse(root);
        }
    }

    pub fn get(&mut self, index: usize) -> Option<&T::Key> {
        if index >= self.length {
            return None;
        }
        let split = Split3::seek_by_size(&mut self.root, index..=index);
        let node = split.mid()?.node;
        drop(split);
        Some(unsafe { &(*node.as_ptr()).data.value.key })
    }

    pub fn modify<F>(&mut self, index: usize, f: F)
    where
        F: FnOnce(&T::Key) -> T::Key,
    {
        assert!(index < self.length);
        let mut split = Split3::seek_by_size(&mut self.root, index..=index);
        let mut node = split.mid_datamut().unwrap();
        ImplicitTreapSpec::<T>::top_down(node.reborrow_datamut());
        {
            let data = node.data_mut();
            data.value.key = f(&data.value.key);
        }
        ImplicitTreapSpec::<T>::bottom_up(node);
    }

    pub fn insert(&mut self, index: usize, x: T::Key) {
        assert!(index <= self.length);
        let node = self.node(x);
        if index == 0 {
            self.root = ImplicitTreapSpec::<T>::merge(Some(node), self.root.take());
        } else if index == self.length {
            self.root = ImplicitTreapSpec::<T>::merge(self.root.take(), Some(node));
        } else {
            let mut node = Some(node);
            let mut split = Split::new(&mut self.root, SeekBySize::new(index), EqualSide::Right);
            split.manually_merge(|left, right| {
                ImplicitTreapSpec::<T>::merge(
                    ImplicitTreapSpec::<T>::merge(left, node.take()),
                    right,
                )
            });
        }
        self.length += 1;
    }

fn build<I>( &mut self, iter: I, ) -> (Option<BstRoot<ImplicitTreapSpec<T>>>, usize)

where I: IntoIterator<Item = T::Key>,

Examples found in repository

crates/competitive/src/data_structure/implicit_treap.rs (line 518)

    fn extend<I>(&mut self, iter: I)
    where
        I: IntoIterator<Item = T::Key>,
    {
        let (root, len) = self.build(iter);
        self.root = ImplicitTreapSpec::<T>::merge(self.root.take(), root);
        self.length += len;
    }

fn build_bottom_up(node: BstDataMutRef<'_, ImplicitTreapSpec<T>>)

Examples found in repository

crates/competitive/src/data_structure/implicit_treap.rs (line 324)

    fn build<I>(&mut self, iter: I) -> (Option<ImplicitTreapRoot<T>>, usize)
    where
        I: IntoIterator<Item = T::Key>,
    {
        let mut stack = vec![];
        let mut len = 0;
        for key in iter {
            let mut cur = self.node(key).node;
            let mut left = None;
            unsafe {
                while stack
                    .last()
                    .is_some_and(|node: &NonNull<ImplicitTreapNode<T>>| {
                        node.as_ref().data.priority < cur.as_ref().data.priority
                    })
                {
                    left = stack.pop();
                }
                cur.as_mut().child[0] = left;
                if let Some(parent) = stack.last_mut() {
                    parent.as_mut().child[1] = Some(cur);
                }
            }
            stack.push(cur);
            len += 1;
        }
        let root = stack.first().copied().map(BstRoot::new);
        if let Some(mut root) = root {
            Self::build_bottom_up(root.borrow_datamut());
            (Some(root), len)
        } else {
            (None, len)
        }
    }

    fn build_bottom_up(mut node: BstDataMutRef<'_, ImplicitTreapSpec<T>>) {
        if let Ok(left) = node.reborrow_datamut().left().descend() {
            Self::build_bottom_up(left);
        }
        if let Ok(right) = node.reborrow_datamut().right().descend() {
            Self::build_bottom_up(right);
        }
        ImplicitTreapSpec::<T>::bottom_up(node);
    }

pub fn len(&self) -> usize

pub fn is_empty(&self) -> bool

pub fn update<R>(&mut self, range: R, x: T::Act)

where R: RangeBounds<usize>,

Examples found in repository

crates/library_checker/src/data_structure/dynamic_sequence_range_affine_range_sum.rs (line 38)

pub fn dynamic_sequence_range_affine_range_sum(reader: impl Read, writer: impl Write) {
    prepare_io!(reader, writer);
    sc!(n, q, a: [M; iter n]);

    let mut seq = ImplicitTreap::<RangeSumRangeLinear<M>>::with_capacity(n + q);
    seq.extend(a);
    for _ in 0..q {
        sc!(query: Query);
        match query {
            Query::Insert { i, x } => {
                seq.insert(i, x);
            }
            Query::Remove { i } => {
                seq.remove(i);
            }
            Query::Reverse { l, r } => {
                seq.reverse(l..r);
            }
            Query::Update { l, r, bc } => {
                seq.update(l..r, bc);
            }
            Query::Fold { l, r } => {
                pp!(seq.fold(l..r).0);
            }
        }
    }
}

pub fn fold<R>(&mut self, range: R) -> T::Agg

where R: RangeBounds<usize>,

Examples found in repository

crates/library_checker/src/data_structure/range_reverse_range_sum.rs (line 27)

pub fn range_reverse_range_sum(reader: impl Read, writer: impl Write) {
    prepare_io!(reader, writer);
    sc!(n, q, a: [i64; iter n]);
    let mut seq = ImplicitTreap::<RangeSumRangeAdd<i64>>::with_capacity(n);
    seq.extend(a);
    for _ in 0..q {
        sc!(query: Query);
        match query {
            Query::Reverse { l, r } => {
                seq.reverse(l..r);
            }
            Query::Sum { l, r } => {
                let ans = seq.fold(l..r).0;
                pp!(ans);
            }
        }
    }
}

crates/library_checker/src/data_structure/dynamic_sequence_range_affine_range_sum.rs (line 41)

pub fn dynamic_sequence_range_affine_range_sum(reader: impl Read, writer: impl Write) {
    prepare_io!(reader, writer);
    sc!(n, q, a: [M; iter n]);

    let mut seq = ImplicitTreap::<RangeSumRangeLinear<M>>::with_capacity(n + q);
    seq.extend(a);
    for _ in 0..q {
        sc!(query: Query);
        match query {
            Query::Insert { i, x } => {
                seq.insert(i, x);
            }
            Query::Remove { i } => {
                seq.remove(i);
            }
            Query::Reverse { l, r } => {
                seq.reverse(l..r);
            }
            Query::Update { l, r, bc } => {
                seq.update(l..r, bc);
            }
            Query::Fold { l, r } => {
                pp!(seq.fold(l..r).0);
            }
        }
    }
}

pub fn reverse<R>(&mut self, range: R)

where R: RangeBounds<usize>,

Examples found in repository

crates/library_checker/src/data_structure/range_reverse_range_sum.rs (line 24)

pub fn range_reverse_range_sum(reader: impl Read, writer: impl Write) {
    prepare_io!(reader, writer);
    sc!(n, q, a: [i64; iter n]);
    let mut seq = ImplicitTreap::<RangeSumRangeAdd<i64>>::with_capacity(n);
    seq.extend(a);
    for _ in 0..q {
        sc!(query: Query);
        match query {
            Query::Reverse { l, r } => {
                seq.reverse(l..r);
            }
            Query::Sum { l, r } => {
                let ans = seq.fold(l..r).0;
                pp!(ans);
            }
        }
    }
}

crates/library_checker/src/data_structure/dynamic_sequence_range_affine_range_sum.rs (line 35)

pub fn dynamic_sequence_range_affine_range_sum(reader: impl Read, writer: impl Write) {
    prepare_io!(reader, writer);
    sc!(n, q, a: [M; iter n]);

    let mut seq = ImplicitTreap::<RangeSumRangeLinear<M>>::with_capacity(n + q);
    seq.extend(a);
    for _ in 0..q {
        sc!(query: Query);
        match query {
            Query::Insert { i, x } => {
                seq.insert(i, x);
            }
            Query::Remove { i } => {
                seq.remove(i);
            }
            Query::Reverse { l, r } => {
                seq.reverse(l..r);
            }
            Query::Update { l, r, bc } => {
                seq.update(l..r, bc);
            }
            Query::Fold { l, r } => {
                pp!(seq.fold(l..r).0);
            }
        }
    }
}

pub fn get(&mut self, index: usize) -> Option<&T::Key>

pub fn modify<F>(&mut self, index: usize, f: F)

where F: FnOnce(&T::Key) -> T::Key,

pub fn insert(&mut self, index: usize, x: T::Key)

Examples found in repository

crates/library_checker/src/data_structure/dynamic_sequence_range_affine_range_sum.rs (line 29)

pub fn dynamic_sequence_range_affine_range_sum(reader: impl Read, writer: impl Write) {
    prepare_io!(reader, writer);
    sc!(n, q, a: [M; iter n]);

    let mut seq = ImplicitTreap::<RangeSumRangeLinear<M>>::with_capacity(n + q);
    seq.extend(a);
    for _ in 0..q {
        sc!(query: Query);
        match query {
            Query::Insert { i, x } => {
                seq.insert(i, x);
            }
            Query::Remove { i } => {
                seq.remove(i);
            }
            Query::Reverse { l, r } => {
                seq.reverse(l..r);
            }
            Query::Update { l, r, bc } => {
                seq.update(l..r, bc);
            }
            Query::Fold { l, r } => {
                pp!(seq.fold(l..r).0);
            }
        }
    }
}

pub fn remove(&mut self, index: usize) -> Option<T::Key>

Examples found in repository

crates/library_checker/src/data_structure/dynamic_sequence_range_affine_range_sum.rs (line 32)

pub fn dynamic_sequence_range_affine_range_sum(reader: impl Read, writer: impl Write) {
    prepare_io!(reader, writer);
    sc!(n, q, a: [M; iter n]);

    let mut seq = ImplicitTreap::<RangeSumRangeLinear<M>>::with_capacity(n + q);
    seq.extend(a);
    for _ in 0..q {
        sc!(query: Query);
        match query {
            Query::Insert { i, x } => {
                seq.insert(i, x);
            }
            Query::Remove { i } => {
                seq.remove(i);
            }
            Query::Reverse { l, r } => {
                seq.reverse(l..r);
            }
            Query::Update { l, r, bc } => {
                seq.update(l..r, bc);
            }
            Query::Fold { l, r } => {
                pp!(seq.fold(l..r).0);
            }
        }
    }
}

pub fn partition_point_acc<F>(&mut self, left: usize, pred: F) -> usize

where F: FnMut(&T::Agg) -> bool,

pub fn rpartition_point_acc<F>(&mut self, right: usize, pred: F) -> usize

where F: FnMut(&T::Agg) -> bool,

pub fn rotate_left(&mut self, mid: usize)

Examples found in repository

crates/competitive/src/data_structure/implicit_treap.rs (line 505)

    pub fn rotate_right(&mut self, k: usize) {
        assert!(k <= self.length);
        self.rotate_left(self.length - k);
    }

pub fn rotate_right(&mut self, k: usize)

Trait Implementations

impl<T, A> Default for ImplicitTreap<T, A>

where T: LazyMapMonoid, A: Allocator<BstNode<ImplicitTreapData<T>>> + Default,

fn default() -> Self

Returns the “default value” for a type.

impl<T, A> Drop for ImplicitTreap<T, A>

where T: LazyMapMonoid, A: Allocator<BstNode<ImplicitTreapData<T>>>,

fn drop(&mut self)

Executes the destructor for this type.

fn pin_drop(self: Pin<&mut Self>)

🔬This is a nightly-only experimental API. (pin_ergonomics)

Execute the destructor for this type, but different to Drop::drop, it requires self to be pinned.

impl<T, A> Extend<<T as LazyMapMonoid>::Key> for ImplicitTreap<T, A>

where T: LazyMapMonoid, A: Allocator<BstNode<ImplicitTreapData<T>>>,

fn extend<I>(&mut self, iter: I)

where I: IntoIterator<Item = T::Key>,

Extends a collection with the contents of an iterator.

fn extend_one(&mut self, item: T)

🔬This is a nightly-only experimental API. (extend_one)

Extends a collection with exactly one element.

fn extend_reserve(&mut self, additional: usize)

🔬This is a nightly-only experimental API. (extend_one)

Reserves capacity in a collection for the given number of additional elements.