Skip to main content

aizu_online_judge/dsl/
dsl_2_g.rs

1use competitive::prelude::*;
2use competitive::{algebra::RangeSumRangeAdd, data_structure::LazySegmentTree};
3
4competitive::define_enum_scan! {
5    enum Query: usize {
6        0 => Add { s: usize, t: usize, x: u64 }
7        1 => Sum { s: usize, t: usize }
8    }
9}
10
11#[verify::aizu_online_judge("DSL_2_G")]
12pub fn dsl_2_g(reader: impl Read, writer: impl Write) {
13    prepare_io!(reader, writer);
14    sc!(n, q);
15    let mut seg = LazySegmentTree::<RangeSumRangeAdd<_>>::from_keys(std::iter::repeat_n(0, n));
16    for _ in 0..q {
17        sc!(query: Query);
18        match query {
19            Query::Add { s, t, x } => {
20                seg.update(s - 1..t, x);
21            }
22            Query::Sum { s, t } => {
23                pp!(seg.fold(s - 1..t).0);
24            }
25        }
26    }
27}