competitive::data_structure::sliding_window_aggregation

Struct QueueAggregation

pub struct QueueAggregation<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> QueueAggregation<M>
where M: Monoid,

Source

pub fn new() -> Self

Examples found in repository ?

crates/aizu_online_judge/src/dsl/dsl_3_d.rs (line 8)

5pub fn dsl_3_d(reader: impl Read, writer: impl Write) {
6    prepare_io!(reader, writer);
7    sc!(n, l, a: [u64; iter n]);
8    let mut que = QueueAggregation::<MinOperation<_>>::new();
9    let mut ans = Vec::with_capacity(n - l + 1);
10    for a in a {
11        que.push(a);
12        if que.len() == l {
13            ans.push(que.fold_all());
14            que.pop();
15        }
16    }
17    pp!(@it ans);
18}

More examples

Hide additional examples

crates/aizu_online_judge/src/dsl/dsl_3_a.rs (line 8)

5pub fn dsl_3_a(reader: impl Read, writer: impl Write) {
6    prepare_io!(reader, writer);
7    sc!(n, s: u64, a: [u64; iter n]);
8    let mut que = QueueAggregation::<AdditiveOperation<_>>::new();
9    let mut ans = usize::MAX;
10    for a in a {
11        que.push(a);
12        while que.fold_all() >= s {
13            ans = ans.min(que.len());
14            que.pop();
15        }
16    }
17    pp!(if ans == usize::MAX { 0 } else { ans });
18}

crates/library_checker/src/data_structure/queue_operate_all_composite.rs (line 18)

15pub fn queue_operate_all_composite(reader: impl Read, writer: impl Write) {
16    prepare_io!(reader, writer);
17    sc!(q);
18    let mut que = QueueAggregation::<LinearOperation<_>>::new();
19    for _ in 0..q {
20        sc!(query: Query);
21        match query {
22            Query::Push { ab } => {
23                que.push(ab);
24            }
25            Query::Pop => {
26                que.pop();
27            }
28            Query::Apply { x } => {
29                let (a, b) = que.fold_all();
30                pp!(a * x + b);
31            }
32        }
33    }
34}

Source

pub fn len(&self) -> usize

Examples found in repository ?

crates/aizu_online_judge/src/dsl/dsl_3_d.rs (line 12)

5pub fn dsl_3_d(reader: impl Read, writer: impl Write) {
6    prepare_io!(reader, writer);
7    sc!(n, l, a: [u64; iter n]);
8    let mut que = QueueAggregation::<MinOperation<_>>::new();
9    let mut ans = Vec::with_capacity(n - l + 1);
10    for a in a {
11        que.push(a);
12        if que.len() == l {
13            ans.push(que.fold_all());
14            que.pop();
15        }
16    }
17    pp!(@it ans);
18}

More examples

Hide additional examples

crates/aizu_online_judge/src/dsl/dsl_3_a.rs (line 13)

5pub fn dsl_3_a(reader: impl Read, writer: impl Write) {
6    prepare_io!(reader, writer);
7    sc!(n, s: u64, a: [u64; iter n]);
8    let mut que = QueueAggregation::<AdditiveOperation<_>>::new();
9    let mut ans = usize::MAX;
10    for a in a {
11        que.push(a);
12        while que.fold_all() >= s {
13            ans = ans.min(que.len());
14            que.pop();
15        }
16    }
17    pp!(if ans == usize::MAX { 0 } else { ans });
18}

Source

pub fn is_empty(&self) -> bool

Source

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

Examples found in repository ?

crates/aizu_online_judge/src/dsl/dsl_3_d.rs (line 13)

5pub fn dsl_3_d(reader: impl Read, writer: impl Write) {
6    prepare_io!(reader, writer);
7    sc!(n, l, a: [u64; iter n]);
8    let mut que = QueueAggregation::<MinOperation<_>>::new();
9    let mut ans = Vec::with_capacity(n - l + 1);
10    for a in a {
11        que.push(a);
12        if que.len() == l {
13            ans.push(que.fold_all());
14            que.pop();
15        }
16    }
17    pp!(@it ans);
18}

More examples

Hide additional examples

crates/aizu_online_judge/src/dsl/dsl_3_a.rs (line 12)

5pub fn dsl_3_a(reader: impl Read, writer: impl Write) {
6    prepare_io!(reader, writer);
7    sc!(n, s: u64, a: [u64; iter n]);
8    let mut que = QueueAggregation::<AdditiveOperation<_>>::new();
9    let mut ans = usize::MAX;
10    for a in a {
11        que.push(a);
12        while que.fold_all() >= s {
13            ans = ans.min(que.len());
14            que.pop();
15        }
16    }
17    pp!(if ans == usize::MAX { 0 } else { ans });
18}

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

