Skip to main content

library_checker/data_structure/
dynamic_sequence_range_affine_range_sum.rs

1use competitive::prelude::*;
2#[doc(no_inline)]
3pub use competitive::{
4    algebra::RangeSumRangeLinear, data_structure::SplaySequence, num::mint_basic::MInt998244353,
5};
6
7competitive::define_enum_scan! {
8    enum Query: usize {
9        0 => Insert { i: usize, x: MInt998244353 }
10        1 => Remove { i: usize }
11        2 => Reverse { l: usize, r: usize }
12        3 => Update { l: usize, r: usize, bc: (MInt998244353, MInt998244353) }
13        4 => Fold { l: usize, r: usize }
14    }
15}
16
17#[verify::library_checker("dynamic_sequence_range_affine_range_sum")]
18pub fn dynamic_sequence_range_affine_range_sum(reader: impl Read, mut writer: impl Write) {
19    let s = read_all_unchecked(reader);
20    let mut scanner = Scanner::new(&s);
21    scan!(scanner, n, q, a: [MInt998244353; n]);
22
23    let mut seq = SplaySequence::<RangeSumRangeLinear<MInt998244353>>::with_capacity(n + q);
24    seq.extend(a);
25    for _ in 0..q {
26        scan!(scanner, query: Query);
27        match query {
28            Query::Insert { i, x } => {
29                seq.insert(i, x);
30            }
31            Query::Remove { i } => {
32                seq.remove(i);
33            }
34            Query::Reverse { l, r } => {
35                seq.reverse(l..r);
36            }
37            Query::Update { l, r, bc } => {
38                seq.update(l..r, bc);
39            }
40            Query::Fold { l, r } => {
41                writeln!(writer, "{}", seq.fold(l..r).0).ok();
42            }
43        }
44    }
45}