SplaySequence

competitive::data_structure::splay_tree::sequence

Struct SplaySequence 

Source 
pub struct SplaySequence<T, A = MemoryPool<Node<LazyAggElement<T>>>>
where
    T: LazyMapMonoid,
    A: Allocator<Node<LazyAggElement<T>>>,
{
    root: Root<LazyAggSplay<T>>,
    length: usize,
    alloc: ManuallyDrop<A>,
}

Fields§

§root: Root<LazyAggSplay<T>>§length: usize§alloc: ManuallyDrop<A>

Implementations§

Source§

impl<T> SplaySequence<T>
where T: LazyMapMonoid,

Source

pub fn new() -> Self

Source

pub fn with_capacity(capacity: usize) -> Self

Examples found in repository?
crates/library_checker/src/data_structure/dynamic_sequence_range_affine_range_sum.rs (line 13)
8pub fn dynamic_sequence_range_affine_range_sum(reader: impl Read, mut writer: impl Write) {
9    let s = read_all_unchecked(reader);
10    let mut scanner = Scanner::new(&s);
11    scan!(scanner, n, q, a: [MInt998244353; n]);
12
13    let mut seq = SplaySequence::<RangeSumRangeLinear<MInt998244353>>::with_capacity(n + q);
14    seq.extend(a);
15    for _ in 0..q {
16        match scanner.scan::<usize>() {
17            0 => {
18                scan!(scanner, i, x: MInt998244353);
19                seq.insert(i, x);
20            }
21            1 => {
22                scan!(scanner, i);
23                seq.remove(i);
24            }
25            2 => {
26                scan!(scanner, l, r);
27                seq.reverse(l..r);
28            }
29            3 => {
30                scan!(scanner, l, r, bc: (MInt998244353, MInt998244353));
31                seq.update(l..r, bc);
32            }
33            4 => {
34                scan!(scanner, l, r);
35                writeln!(writer, "{}", seq.fold(l..r).0).ok();
36            }
37            _ => unreachable!("unknown query"),
38        }
39    }
40}
Source

pub fn len(&self) -> usize

Source

pub fn is_empty(&self) -> bool

Source§

impl<T, A> SplaySequence<T, A>
where T: LazyMapMonoid, A: Allocator<Node<LazyAggElement<T>>>,

Source

fn range<R>(&mut self, range: R) -> NodeRange<'_, LazyAggSplay<T>>
where R: RangeBounds<usize>,

