cp_library_rs/algebraic_structure/
indexed_monoid.rs

1//! モノイドのラッパー
2
3use std::marker::PhantomData;
4
5use crate::{
6    algebraic_structure::{
7        monoid::Monoid,
8        operation::{Max, Min},
9    },
10    data_structure::segment_tree::SegmentTree,
11};
12
13use num_traits::Bounded;
14
15/// インデックスを同時に取得できるようにするラッパー
16pub struct Indexed<M: Monoid>(PhantomData<M>);
17
18// ========== セグ木の初期化 ==========
19impl<T: Ord + Bounded + Clone> Monoid for Indexed<Min<T>> {
20    type Val = (T, usize);
21    fn e() -> Self::Val {
22        (Min::e(), usize::MAX)
23    }
24    fn op(left: &Self::Val, right: &Self::Val) -> Self::Val {
25        if left <= right {
26            left.clone()
27        } else {
28            right.clone()
29        }
30    }
31}
32
33impl<T: Ord + Bounded + Clone> SegmentTree<Indexed<Min<T>>> {
34    /// セグメント木（インデックス付きで）を初期化する
35    /// - 時間計算量:  $`O(N)`$
36    pub fn new_with_index(N: usize) -> Self {
37        let arr = (0..N).map(|i| (Min::e(), i));
38        Self::from_iter(arr)
39    }
40}
41
42impl<T: Ord + Bounded + Clone> Monoid for Indexed<Max<T>> {
43    type Val = (T, usize);
44    fn e() -> Self::Val {
45        (Max::e(), usize::MAX)
46    }
47    fn op(left: &Self::Val, right: &Self::Val) -> Self::Val {
48        if left >= right {
49            left.clone()
50        } else {
51            right.clone()
52        }
53    }
54}
55
56impl<T: Ord + Bounded + Clone> SegmentTree<Indexed<Max<T>>> {
57    /// セグメント木を（インデックス付きで）初期化する
58    /// - 時間計算量:  $`O(N)`$
59    pub fn new_with_index(N: usize) -> Self {
60        let arr = (0..N).map(|i| (Max::e(), i));
61        Self::from_iter(arr)
62    }
63}
cp_library_rs/algebraic_structure/indexed_monoid.rs

cp_library_rs/algebraic_structure/
indexed_monoid.rs
