cp_library_rs/algebraic_structure/
actedmonoid_mod.rs

1//! modを取る作用付きモノイド
2
3use std::{
4    marker::PhantomData,
5    ops::{Add, Mul},
6};
7
8use crate::algebraic_structure::{
9    actedmonoid::ActedMonoid,
10    affine1d::{Affine, AffineTransform},
11};
12
13use num::One;
14use num_traits::Zero;
15
16/// 1次元Affine変換
17/// - 区間を $`ax + b`$ で更新（Affine変換）
18/// - 区間和を取得
19#[derive(Debug)]
20pub struct AffineSum<T>(PhantomData<T>);
21
22impl<T> ActedMonoid for AffineSum<T>
23where
24    T: Add<Output = T> + Mul<Output = T> + Zero + One + Copy + PartialEq + Mul<usize, Output = T>,
25{
26    type Val = (T, usize);
27    type Act = Affine<T>;
28    fn e() -> Self::Val {
29        (T::zero(), 0)
30    }
31    fn id() -> Self::Act {
32        Self::Act::id_()
33    }
34    fn op(x: &Self::Val, y: &Self::Val) -> Self::Val {
35        let (xv, xs) = *x;
36        let (yv, ys) = *y;
37        (xv + yv, xs + ys)
38    }
39    fn compose(x: &Self::Act, y: &Self::Act) -> Self::Act {
40        y.compose(x)
41    }
42    fn mapping(x: &Self::Val, y: &Self::Act) -> Self::Val {
43        let (a, b) = *y;
44        let (val, size) = *x;
45        (a * val + b * size, size)
46    }
47}
48
49/// 一次関数のupdate + 関数合成
50/// - 区間を $`ax + b`$ で更新
51/// - 区間を関数として合成
52#[derive(Debug)]
53pub struct AffineUpdateComposite<T>(PhantomData<T>);
54
55impl<T> ActedMonoid for AffineUpdateComposite<T>
56where
57    T: Add<Output = T> + Mul<Output = T> + Zero + One + Copy + PartialEq,
58{
59    type Val = Affine<T>;
60    type Act = Affine<T>;
61    fn e() -> Self::Val {
62        Self::Val::id_()
63    }
64    fn id() -> Self::Act {
65        Self::Act::id_()
66    }
67    fn op(x: &Self::Val, y: &Self::Val) -> Self::Val {
68        y.compose(x)
69    }
70    fn compose(_x: &Self::Act, y: &Self::Act) -> Self::Act {
71        *y
72    }
73    fn mapping(_x: &Self::Val, y: &Self::Act) -> Self::Val {
74        *y
75    }
76}
cp_library_rs/algebraic_structure/actedmonoid_mod.rs

cp_library_rs/algebraic_structure/
actedmonoid_mod.rs
