competitive/algebra/
action.rs

1use super::*;
2use std::{
3    marker::PhantomData,
4    ops::{Add, Mul},
5};
6
7pub trait MonoidAct {
8    type Key;
9    type Act: Clone;
10    type ActMonoid: Monoid<T = Self::Act>;
11
12    fn act(x: &Self::Key, a: &Self::Act) -> Self::Key;
13
14    fn act_assign(x: &mut Self::Key, a: &Self::Act) {
15        *x = Self::act(x, a);
16    }
17    fn unit() -> Self::Act {
18        <Self::ActMonoid as Unital>::unit()
19    }
20    fn operate(x: &Self::Act, y: &Self::Act) -> Self::Act {
21        <Self::ActMonoid as Magma>::operate(x, y)
22    }
23    fn operate_assign(x: &mut Self::Act, y: &Self::Act) {
24        *x = <Self::ActMonoid as Magma>::operate(x, y);
25    }
26}
27
28pub struct EmptyAct<T> {
29    _marker: PhantomData<fn() -> T>,
30}
31impl<T> MonoidAct for EmptyAct<T>
32where
33    T: Clone,
34{
35    type Key = T;
36    type Act = ();
37    type ActMonoid = ();
38
39    fn act(x: &Self::Key, _a: &Self::Act) -> Self::Key {
40        x.clone()
41    }
42}
43
44pub struct FlattenAct<M> {
45    _marker: PhantomData<fn() -> M>,
46}
47impl<M> MonoidAct for FlattenAct<M>
48where
49    M: Monoid,
50{
51    type Key = M::T;
52    type Act = M::T;
53    type ActMonoid = M;
54    fn act(x: &Self::Key, a: &Self::Act) -> Self::Key {
55        M::operate(x, a)
56    }
57}
58
59pub struct LinearAct<T> {
60    _marker: PhantomData<fn() -> T>,
61}
62impl<T> MonoidAct for LinearAct<T>
63where
64    T: Clone + Zero + One + Add<Output = T> + Mul<Output = T>,
65{
66    type Key = T;
67    type Act = (T, T);
68    type ActMonoid = LinearOperation<T>;
69
70    fn act(x: &Self::Key, (a, b): &Self::Act) -> Self::Key {
71        a.clone() * x.clone() + b.clone()
72    }
73}
74
75pub struct UpdateAct<T> {
76    _marker: PhantomData<fn() -> T>,
77}
78impl<T> MonoidAct for UpdateAct<T>
79where
80    T: Clone,
81{
82    type Key = T;
83    type Act = Option<T>;
84    type ActMonoid = LastOperation<T>;
85
86    fn act(x: &Self::Key, a: &Self::Act) -> Self::Key {
87        a.as_ref().unwrap_or(x).clone()
88    }
89}
competitive/algebra/action.rs

competitive/algebra/
action.rs
