library_checker/datastructure/
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
9#[verify::library_checker("deque_operate_all_composite")]
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}