Examples found in repository?
crates/competitive/src/data_structure/splay_tree/sequence.rs (line 326)
322    pub fn update<R>(&mut self, range: R, x: T::Act)
323    where
324        R: RangeBounds<usize>,
325    {
326        if let Some(root) = self.range(range).root_mut().root_data_mut() {
327            LazyAggSplay::<T>::update_lazy(root, &x);
328        }
329    }
330    pub fn fold<R>(&mut self, range: R) -> T::Agg
331    where
332        R: RangeBounds<usize>,
333    {
334        if let Some(root) = self.range(range).root().root() {
335            root.data().agg.clone()
336        } else {
337            T::agg_unit()
338        }
339    }
340    pub fn reverse<R>(&mut self, range: R)
341    where
342        R: RangeBounds<usize>,
343    {
344        if let Some(root) = self.range(range).root_mut().root_data_mut() {
345            LazyAggSplay::<T>::reverse(root);
346        }
347    }
348    pub fn get(&mut self, index: usize) -> Option<&T::Key> {
349        self.root.splay_by(SeekBySize::new(index))?;
350        self.root.root().map(|root| &root.data().key)
351    }
352    pub fn modify<F>(&mut self, index: usize, f: F)
353    where
354        F: FnOnce(&T::Key) -> T::Key,
355    {
356        self.root.splay_by(SeekBySize::new(index)).unwrap();
357        let data = self.root.root_data_mut().unwrap().data_mut();
358        data.key = f(&data.key);
359        LazyAggSplay::<T>::bottom_up(self.root.root_data_mut().unwrap());
360    }
361    pub fn insert(&mut self, index: usize, x: T::Key) {
362        assert!(index <= self.length);
363        self.root.splay_by(SeekBySize::new(index));
364        let agg = T::single_agg(&x);
365        unsafe {
366            let node = NodeRef::from_data(
367                LazyAggElement {
368                    key: x,
369                    agg,
370                    lazy: T::act_unit(),
371                    size: 1,
372                    rev: false,
373                },
374                self.alloc.deref_mut(),
375            );
376            if index == self.length {
377                self.root.insert_right(node);
378            } else {
379                self.root.insert_left(node);
380            }
381        }
382        self.length += 1;
383    }
384    pub fn remove(&mut self, index: usize) -> Option<T::Key> {
385        if index >= self.length {
386            return None;
387        }
388        self.root.splay_by(SeekBySize::new(index));
389        self.length -= 1;
390        let node = self.root.take_root().unwrap().into_dying();
391        unsafe { Some(node.into_data(self.alloc.deref_mut()).key) }
392    }
393    pub fn position_acc<R, F>(&mut self, range: R, f: F) -> Option<usize>
394    where
395        R: RangeBounds<usize>,
396        F: FnMut(&T::Agg) -> bool,
397    {
398        let mut range = self.range(range);
399        let ord = range.root_mut().splay_by(SeekByAccCond::new(f));
400        if !matches!(ord, Some(Ordering::Equal)) {
401            return None;
402        }
403        let front_size = range.front().size();
404        let left_size = range.root().left_size();
405        Some(front_size + left_size)
406    }
407    pub fn rposition_acc<R, F>(&mut self, range: R, f: F) -> Option<usize>
408    where
409        R: RangeBounds<usize>,
410        F: FnMut(&T::Agg) -> bool,
411    {
412        let mut range = self.range(range);
413        let ord = range.root_mut().splay_by(SeekByRaccCond::new(f));
414        if !matches!(ord, Some(Ordering::Equal)) {
415            return None;
416        }
417        let front_size = range.front().size();
418        let left_size = range.root().left_size();
419        Some(front_size + left_size)
420    }
421    pub fn rotate_left(&mut self, mid: usize) {
422        assert!(mid <= self.length);
423        if mid != 0 || mid != self.length {
424            self.range(mid..).drop_rotate_left()
425        }
426    }
Source

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 31)
8pub fn dynamic_sequence_range_affine_range_sum(reader: impl Read, mut writer: impl Write) {
9    let s = read_all_unchecked(reader);
10    let mut scanner = Scanner::new(&s);
11    scan!(scanner, n, q, a: [MInt998244353; n]);
12
13    let mut seq = SplaySequence::<RangeSumRangeLinear<MInt998244353>>::with_capacity(n + q);
14    seq.extend(a);
15    for _ in 0..q {
16        match scanner.scan::<usize>() {
17            0 => {
18                scan!(scanner, i, x: MInt998244353);
19                seq.insert(i, x);
20            }
21            1 => {
22                scan!(scanner, i);
23                seq.remove(i);
24            }
25            2 => {
26                scan!(scanner, l, r);
27                seq.reverse(l..r);
28            }
29            3 => {
30                scan!(scanner, l, r, bc: (MInt998244353, MInt998244353));
31                seq.update(l..r, bc);
32            }
33            4 => {
34                scan!(scanner, l, r);
35                writeln!(writer, "{}", seq.fold(l..r).0).ok();
36            }
37            _ => unreachable!("unknown query"),
38        }
39    }
40}
Source

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

Examples found in repository?
crates/library_checker/src/data_structure/dynamic_sequence_range_affine_range_sum.rs (line 35)
8pub fn dynamic_sequence_range_affine_range_sum(reader: impl Read, mut writer: impl Write) {
9    let s = read_all_unchecked(reader);
10    let mut scanner = Scanner::new(&s);
11    scan!(scanner, n, q, a: [MInt998244353; n]);
12
13    let mut seq = SplaySequence::<RangeSumRangeLinear<MInt998244353>>::with_capacity(n + q);
14    seq.extend(a);
15    for _ in 0..q {
16        match scanner.scan::<usize>() {
17            0 => {
18                scan!(scanner, i, x: MInt998244353);
19                seq.insert(i, x);
20            }
21            1 => {
22                scan!(scanner, i);
23                seq.remove(i);
24            }
25            2 => {
26                scan!(scanner, l, r);
27                seq.reverse(l..r);
28            }
29            3 => {
30                scan!(scanner, l, r, bc: (MInt998244353, MInt998244353));
31                seq.update(l..r, bc);
32            }
33            4 => {
34                scan!(scanner, l, r);
35                writeln!(writer, "{}", seq.fold(l..r).0).ok();
36            }
37            _ => unreachable!("unknown query"),
38        }
39    }
40}
Source

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