15pub fn queue_operate_all_composite(reader: impl Read, writer: impl Write) {
16    prepare_io!(reader, writer);
17    sc!(q);
18    let mut que = QueueAggregation::<LinearOperation<_>>::new();
19    for _ in 0..q {
20        sc!(query: Query);
21        match query {
22            Query::Push { ab } => {
23                que.push(ab);
24            }
25            Query::Pop => {
26                que.pop();
27            }
28            Query::Apply { x } => {
29                let (a, b) = que.fold_all();
30                pp!(a * x + b);
31            }
32        }
33    }
34}

Source

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

Source

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

Examples found in repository ?

crates/aizu_online_judge/src/dsl/dsl_3_d.rs (line 11)

5pub fn dsl_3_d(reader: impl Read, writer: impl Write) {
6    prepare_io!(reader, writer);
7    sc!(n, l, a: [u64; iter n]);
8    let mut que = QueueAggregation::<MinOperation<_>>::new();
9    let mut ans = Vec::with_capacity(n - l + 1);
10    for a in a {
11        que.push(a);
12        if que.len() == l {
13            ans.push(que.fold_all());
14            que.pop();
15        }
16    }
17    pp!(@it ans);
18}

More examples

Hide additional examples

crates/aizu_online_judge/src/dsl/dsl_3_a.rs (line 11)

5pub fn dsl_3_a(reader: impl Read, writer: impl Write) {
6    prepare_io!(reader, writer);
7    sc!(n, s: u64, a: [u64; iter n]);
8    let mut que = QueueAggregation::<AdditiveOperation<_>>::new();
9    let mut ans = usize::MAX;
10    for a in a {
11        que.push(a);
12        while que.fold_all() >= s {
13            ans = ans.min(que.len());
14            que.pop();
15        }
16    }
17    pp!(if ans == usize::MAX { 0 } else { ans });
18}

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

15pub fn queue_operate_all_composite(reader: impl Read, writer: impl Write) {
16    prepare_io!(reader, writer);
17    sc!(q);
18    let mut que = QueueAggregation::<LinearOperation<_>>::new();
19    for _ in 0..q {
20        sc!(query: Query);
21        match query {
22            Query::Push { ab } => {
23                que.push(ab);
24            }
25            Query::Pop => {
26                que.pop();
27            }
28            Query::Apply { x } => {
29                let (a, b) = que.fold_all();
30                pp!(a * x + b);
31            }
32        }
33    }
34}

Source

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

Examples found in repository ?

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

87    pub fn pop(&mut self) -> Option<M::T> {
88        if self.front_stack.is_empty() {
89            let mut back_stack = std::mem::take(&mut self.back_stack);
90            for x in back_stack.drain(..).map(|t| t.1).rev() {
91                self.push_front(x);
92            }
93            self.back_stack = back_stack;
94        }
95        self.front_stack.pop().map(|t| t.1)
96    }

Source

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

Examples found in repository ?

crates/aizu_online_judge/src/dsl/dsl_3_d.rs (line 14)

5pub fn dsl_3_d(reader: impl Read, writer: impl Write) {
6    prepare_io!(reader, writer);
7    sc!(n, l, a: [u64; iter n]);
8    let mut que = QueueAggregation::<MinOperation<_>>::new();
9    let mut ans = Vec::with_capacity(n - l + 1);
10    for a in a {
11        que.push(a);
12        if que.len() == l {
13            ans.push(que.fold_all());
14            que.pop();
15        }
16    }
17    pp!(@it ans);
18}

More examples

Hide additional examples

crates/aizu_online_judge/src/dsl/dsl_3_a.rs (line 14)

5pub fn dsl_3_a(reader: impl Read, writer: impl Write) {
6    prepare_io!(reader, writer);
7    sc!(n, s: u64, a: [u64; iter n]);
8    let mut que = QueueAggregation::<AdditiveOperation<_>>::new();
9    let mut ans = usize::MAX;
10    for a in a {
11        que.push(a);
12        while que.fold_all() >= s {
13            ans = ans.min(que.len());
14            que.pop();
15        }
16    }
17    pp!(if ans == usize::MAX { 0 } else { ans });
18}

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

15pub fn queue_operate_all_composite(reader: impl Read, writer: impl Write) {
16    prepare_io!(reader, writer);
17    sc!(q);
18    let mut que = QueueAggregation::<LinearOperation<_>>::new();
19    for _ in 0..q {
20        sc!(query: Query);
21        match query {
22            Query::Push { ab } => {
23                que.push(ab);
24            }
25            Query::Pop => {
26                que.pop();
27            }
28            Query::Apply { x } => {
29                let (a, b) = que.fold_all();
30                pp!(a * x + b);
31            }
32        }
33    }
34}