Struct DequeAggregation

Source

pub struct DequeAggregation<M>where
    M: Monoid,{
    front_stack: Vec<(M::T, M::T)>,
    back_stack: Vec<(M::T, M::T)>,
}

Fields§

§front_stack: Vec<(M::T, M::T)>§back_stack: Vec<(M::T, M::T)>

Implementations§

Source §

impl<M> DequeAggregation<M>
where M: Monoid,

Source

pub fn new() -> Self

Examples found in repository ?

crates/library_checker/src/data_structure/deque_operate_all_composite.rs (line 14)

10pub fn deque_operate_all_composite(reader: impl Read, mut writer: impl Write) {
11    let s = read_all_unchecked(reader);
12    let mut scanner = Scanner::new(&s);
13    scan!(scanner, q);
14    let mut deq = DequeAggregation::<LinearOperation<_>>::new();
15    for _ in 0..q {
16        match scanner.scan::<usize>() {
17            0 => {
18                scan!(scanner, ab: (MInt998244353, MInt998244353));
19                deq.push_front(ab);
20            }
21            1 => {
22                scan!(scanner, ab: (MInt998244353, MInt998244353));
23                deq.push_back(ab);
24            }
25            2 => {
26                deq.pop_front();
27            }
28            3 => {
29                deq.pop_back();
30            }
31            4 => {
32                scan!(scanner, x: MInt998244353);
33                let (a, b) = deq.fold_all();
34                writeln!(writer, "{}", a * x + b).ok();
35            }
36            _ => unreachable!("unknown query"),
37        }
38    }
39}

Source

pub fn len(&self) -> usize

Source

pub fn is_empty(&self) -> bool

Source

pub fn fold_all(&self) -> M::T

Examples found in repository ?

crates/library_checker/src/data_structure/deque_operate_all_composite.rs (line 33)

10pub fn deque_operate_all_composite(reader: impl Read, mut writer: impl Write) {
11    let s = read_all_unchecked(reader);
12    let mut scanner = Scanner::new(&s);
13    scan!(scanner, q);
14    let mut deq = DequeAggregation::<LinearOperation<_>>::new();
15    for _ in 0..q {
16        match scanner.scan::<usize>() {
17            0 => {
18                scan!(scanner, ab: (MInt998244353, MInt998244353));
19                deq.push_front(ab);
20            }
21            1 => {
22                scan!(scanner, ab: (MInt998244353, MInt998244353));
23                deq.push_back(ab);
24            }
25            2 => {
26                deq.pop_front();
27            }
28            3 => {
29                deq.pop_back();
30            }
31            4 => {
32                scan!(scanner, x: MInt998244353);
33                let (a, b) = deq.fold_all();
34                writeln!(writer, "{}", a * x + b).ok();
35            }
36            _ => unreachable!("unknown query"),
37        }
38    }
39}

Source

pub fn front(&self) -> Option<&M::T>

Source

pub fn back(&self) -> Option<&M::T>

Source

pub fn push_front(&mut self, value: M::T)

Examples found in repository ?

crates/competitive/src/data_structure/sliding_window_aggregation.rs (line 192)

187    pub fn pop_front(&mut self) -> Option<M::T> {
188        if self.front_stack.is_empty() {
189            let n = self.back_stack.len();
190            let mut back_stack = std::mem::take(&mut self.back_stack);
191            for x in back_stack.drain(..n.div_ceil(2)).map(|t| t.1).rev() {
192                self.push_front(x);
193            }
194            for x in back_stack.drain(..).map(|t| t.1) {
195                self.push_back(x);
196            }
197        }
198        self.front_stack.pop().map(|t| t.1)
199    }
200    pub fn pop_back(&mut self) -> Option<M::T> {
201        if self.back_stack.is_empty() {
202            let n = self.front_stack.len();
203            let mut front_stack = std::mem::take(&mut self.front_stack);
204            for x in front_stack.drain(..n.div_ceil(2)).map(|t| t.1).rev() {
205                self.push_back(x);
206            }
207            for x in front_stack.drain(..).map(|t| t.1) {
208                self.push_front(x);
209            }
210        }
211        self.back_stack.pop().map(|t| t.1)
212    }

More examples

Hide additional examples

crates/library_checker/src/data_structure/deque_operate_all_composite.rs (line 19)

10pub fn deque_operate_all_composite(reader: impl Read, mut writer: impl Write) {
11    let s = read_all_unchecked(reader);
12    let mut scanner = Scanner::new(&s);
13    scan!(scanner, q);
14    let mut deq = DequeAggregation::<LinearOperation<_>>::new();
15    for _ in 0..q {
16        match scanner.scan::<usize>() {
17            0 => {
18                scan!(scanner, ab: (MInt998244353, MInt998244353));
19                deq.push_front(ab);
20            }
21            1 => {
22                scan!(scanner, ab: (MInt998244353, MInt998244353));
23                deq.push_back(ab);
24            }
25            2 => {
26                deq.pop_front();
27            }
28            3 => {
29                deq.pop_back();
30            }
31            4 => {
32                scan!(scanner, x: MInt998244353);
33                let (a, b) = deq.fold_all();
34                writeln!(writer, "{}", a * x + b).ok();
35            }
36            _ => unreachable!("unknown query"),
37        }
38    }
39}

