library_checker/data_structure/
static_rectangle_add_rectangle_sum.rs

1use competitive::prelude::*;
2use competitive::{
3    algebra::{AdditiveOperation, ArrayOperation},
4    algorithm::SliceSortExt,
5    data_structure::{BinaryIndexedTree, StaticSearch},
6    num::{Zero, mint_basic::MInt998244353 as M},
7};
8
9#[verify::library_checker("static_rectangle_add_rectangle_sum")]
10pub fn static_rectangle_add_rectangle_sum(reader: impl Read, writer: impl Write) {
11    prepare_io!(buffered; reader, writer);
12    sc!(n, q, rectangles: [(u32, u32, u32, u32, M); n], queries: [(u32, u32, u32, u32); q]);
13    let mut ys: Vec<_> = rectangles
14        .iter()
15        .flat_map(|&(_, d, _, u, _)| [d, u])
16        .collect();
17    ys.radix_sort_by_key(|&y| y);
18    ys.dedup();
19    let search = StaticSearch::from_sorted(&ys);
20    let endpoints: Vec<_> = rectangles
21        .iter()
22        .flat_map(|&(_, d, _, u, _)| [d, u])
23        .chain(queries.iter().flat_map(|&(_, d, _, u)| [d, u]))
24        .collect();
25    let mut positions = vec![0; endpoints.len()];
26    search.lower_bound_batch(&endpoints, &mut positions);
27    let mut points: Vec<_> = rectangles
28        .into_iter()
29        .zip(positions[..2 * n].as_chunks().0)
30        .flat_map(|((l, _, r, _, w), &[d, u])| {
31            let d = d as u32;
32            let u = u as u32;
33            [(l, d, w), (l, u, -w), (r, d, -w), (r, u, w)]
34        })
35        .collect();
36    points.radix_sort_by_key(|&(x, ..)| x);
37    let mut events: Vec<_> = queries
38        .into_iter()
39        .zip(positions[2 * n..].as_chunks().0)
40        .enumerate()
41        .flat_map(|(i, ((l, d, r, u), &[di, ui]))| {
42            let di = di as u32;
43            let ui = ui as u32;
44            [
45                (l, d, u, di, ui, i as u32, false),
46                (r, d, u, di, ui, i as u32, true),
47            ]
48        })
49        .collect();
50    events.radix_sort_by_key(|&(x, ..)| x);
51    let mut bit = BinaryIndexedTree::<ArrayOperation<AdditiveOperation<M>, 4>>::new(ys.len());
52    let mut points = points.into_iter().peekable();
53    let mut ans = vec![M::zero(); q];
54    for (x, d, u, di, ui, i, add) in events {
55        while points.peek().is_some_and(|&(px, ..)| px < x) {
56            let (px, py, w) = points.next().unwrap();
57            let wx = w * M::from(px);
58            let wy = w * M::from(ys[py as usize]);
59            bit.update(py as usize, [w, wx, wy, wx * M::from(ys[py as usize])]);
60        }
61        for (y, yi, add) in [(d, di, !add), (u, ui, add)] {
62            let [w, wx, wy, wxy] = bit.accumulate0(yi as usize);
63            let value = (w * M::from(x) - wx) * M::from(y) - wy * M::from(x) + wxy;
64            if add {
65                ans[i as usize] += value;
66            } else {
67                ans[i as usize] -= value;
68            }
69        }
70    }
71    pp!(@lf @it ans);
72}
library_checker/data_structure/static_rectangle_add_rectangle_sum.rs

library_checker/data_structure/
static_rectangle_add_rectangle_sum.rs
