library_checker/data_structure/
staticrmq.rs

1use competitive::prelude::*;
2use competitive::{
3    algebra::MinOperation,
4    data_structure::{DisjointSparseTable, RangeMinimumQuery, SegmentTree, StaticRangeProduct},
5};
6
7#[verify::library_checker("staticrmq")]
8pub fn staticrmq_disjoint_sparse_table(reader: impl Read, writer: impl Write) {
9    prepare_io!(reader, writer);
10    sc!(n, q, a: [u64; n], lr: [(usize, usize); iter q]);
11    let table = DisjointSparseTable::<MinOperation<_>>::new(a);
12    for (l, r) in lr {
13        pp!(table.fold(l, r));
14    }
15}
16
17#[verify::library_checker("staticrmq")]
18pub fn staticrmq_segment_tree(reader: impl Read, writer: impl Write) {
19    prepare_io!(reader, writer);
20    sc!(n, q, a: [u64; n], lr: [(usize, usize); iter q]);
21    let seg = SegmentTree::<MinOperation<_>>::from_vec(a);
22    for (l, r) in lr {
23        pp!(seg.fold(l..r));
24    }
25}
26
27#[verify::library_checker("staticrmq")]
28pub fn staticrmq_range_minimum_query(reader: impl Read, writer: impl Write) {
29    prepare_io!(reader, writer);
30    sc!(n, q, a: [u64; n], lr: [(usize, usize); iter q]);
31    let rmq = RangeMinimumQuery::new(a);
32    for (l, r) in lr {
33        pp!(rmq.fold(l, r));
34    }
35}
36
37#[verify::library_checker("staticrmq")]
38pub fn staticrmq_static_range_product(reader: impl Read, writer: impl Write) {
39    prepare_io!(reader, writer);
40    sc!(n, q, a: [u64; n], lr: [(usize, usize); iter q]);
41    let table = StaticRangeProduct::<MinOperation<_>>::new(a);
42    for (l, r) in lr {
43        pp!(table.fold(l, r));
44    }
45}
library_checker/data_structure/staticrmq.rs

library_checker/data_structure/
staticrmq.rs