Source

pub fn push_back(&mut self, value: M::T)

Examples found in repository ?

crates/competitive/src/data_structure/sliding_window_aggregation.rs (line 195)

187    pub fn pop_front(&mut self) -> Option<M::T> {
188        if self.front_stack.is_empty() {
189            let n = self.back_stack.len();
190            let mut back_stack = std::mem::take(&mut self.back_stack);
191            for x in back_stack.drain(..n.div_ceil(2)).map(|t| t.1).rev() {
192                self.push_front(x);
193            }
194            for x in back_stack.drain(..).map(|t| t.1) {
195                self.push_back(x);
196            }
197        }
198        self.front_stack.pop().map(|t| t.1)
199    }
200    pub fn pop_back(&mut self) -> Option<M::T> {
201        if self.back_stack.is_empty() {
202            let n = self.front_stack.len();
203            let mut front_stack = std::mem::take(&mut self.front_stack);
204            for x in front_stack.drain(..n.div_ceil(2)).map(|t| t.1).rev() {
205                self.push_back(x);
206            }
207            for x in front_stack.drain(..).map(|t| t.1) {
208                self.push_front(x);
209            }
210        }
211        self.back_stack.pop().map(|t| t.1)
212    }

More examples

Hide additional examples

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

10pub fn deque_operate_all_composite(reader: impl Read, mut writer: impl Write) {
11    let s = read_all_unchecked(reader);
12    let mut scanner = Scanner::new(&s);
13    scan!(scanner, q);
14    let mut deq = DequeAggregation::<LinearOperation<_>>::new();
15    for _ in 0..q {
16        match scanner.scan::<usize>() {
17            0 => {
18                scan!(scanner, ab: (MInt998244353, MInt998244353));
19                deq.push_front(ab);
20            }
21            1 => {
22                scan!(scanner, ab: (MInt998244353, MInt998244353));
23                deq.push_back(ab);
24            }
25            2 => {
26                deq.pop_front();
27            }
28            3 => {
29                deq.pop_back();
30            }
31            4 => {
32                scan!(scanner, x: MInt998244353);
33                let (a, b) = deq.fold_all();
34                writeln!(writer, "{}", a * x + b).ok();
35            }
36            _ => unreachable!("unknown query"),
37        }
38    }
39}

Source

pub fn pop_front(&mut self) -> Option<M::T>

Examples found in repository ?

crates/library_checker/src/data_structure/deque_operate_all_composite.rs (line 26)

10pub fn deque_operate_all_composite(reader: impl Read, mut writer: impl Write) {
11    let s = read_all_unchecked(reader);
12    let mut scanner = Scanner::new(&s);
13    scan!(scanner, q);
14    let mut deq = DequeAggregation::<LinearOperation<_>>::new();
15    for _ in 0..q {
16        match scanner.scan::<usize>() {
17            0 => {
18                scan!(scanner, ab: (MInt998244353, MInt998244353));
19                deq.push_front(ab);
20            }
21            1 => {
22                scan!(scanner, ab: (MInt998244353, MInt998244353));
23                deq.push_back(ab);
24            }
25            2 => {
26                deq.pop_front();
27            }
28            3 => {
29                deq.pop_back();
30            }
31            4 => {
32                scan!(scanner, x: MInt998244353);
33                let (a, b) = deq.fold_all();
34                writeln!(writer, "{}", a * x + b).ok();
35            }
36            _ => unreachable!("unknown query"),
37        }
38    }
39}

Source

pub fn pop_back(&mut self) -> Option<M::T>

Examples found in repository ?

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

10pub fn deque_operate_all_composite(reader: impl Read, mut writer: impl Write) {
11    let s = read_all_unchecked(reader);
12    let mut scanner = Scanner::new(&s);
13    scan!(scanner, q);
14    let mut deq = DequeAggregation::<LinearOperation<_>>::new();
15    for _ in 0..q {
16        match scanner.scan::<usize>() {
17            0 => {
18                scan!(scanner, ab: (MInt998244353, MInt998244353));
19                deq.push_front(ab);
20            }
21            1 => {
22                scan!(scanner, ab: (MInt998244353, MInt998244353));
23                deq.push_back(ab);
24            }
25            2 => {
26                deq.pop_front();
27            }
28            3 => {
29                deq.pop_back();
30            }
31            4 => {
32                scan!(scanner, x: MInt998244353);
33                let (a, b) = deq.fold_all();
34                writeln!(writer, "{}", a * x + b).ok();
35            }
36            _ => unreachable!("unknown query"),
37        }
38    }
39}