library_checker/data_structure/
point_add_rectangle_sum.rs

1use competitive::prelude::*;
2#[doc(no_inline)]
3pub use competitive::{algebra::AdditiveOperation, data_structure::CompressedSegmentTree2d};
4
5competitive::define_enum_scan! {
6    #[derive(Clone, Copy)]
7    enum Query: u8 {
8        0 => Add { x: u32, y: u32, w: u64 }
9        1 => Sum { l: u32, d: u32, r: u32, u: u32 }
10    }
11}
12
13#[verify::library_checker("point_add_rectangle_sum")]
14pub fn point_add_rectangle_sum(reader: impl Read, mut writer: impl Write) {
15    let s = read_all_unchecked(reader);
16    let mut scanner = Scanner::new(&s);
17    scan!(scanner, n, q, xyw: [(u32, u32, u64); n], queries: [Query; q]);
18    let points: Vec<_> = xyw
19        .iter()
20        .map(|&(x, y, _)| (x, (y,)))
21        .chain(queries.iter().filter_map(|&query| {
22            if let Query::Add { x, y, .. } = query {
23                Some((x, (y,)))
24            } else {
25                None
26            }
27        }))
28        .collect();
29
30    let mut seg = CompressedSegmentTree2d::<AdditiveOperation<u64>, _, _>::new(&points);
31    for &(x, y, w) in &xyw {
32        seg.update(&(x, (y,)), &w);
33    }
34
35    for query in queries {
36        match query {
37            Query::Add { x, y, w } => {
38                seg.update(&(x, (y,)), &w);
39            }
40            Query::Sum { l, d, r, u } => {
41                let ans = seg.fold(&(l..r, (d..u,)));
42                writeln!(writer, "{}", ans).ok();
43            }
44        }
45    }
46}

library_checker/data_structure/point_add_rectangle_sum.rs

library_checker/data_structure/
point_add_rectangle_sum.rs