competitive::data_structure::sliding_window_aggregation

Struct DequeAggregation

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 24)

20pub fn deque_operate_all_composite(reader: impl Read, mut writer: impl Write) {
21    let s = read_all_unchecked(reader);
22    let mut scanner = Scanner::new(&s);
23    scan!(scanner, q);
24    let mut deq = DequeAggregation::<LinearOperation<_>>::new();
25    for _ in 0..q {
26        scan!(scanner, query: Query);
27        match query {
28            Query::PushFront { ab } => {
29                deq.push_front(ab);
30            }
31            Query::PushBack { ab } => {
32                deq.push_back(ab);
33            }
34            Query::PopFront => {
35                deq.pop_front();
36            }
37            Query::PopBack => {
38                deq.pop_back();
39            }
40            Query::Apply { x } => {
41                let (a, b) = deq.fold_all();
42                writeln!(writer, "{}", a * x + b).ok();
43            }
44        }
45    }
46}

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 41)

20pub fn deque_operate_all_composite(reader: impl Read, mut writer: impl Write) {
21    let s = read_all_unchecked(reader);
22    let mut scanner = Scanner::new(&s);
23    scan!(scanner, q);
24    let mut deq = DequeAggregation::<LinearOperation<_>>::new();
25    for _ in 0..q {
26        scan!(scanner, query: Query);
27        match query {
28            Query::PushFront { ab } => {
29                deq.push_front(ab);
30            }
31            Query::PushBack { ab } => {
32                deq.push_back(ab);
33            }
34            Query::PopFront => {
35                deq.pop_front();
36            }
37            Query::PopBack => {
38                deq.pop_back();
39            }
40            Query::Apply { x } => {
41                let (a, b) = deq.fold_all();
42                writeln!(writer, "{}", a * x + b).ok();
43            }
44        }
45    }
46}

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 29)

20pub fn deque_operate_all_composite(reader: impl Read, mut writer: impl Write) {
21    let s = read_all_unchecked(reader);
22    let mut scanner = Scanner::new(&s);
23    scan!(scanner, q);
24    let mut deq = DequeAggregation::<LinearOperation<_>>::new();
25    for _ in 0..q {
26        scan!(scanner, query: Query);
27        match query {
28            Query::PushFront { ab } => {
29                deq.push_front(ab);
30            }
31            Query::PushBack { ab } => {
32                deq.push_back(ab);
33            }
34            Query::PopFront => {
35                deq.pop_front();
36            }
37            Query::PopBack => {
38                deq.pop_back();
39            }
40            Query::Apply { x } => {
41                let (a, b) = deq.fold_all();
42                writeln!(writer, "{}", a * x + b).ok();
43            }
44        }
45    }
46}

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 32)

20pub fn deque_operate_all_composite(reader: impl Read, mut writer: impl Write) {
21    let s = read_all_unchecked(reader);
22    let mut scanner = Scanner::new(&s);
23    scan!(scanner, q);
24    let mut deq = DequeAggregation::<LinearOperation<_>>::new();
25    for _ in 0..q {
26        scan!(scanner, query: Query);
27        match query {
28            Query::PushFront { ab } => {
29                deq.push_front(ab);
30            }
31            Query::PushBack { ab } => {
32                deq.push_back(ab);
33            }
34            Query::PopFront => {
35                deq.pop_front();
36            }
37            Query::PopBack => {
38                deq.pop_back();
39            }
40            Query::Apply { x } => {
41                let (a, b) = deq.fold_all();
42                writeln!(writer, "{}", a * x + b).ok();
43            }
44        }
45    }
46}

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 35)

20pub fn deque_operate_all_composite(reader: impl Read, mut writer: impl Write) {
21    let s = read_all_unchecked(reader);
22    let mut scanner = Scanner::new(&s);
23    scan!(scanner, q);
24    let mut deq = DequeAggregation::<LinearOperation<_>>::new();
25    for _ in 0..q {
26        scan!(scanner, query: Query);
27        match query {
28            Query::PushFront { ab } => {
29                deq.push_front(ab);
30            }
31            Query::PushBack { ab } => {
32                deq.push_back(ab);
33            }
34            Query::PopFront => {
35                deq.pop_front();
36            }
37            Query::PopBack => {
38                deq.pop_back();
39            }
40            Query::Apply { x } => {
41                let (a, b) = deq.fold_all();
42                writeln!(writer, "{}", a * x + b).ok();
43            }
44        }
45    }
46}

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 38)

20pub fn deque_operate_all_composite(reader: impl Read, mut writer: impl Write) {
21    let s = read_all_unchecked(reader);
22    let mut scanner = Scanner::new(&s);
23    scan!(scanner, q);
24    let mut deq = DequeAggregation::<LinearOperation<_>>::new();
25    for _ in 0..q {
26        scan!(scanner, query: Query);
27        match query {
28            Query::PushFront { ab } => {
29                deq.push_front(ab);
30            }
31            Query::PushBack { ab } => {
32                deq.push_back(ab);
33            }
34            Query::PopFront => {
35                deq.pop_front();
36            }
37            Query::PopBack => {
38                deq.pop_back();
39            }
40            Query::Apply { x } => {
41                let (a, b) = deq.fold_all();
42                writeln!(writer, "{}", a * x + b).ok();
43            }
44        }
45    }
46}