library_checker/data_structure/
point_set_range_composite_large_array.rs1use competitive::prelude::*;
2use competitive::{
3 algebra::LinearOperation,
4 algorithm::SliceSortExt,
5 data_structure::{SegmentTree, StaticSearch},
6 num::mint_basic::MInt998244353 as M,
7};
8
9competitive::define_enum_scan! {
10 #[derive(Clone, Copy)]
11 enum Query: u8 {
12 0 => Set { p: u32, cd: (M, M) }
13 1 => Apply { l: u32, r: u32, x: M }
14 }
15}
16
17#[verify::library_checker("point_set_range_composite_large_array")]
18pub fn point_set_range_composite_large_array(reader: impl Read, writer: impl Write) {
19 prepare_io!(buffered; reader, writer);
20 sc!(_n: u32, q, queries: [Query; q]);
21 let mut values: Vec<_> = queries
22 .iter()
23 .filter_map(|&query| match query {
24 Query::Set { p, .. } => Some(p),
25 _ => None,
26 })
27 .collect();
28 values.radix_sort_by_key(|&x| x);
29 values.dedup();
30 let search = StaticSearch::from_sorted(&values);
31 let mut seg = SegmentTree::<LinearOperation<M>>::new(values.len());
32 let mut endpoints = Vec::with_capacity(2 * q);
33 for &query in &queries {
34 match query {
35 Query::Set { p, .. } => endpoints.push(p),
36 Query::Apply { l, r, .. } => endpoints.extend([l, r]),
37 }
38 }
39 let mut positions = vec![0; endpoints.len()];
40 search.lower_bound_batch(&endpoints, &mut positions);
41 let mut positions = positions.into_iter();
42 for query in queries {
43 match query {
44 Query::Set { cd, .. } => seg.set(positions.next().unwrap(), cd),
45 Query::Apply { x, .. } => {
46 let l = positions.next().unwrap();
47 let r = positions.next().unwrap();
48 let (a, b) = seg.fold(l..r);
49 pp!(a * x + b);
50 }
51 }
52 }
53}