Skip to main content

library_checker/data_structure/
deque_operate_all_composite.rs

1use competitive::prelude::*;
2#[doc(no_inline)]
3pub use competitive::{
4    algebra::LinearOperation,
5    data_structure::DequeAggregation,
6    num::{MInt, mint_basic::MInt998244353},
7};
8
9competitive::define_enum_scan! {
10    enum Query: usize {
11        0 => PushFront { ab: (MInt998244353, MInt998244353) }
12        1 => PushBack { ab: (MInt998244353, MInt998244353) }
13        2 => PopFront
14        3 => PopBack
15        4 => Apply { x: MInt998244353 }
16    }
17}
18
19#[verify::library_checker("deque_operate_all_composite")]
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}