Examples found in repository?
crates/library_checker/src/data_structure/dynamic_sequence_range_affine_range_sum.rs (line 27)
8pub fn dynamic_sequence_range_affine_range_sum(reader: impl Read, mut writer: impl Write) {
9    let s = read_all_unchecked(reader);
10    let mut scanner = Scanner::new(&s);
11    scan!(scanner, n, q, a: [MInt998244353; n]);
12
13    let mut seq = SplaySequence::<RangeSumRangeLinear<MInt998244353>>::with_capacity(n + q);
14    seq.extend(a);
15    for _ in 0..q {
16        match scanner.scan::<usize>() {
17            0 => {
18                scan!(scanner, i, x: MInt998244353);
19                seq.insert(i, x);
20            }
21            1 => {
22                scan!(scanner, i);
23                seq.remove(i);
24            }
25            2 => {
26                scan!(scanner, l, r);
27                seq.reverse(l..r);
28            }
29            3 => {
30                scan!(scanner, l, r, bc: (MInt998244353, MInt998244353));
31                seq.update(l..r, bc);
32            }
33            4 => {
34                scan!(scanner, l, r);
35                writeln!(writer, "{}", seq.fold(l..r).0).ok();
36            }
37            _ => unreachable!("unknown query"),
38        }
39    }
40}
Source

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

Source

pub fn modify<F>(&mut self, index: usize, f: F)
where F: FnOnce(&T::Key) -> T::Key,

Source

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 19)
8pub fn dynamic_sequence_range_affine_range_sum(reader: impl Read, mut writer: impl Write) {
9    let s = read_all_unchecked(reader);
10    let mut scanner = Scanner::new(&s);
11    scan!(scanner, n, q, a: [MInt998244353; n]);
12
13    let mut seq = SplaySequence::<RangeSumRangeLinear<MInt998244353>>::with_capacity(n + q);
14    seq.extend(a);
15    for _ in 0..q {
16        match scanner.scan::<usize>() {
17            0 => {
18                scan!(scanner, i, x: MInt998244353);
19                seq.insert(i, x);
20            }
21            1 => {
22                scan!(scanner, i);
23                seq.remove(i);
24            }
25            2 => {
26                scan!(scanner, l, r);
27                seq.reverse(l..r);
28            }
29            3 => {
30                scan!(scanner, l, r, bc: (MInt998244353, MInt998244353));
31                seq.update(l..r, bc);
32            }
33            4 => {
34                scan!(scanner, l, r);
35                writeln!(writer, "{}", seq.fold(l..r).0).ok();
36            }
37            _ => unreachable!("unknown query"),
38        }
39    }
40}
Source

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 23)
8pub fn dynamic_sequence_range_affine_range_sum(reader: impl Read, mut writer: impl Write) {
9    let s = read_all_unchecked(reader);
10    let mut scanner = Scanner::new(&s);
11    scan!(scanner, n, q, a: [MInt998244353; n]);
12
13    let mut seq = SplaySequence::<RangeSumRangeLinear<MInt998244353>>::with_capacity(n + q);
14    seq.extend(a);
15    for _ in 0..q {
16        match scanner.scan::<usize>() {
17            0 => {
18                scan!(scanner, i, x: MInt998244353);
19                seq.insert(i, x);
20            }
21            1 => {
22                scan!(scanner, i);
23                seq.remove(i);
24            }
25            2 => {
26                scan!(scanner, l, r);
27                seq.reverse(l..r);
28            }
29            3 => {
30                scan!(scanner, l, r, bc: (MInt998244353, MInt998244353));
31                seq.update(l..r, bc);
32            }
33            4 => {
34                scan!(scanner, l, r);
35                writeln!(writer, "{}", seq.fold(l..r).0).ok();
36            }
37            _ => unreachable!("unknown query"),
38        }
39    }
40}
Source

pub fn position_acc<R, F>(&mut self, range: R, f: F) -> Option<usize>
where R: RangeBounds<usize>, F: FnMut(&T::Agg) -> bool,

