Skip to main content

library_checker/data_structure/
range_reverse_range_sum.rs

1use competitive::prelude::*;
2#[doc(no_inline)]
3pub use competitive::{algebra::RangeSumRangeAdd, data_structure::SplaySequence};
4
5competitive::define_enum_scan! {
6    enum Query: u8 {
7        0 => Reverse { l: usize, r: usize }
8        1 => Sum { l: usize, r: usize }
9    }
10}
11
12#[verify::library_checker("range_reverse_range_sum")]
13pub fn range_reverse_range_sum(reader: impl Read, mut writer: impl Write) {
14    let s = read_all_unchecked(reader);
15    let mut scanner = Scanner::new(&s);
16    scan!(scanner, n, q, a: [i64; n]);
17    let mut seq = SplaySequence::<RangeSumRangeAdd<i64>>::with_capacity(n);
18    seq.extend(a);
19    for _ in 0..q {
20        scan!(scanner, query: Query);
21        match query {
22            Query::Reverse { l, r } => {
23                seq.reverse(l..r);
24            }
25            Query::Sum { l, r } => {
26                let ans = seq.fold(l..r).0;
27                writeln!(writer, "{}", ans).ok();
28            }
29        }
30    }
31}