Struct DequeAggregation

Source

pub struct DequeAggregation<M>where
    M: Monoid,
{ /* private fields */ }

Implementations§

Source §

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

Source

pub fn new() -> Self

Examples found in repository ?

crates/library_checker/src/datastructure/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            _ => panic!("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/datastructure/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            _ => panic!("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_winsow_aggregation.rs (line 194)

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

More examples

Hide additional examples

crates/library_checker/src/datastructure/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            _ => panic!("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_winsow_aggregation.rs (line 197)

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

More examples

Hide additional examples

crates/library_checker/src/datastructure/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            _ => panic!("unknown query"),
37        }
38    }
39}

Source

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

Examples found in repository ?

crates/library_checker/src/datastructure/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            _ => panic!("unknown query"),
37        }
38    }
39}

Source

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

Examples found in repository ?

crates/library_checker/src/datastructure/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            _ => panic!("unknown query"),
37        }
38    }
39}