library_checker/data_structure/
dynamic_sequence_range_affine_range_sum.rs

1use competitive::prelude::*;
2use competitive::{
3    algebra::RangeSumRangeLinear,
4    data_structure::{ImplicitSplayTree, ImplicitTreap},
5    num::mint_basic::MInt998244353 as M,
6};
7
8competitive::define_enum_scan! {
9    enum Query: usize {
10        0 => Insert { i: usize, x: M }
11        1 => Remove { i: usize }
12        2 => Reverse { l: usize, r: usize }
13        3 => Update { l: usize, r: usize, bc: (M, M) }
14        4 => Fold { l: usize, r: usize }
15    }
16}
17
18#[verify::library_checker("dynamic_sequence_range_affine_range_sum")]
19pub fn dynamic_sequence_range_affine_range_sum(reader: impl Read, writer: impl Write) {
20    prepare_io!(reader, writer);
21    sc!(n, q, a: [M; iter n]);
22
23    let mut seq = ImplicitTreap::<RangeSumRangeLinear<M>>::with_capacity(n + q);
24    seq.extend(a);
25    for _ in 0..q {
26        sc!(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                pp!(seq.fold(l..r).0);
42            }
43        }
44    }
45}
46
47#[verify::library_checker("dynamic_sequence_range_affine_range_sum")]
48pub fn dynamic_sequence_range_affine_range_sum_implicit_splay_tree(
49    reader: impl Read,
50    writer: impl Write,
51) {
52    prepare_io!(reader, writer);
53    sc!(n, q, a: [M; iter n]);
54
55    let mut seq = ImplicitSplayTree::<RangeSumRangeLinear<M>>::with_capacity(n + q);
56    seq.extend(a);
57    for _ in 0..q {
58        sc!(query: Query);
59        match query {
60            Query::Insert { i, x } => {
61                seq.insert(i, x);
62            }
63            Query::Remove { i } => {
64                seq.remove(i);
65            }
66            Query::Reverse { l, r } => {
67                seq.reverse(l..r);
68            }
69            Query::Update { l, r, bc } => {
70                seq.update(l..r, bc);
71            }
72            Query::Fold { l, r } => {
73                pp!(seq.fold(l..r).0);
74            }
75        }
76    }
77}
library_checker/data_structure/dynamic_sequence_range_affine_range_sum.rs

library_checker/data_structure/
dynamic_sequence_range_affine_range_sum.rs
