competitive::data_structure::splay_tree::sequence

Struct SplaySequence

Source 
pub struct SplaySequence<T, A = MemoryPool<Node<LazyAggElement<T>>>>
where
    T: MonoidAction,
    A: Allocator<Node<LazyAggElement<T>>>,
{ /* private fields */ }

Implementations§

Source§

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

Source

pub fn new() -> Self

Source

pub fn with_capacity(capacity: usize) -> Self

Examples found in repository?
crates/library_checker/src/datastructure/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            _ => panic!("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: MonoidAction, A: Allocator<Node<LazyAggElement<T>>>,

Source

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

Examples found in repository?
crates/library_checker/src/datastructure/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            _ => panic!("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/datastructure/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            _ => panic!("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/datastructure/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            _ => panic!("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/datastructure/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            _ => panic!("unknown query"),
38        }
39    }
40}
Source

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

Examples found in repository?
crates/library_checker/src/datastructure/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            _ => panic!("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 435)
433    pub fn rotate_right(&mut self, k: usize) {
434        assert!(k <= self.length);
435        self.rotate_left(self.length - k);
436    }
Source

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

Trait Implementations§

Source§

impl<T, A> Debug for SplaySequence<T, A>
where T: MonoidAction, T::Key: Debug, T::Agg: Debug, T::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: MonoidAction, 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: MonoidAction, 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 MonoidAction>::Key> for SplaySequence<T, A>
where T: MonoidAction, 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 MonoidAction>::Key: RefUnwindSafe, <T as MonoidAction>::Agg: RefUnwindSafe, <T as MonoidAction>::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 MonoidAction>::Key: RefUnwindSafe, <T as MonoidAction>::Agg: RefUnwindSafe, <T as MonoidAction>::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.