library_checker/data_structure/
range_reverse_range_sum.rs

1use competitive::prelude::*;
2use competitive::{
3    algebra::RangeSumRangeAdd,
4    data_structure::{ImplicitSplayTree, ImplicitTreap},
5};
6
7competitive::define_enum_scan! {
8    enum Query: u8 {
9        0 => Reverse { l: usize, r: usize }
10        1 => Sum { l: usize, r: usize }
11    }
12}
13
14#[verify::library_checker("range_reverse_range_sum")]
15pub fn range_reverse_range_sum(reader: impl Read, writer: impl Write) {
16    prepare_io!(reader, writer);
17    sc!(n, q, a: [i64; iter n]);
18    let mut seq = ImplicitTreap::<RangeSumRangeAdd<i64>>::with_capacity(n);
19    seq.extend(a);
20    for _ in 0..q {
21        sc!(query: Query);
22        match query {
23            Query::Reverse { l, r } => {
24                seq.reverse(l..r);
25            }
26            Query::Sum { l, r } => {
27                let ans = seq.fold(l..r).0;
28                pp!(ans);
29            }
30        }
31    }
32}
33
34#[verify::library_checker("range_reverse_range_sum")]
35pub fn range_reverse_range_sum_implicit_splay_tree(reader: impl Read, writer: impl Write) {
36    prepare_io!(reader, writer);
37    sc!(n, q, a: [i64; iter n]);
38    let mut seq = ImplicitSplayTree::<RangeSumRangeAdd<i64>>::with_capacity(n);
39    seq.extend(a);
40    for _ in 0..q {
41        sc!(query: Query);
42        match query {
43            Query::Reverse { l, r } => {
44                seq.reverse(l..r);
45            }
46            Query::Sum { l, r } => {
47                let ans = seq.fold(l..r).0;
48                pp!(ans);
49            }
50        }
51    }
52}
library_checker/data_structure/range_reverse_range_sum.rs

library_checker/data_structure/
range_reverse_range_sum.rs
