代数 - Min/Max モノイド

整数は \(\min\) または \(\max\) を演算にしてモノイドになる. ただし, それぞれ単位元として \(\infty\) 及び \(-\infty\) を付け足す必要がある.

これを セグメントツリー に載せると RMQ.

/// Algebra - Monoid - MinInt
use crate::algebra::monoid::*;
use crate::monoid; // IGNORE

#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord)]
pub enum MinInt<X> {
    Val(X),
    Maximal,
}
impl<X> MinInt<X> {
    pub fn unwrap(self) -> X {
        match self {
            Self::Val(x) => x,
            _ => panic!(),
        }
    }
}
monoid! {
    MinInt<X> where [X:Ord];
    one = MinInt::Maximal;
    mul(self, other) = {
        if self < other {
            self
        } else {
            other
        }
    }
}

#[cfg(test)]
mod test_monoid_minint {
    use crate::algebra::monoid_min::*;
    #[test]
    fn test_min() {
        assert_eq!(MinInt::Val(2).unwrap(), 2);
        assert_eq!(MinInt::Val(1) * MinInt::Val(2), MinInt::Val(1));
        assert_eq!(MinInt::Val(2) * MinInt::Val(1), MinInt::Val(1));
        assert_eq!(MinInt::Val(2) * MinInt::Maximal, MinInt::Val(2));
        assert_eq!(MinInt::Maximal * MinInt::Val(1), MinInt::Val(1));
    }
}

/// Algebra - Monoid - MaxInt
use crate::algebra::monoid::*;
use crate::monoid; // IGNORE

#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord)]
pub enum MaxInt<X> {
    Minimal,
    Val(X),
}
impl<X> MaxInt<X> {
    pub fn unwrap(self) -> X {
        match self {
            Self::Val(x) => x,
            _ => panic!(),
        }
    }
}
monoid! {
    MaxInt<X> where [X:Ord];
    one = MaxInt::Minimal;
    mul(self, other) = {
        if self > other {
            self
        } else {
            other
        }
    }
}

#[cfg(test)]
mod test_monoid_maxint {
    use crate::algebra::monoid_max::*;
    #[test]
    fn test_max() {
        assert_eq!(MaxInt::Val(2).unwrap(), 2);
        assert_eq!(MaxInt::Val(1) * MaxInt::Val(2), MaxInt::Val(2));
        assert_eq!(MaxInt::Val(2) * MaxInt::Val(1), MaxInt::Val(2));
        assert_eq!(MaxInt::Val(2) * MaxInt::Minimal, MaxInt::Val(2));
        assert_eq!(MaxInt::Minimal * MaxInt::Val(1), MaxInt::Val(1));
    }
}