library_checker/datastructure/
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
7#[verify::library_checker("dynamic_sequence_range_affine_range_sum")]
8pub fn dynamic_sequence_range_affine_range_sum(reader: impl Read, mut writer: impl Write) {
9    let s = read_all_unchecked(reader);
10    let mut scanner = Scanner::new(&s);
11    scan!(scanner, n, q, a: [MInt998244353; n]);
12
13    let mut seq = SplaySequence::<RangeSumRangeLinear<MInt998244353>>::with_capacity(n + q);
14    seq.extend(a);
15    for _ in 0..q {
16        match scanner.scan::<usize>() {
17            0 => {
18                scan!(scanner, i, x: MInt998244353);
19                seq.insert(i, x);
20            }
21            1 => {
22                scan!(scanner, i);
23                seq.remove(i);
24            }
25            2 => {
26                scan!(scanner, l, r);
27                seq.reverse(l..r);
28            }
29            3 => {
30                scan!(scanner, l, r, bc: (MInt998244353, MInt998244353));
31                seq.update(l..r, bc);
32            }
33            4 => {
34                scan!(scanner, l, r);
35                writeln!(writer, "{}", seq.fold(l..r).0).ok();
36            }
37            _ => panic!("unknown query"),
38        }
39    }
40}