cp_library_rs/algebraic_structure/
actedmonoid.rs

1//! 作用付きモノイド
2
3/// 作用付きモノイド
4pub trait ActedMonoid {
5    /// 要素のデータ型
6    type Val: Clone + PartialEq;
7    /// 作用素のデータ型
8    type Act: Clone + PartialEq;
9    /// 要素Xの単位元を返す
10    fn e() -> Self::Val;
11    /// 作用素Fの単位元を返す
12    fn id() -> Self::Act;
13    /// 要素同士の演算
14    fn op(x: &Self::Val, y: &Self::Val) -> Self::Val;
15    /// 要素に対する作用
16    fn mapping(x: &Self::Val, y: &Self::Act) -> Self::Val;
17    /// 作用素同士の演算
18    fn compose(x: &Self::Act, y: &Self::Act) -> Self::Act;
19}
20
21/// （遅延セグ木）作用付きモノイド
22pub mod examples {
23
24    use std::{
25        marker::PhantomData,
26        ops::{Add, Mul},
27    };
28
29    use num::{Bounded, FromPrimitive, Zero};
30
31    use super::ActedMonoid;
32
33    /// 区間加算 + 区間和
34    #[derive(Debug)]
35    pub struct AddSum<T>(PhantomData<T>);
36    impl<T> ActedMonoid for AddSum<T>
37    where
38        T: Zero + Clone + Add<Output = T> + Mul<Output = T> + FromPrimitive + PartialEq,
39    {
40        type Val = (T, usize);
41        type Act = T;
42        fn e() -> Self::Val {
43            (T::zero(), 0)
44        }
45        fn id() -> Self::Act {
46            T::zero()
47        }
48        fn op(x: &Self::Val, y: &Self::Val) -> Self::Val {
49            let (xv, xs) = x.clone();
50            let (yv, ys) = y.clone();
51            (xv + yv, xs + ys)
52        }
53        fn mapping(x: &Self::Val, y: &Self::Act) -> Self::Val {
54            let (val, size) = x.clone();
55            (val + y.clone() * T::from_usize(size).unwrap(), size)
56        }
57        fn compose(x: &Self::Act, y: &Self::Act) -> Self::Act {
58            x.clone() + y.clone()
59        }
60    }
61
62    /// 区間更新 + 区間最小値
63    #[derive(Debug)]
64    pub struct UpdateMin<T>(PhantomData<T>);
65    impl<T: Bounded + Ord + Clone> ActedMonoid for UpdateMin<T> {
66        type Val = T;
67        type Act = T;
68        fn e() -> Self::Val {
69            T::max_value()
70        }
71        fn id() -> Self::Act {
72            T::max_value()
73        }
74        fn op(x: &Self::Val, y: &Self::Val) -> Self::Val {
75            x.clone().min(y.clone())
76        }
77        fn mapping(_x: &Self::Val, y: &Self::Act) -> Self::Val {
78            if *y == Self::id() {
79                _x.clone()
80            } else {
81                y.clone()
82            }
83        }
84        fn compose(_x: &Self::Act, y: &Self::Act) -> Self::Act {
85            if *y == Self::id() {
86                _x.clone()
87            } else {
88                y.clone()
89            }
90        }
91    }
92
93    /// 区間更新 + 区間最大値
94    #[derive(Debug)]
95    pub struct UpdateMax<T>(PhantomData<T>);
96    impl<T: Bounded + Ord + Clone> ActedMonoid for UpdateMax<T> {
97        type Val = T;
98        type Act = T;
99        fn e() -> Self::Val {
100            T::min_value()
101        }
102        fn id() -> Self::Act {
103            T::min_value()
104        }
105        fn op(x: &Self::Val, y: &Self::Val) -> Self::Val {
106            x.clone().max(y.clone())
107        }
108        fn mapping(_x: &Self::Val, y: &Self::Act) -> Self::Val {
109            if *y == Self::id() {
110                _x.clone()
111            } else {
112                y.clone()
113            }
114        }
115        fn compose(_x: &Self::Act, y: &Self::Act) -> Self::Act {
116            if *y == Self::id() {
117                _x.clone()
118            } else {
119                y.clone()
120            }
121        }
122    }
123
124    /// 最大値と最小値 + 区間更新
125    pub struct UpdateMinMax<T>(PhantomData<T>);
126    impl<T: Ord + Bounded + Clone> ActedMonoid for UpdateMinMax<T> {
127        type Val = (T, T);
128        type Act = Option<(T, T)>;
129        fn e() -> Self::Val {
130            (T::max_value(), T::min_value())
131        }
132        fn id() -> Self::Act {
133            None
134        }
135        fn op(x: &Self::Val, y: &Self::Val) -> Self::Val {
136            let (xmin, xmax) = x.clone();
137            let (ymin, ymax) = y.clone();
138            (xmin.min(ymin), xmax.max(ymax))
139        }
140        fn mapping(_x: &Self::Val, y: &Self::Act) -> Self::Val {
141            match y.clone() {
142                Some(v) => v,
143                None => _x.clone(),
144            }
145        }
146        fn compose(_x: &Self::Act, y: &Self::Act) -> Self::Act {
147            match y.clone() {
148                Some(v) => Some(v),
149                None => _x.clone(),
150            }
151        }
152    }
153
154    /// 区間加算 + 区間最小値
155    #[derive(Debug)]
156    pub struct AddMin<T>(PhantomData<T>);
157    impl<T> ActedMonoid for AddMin<T>
158    where
159        T: Zero + Clone + Add<Output = T> + Ord + Bounded,
160    {
161        type Val = T;
162        type Act = T;
163        fn e() -> Self::Val {
164            T::max_value()
165        }
166        fn id() -> Self::Act {
167            T::zero()
168        }
169        fn op(x: &Self::Val, y: &Self::Val) -> Self::Val {
170            x.clone().min(y.clone())
171        }
172        fn mapping(x: &Self::Val, y: &Self::Act) -> Self::Val {
173            x.clone() + y.clone()
174        }
175        fn compose(x: &Self::Act, y: &Self::Act) -> Self::Act {
176            x.clone() + y.clone()
177        }
178    }
179
180    /// 区間加算 + 区間最大値
181    #[derive(Debug)]
182    pub struct AddMax<T>(PhantomData<T>);
183    impl<T> ActedMonoid for AddMax<T>
184    where
185        T: Zero + Clone + Add<Output = T> + Ord + Bounded,
186    {
187        type Val = T;
188        type Act = T;
189        fn e() -> Self::Val {
190            T::min_value()
191        }
192        fn id() -> Self::Act {
193            T::zero()
194        }
195        fn op(x: &Self::Val, y: &Self::Val) -> Self::Val {
196            x.clone().max(y.clone())
197        }
198        fn mapping(x: &Self::Val, y: &Self::Act) -> Self::Val {
199            x.clone() + y.clone()
200        }
201        fn compose(x: &Self::Act, y: &Self::Act) -> Self::Act {
202            x.clone() + y.clone()
203        }
204    }
205
206    /// 区間更新 + 区間和取得
207    #[derive(Debug)]
208    pub struct UpdateSum<T>(PhantomData<T>);
209    impl<T> ActedMonoid for UpdateSum<T>
210    where
211        T: Zero + Clone + Add<Output = T> + Mul<Output = T> + FromPrimitive + PartialEq,
212    {
213        type Val = (T, usize);
214        type Act = Option<T>;
215        fn e() -> Self::Val {
216            (T::zero(), 0)
217        }
218        fn id() -> Self::Act {
219            None
220        }
221        fn op(x: &Self::Val, y: &Self::Val) -> Self::Val {
222            let (xv, xs) = x.clone();
223            let (yv, ys) = y.clone();
224            (xv + yv, xs + ys)
225        }
226        fn mapping(_x: &Self::Val, y: &Self::Act) -> Self::Val {
227            let (val, size) = _x.clone();
228            match y.clone() {
229                Some(v) => (v * T::from_usize(size).unwrap(), size),
230                None => (val, size),
231            }
232        }
233        fn compose(_x: &Self::Act, y: &Self::Act) -> Self::Act {
234            match y.clone() {
235                Some(v) => Some(v),
236                None => _x.clone(),
237            }
238        }
239    }
240
241    /// 等差数列加算 + 区間和
242    pub struct ArithSum<T>(PhantomData<T>);
243
244    #[derive(Debug, Clone, PartialEq)]
245    pub struct ArithVal<T> {
246        pub val_sum: T,
247        pub index_sum: usize,
248        pub len: usize,
249    }
250
251    impl<T: Zero> ArithVal<T> {
252        /// インデックス i の値を初期化する
253        pub fn new(i: usize) -> Self {
254            Self {
255                val_sum: T::zero(),
256                index_sum: i,
257                len: 1,
258            }
259        }
260    }
261
262    /// 等差数列
263    #[derive(Debug, Clone, PartialEq)]
264    pub struct ArithAct<T> {
265        /// 公差
266        pub a: T,
267        /// 切片
268        pub b: T,
269    }
270
271    impl<T> ArithAct<T> {
272        /// 等差数列 `a*i + b` を初期化する
273        pub fn new(a: T, b: T) -> Self {
274            Self { a, b }
275        }
276    }
277
278    impl<T> ActedMonoid for ArithSum<T>
279    where
280        T: Zero + Clone + Add<Output = T> + Mul<Output = T> + FromPrimitive + PartialEq,
281    {
282        type Val = ArithVal<T>;
283        type Act = ArithAct<T>;
284        fn e() -> Self::Val {
285            ArithVal {
286                val_sum: T::zero(),
287                index_sum: 0,
288                len: 0,
289            }
290        }
291        fn id() -> Self::Act {
292            ArithAct {
293                a: T::zero(),
294                b: T::zero(),
295            }
296        }
297        fn op(x: &Self::Val, y: &Self::Val) -> Self::Val {
298            let x = x.clone();
299            let y = y.clone();
300            ArithVal {
301                val_sum: x.val_sum + y.val_sum,
302                index_sum: x.index_sum + y.index_sum,
303                len: x.len + y.len,
304            }
305        }
306        fn mapping(x: &Self::Val, y: &Self::Act) -> Self::Val {
307            let ArithVal {
308                val_sum,
309                index_sum,
310                len,
311            } = x.clone();
312            let ArithAct { a, b } = y.clone();
313            ArithVal {
314                val_sum: val_sum
315                    + a * T::from_usize(index_sum).unwrap()
316                    + b * T::from_usize(len).unwrap(),
317                index_sum,
318                len,
319            }
320        }
321        fn compose(x: &Self::Act, y: &Self::Act) -> Self::Act {
322            let x = x.clone();
323            let y = y.clone();
324            ArithAct {
325                a: x.a + y.a,
326                b: x.b + y.b,
327            }
328        }
329    }
330}
cp_library_rs/algebraic_structure/actedmonoid.rs

cp_library_rs/algebraic_structure/
actedmonoid.rs