Source

pub fn rposition_acc<R, F>(&mut self, range: R, f: F) -> Option<usize>
where R: RangeBounds<usize>, F: FnMut(&T::Agg) -> bool,

Source

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

Examples found in repository?
crates/competitive/src/data_structure/splay_tree/sequence.rs (line 429)
427    pub fn rotate_right(&mut self, k: usize) {
428        assert!(k <= self.length);
429        self.rotate_left(self.length - k);
430    }
Source

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

Trait Implementations§

Source§

impl<T, A> Debug for SplaySequence<T, A>
where T: LazyMapMonoid<Key: Debug, Agg: Debug, Act: Debug>, A: Allocator<Node<LazyAggElement<T>>>,

Source§

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter. Read more
Source§

impl<T, A> Default for SplaySequence<T, A>
where T: LazyMapMonoid, A: Allocator<Node<LazyAggElement<T>>> + Default,

Source§

fn default() -> Self

Returns the “default value” for a type. Read more
Source§

impl<T, A> Drop for SplaySequence<T, A>
where T: LazyMapMonoid, A: Allocator<Node<LazyAggElement<T>>>,

Source§

fn drop(&mut self)

Executes the destructor for this type. Read more
Source§

impl<T, A> Extend<<T as LazyMapMonoid>::Key> for SplaySequence<T, A>
where T: LazyMapMonoid, A: Allocator<Node<LazyAggElement<T>>>,

Source§

fn extend<I>(&mut self, iter: I)
where I: IntoIterator<Item = T::Key>,

Extends a collection with the contents of an iterator. Read more
Source§

fn extend_one(&mut self, item: A)

🔬This is a nightly-only experimental API. (extend_one)
Extends a collection with exactly one element.
Source§

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. Read more

Auto Trait Implementations§

§

impl<T, A> Freeze for SplaySequence<T, A>
where A: Freeze,

§

impl<T, A> RefUnwindSafe for SplaySequence<T, A>
where A: RefUnwindSafe, <T as LazyMapMonoid>::Key: RefUnwindSafe, <T as LazyMapMonoid>::Agg: RefUnwindSafe, <T as LazyMapMonoid>::Act: RefUnwindSafe,

§

impl<T, A = MemoryPool<Node<LazyAggElement<T>>>> !Send for SplaySequence<T, A>

§

impl<T, A = MemoryPool<Node<LazyAggElement<T>>>> !Sync for SplaySequence<T, A>

§

impl<T, A> Unpin for SplaySequence<T, A>
where A: Unpin,

§

impl<T, A> UnwindSafe for SplaySequence<T, A>
where A: UnwindSafe, <T as LazyMapMonoid>::Key: RefUnwindSafe, <T as LazyMapMonoid>::Agg: RefUnwindSafe, <T as LazyMapMonoid>::Act: RefUnwindSafe,

Blanket Implementations§

Source§

impl<T> Any for T
where T: 'static + ?Sized,

Source§

fn type_id(&self) -> TypeId

Gets the TypeId of self. Read more
Source§

impl<T> Borrow<T> for T
where T: ?Sized,

Source§

fn borrow(&self) -> &T

Immutably borrows from an owned value. Read more
Source§

impl<T> BorrowMut<T> for T
where T: ?Sized,

Source§

fn borrow_mut(&mut self) -> &mut T

Mutably borrows from an owned value. Read more
Source§

impl<T> From<T> for T

Source§

fn from(t: T) -> T

Returns the argument unchanged.

Source§

impl<T, U> Into<U> for T
where U: From<T>,

Source§

fn into(self) -> U

Calls U::from(self).

That is, this conversion is whatever the implementation of From<T> for U chooses to do.

Source§

impl<T, U> TryFrom<U> for T
where U: Into<T>,

Source§

type Error = Infallible

The type returned in the event of a conversion error.
Source§

fn try_from(value: U) -> Result<T, <T as TryFrom<U>>::Error>

Performs the conversion.
Source§

impl<T, U> TryInto<U> for T
where U: TryFrom<T>,

Source§

type Error = <U as TryFrom<T>>::Error

The type returned in the event of a conversion error.
Source§

fn try_into(self) -> Result<U, <U as TryFrom<T>>::Error>

Performs the conversion.