Unital

competitive::algebra

Trait Unital 

Source 
pub trait Unital: Magma {
    // Required method
    fn unit() -> Self::T;

    // Provided methods
    fn is_unit(x: &Self::T) -> bool
       where Self::T: PartialEq { ... }
    fn set_unit(x: &mut Self::T) { ... }
}
Expand description

$\exists e \in T, \forall a \in T, e \circ a = a \circ e = e$

Required Methods§

Source

fn unit() -> Self::T

identity element: $e$

Provided Methods§

Source

fn is_unit(x: &Self::T) -> bool
where Self::T: PartialEq,

Examples found in repository?
crates/competitive/src/algebra/lazy_map.rs (line 127)
126    fn act_agg(&(x, y): &Self::Agg, &a: &Self::Act) -> Option<Self::Agg> {
127        Some(if <Self::ActMonoid as Unital>::is_unit(&a) {
128            (x, y)
129        } else {
130            (x + a * y, y)
131        })
132    }
133}
134
135pub struct RangeSumRangeLinear<T> {
136    _marker: PhantomData<fn() -> T>,
137}
138impl<T> LazyMapMonoid for RangeSumRangeLinear<T>
139where
140    T: Copy + Zero + One + Add<Output = T> + Mul<Output = T> + PartialEq,
141{
142    type Key = T;
143    type Agg = (T, T);
144    type Act = (T, T);
145    type AggMonoid = (AdditiveOperation<T>, AdditiveOperation<T>);
146    type ActMonoid = LinearOperation<T>;
147    type KeyAct = LinearAct<T>;
148    fn single_agg(key: &Self::Key) -> Self::Agg {
149        (*key, T::one())
150    }
151    fn act_agg(&(x, y): &Self::Agg, &(a, b): &Self::Act) -> Option<Self::Agg> {
152        Some(if <Self::ActMonoid as Unital>::is_unit(&(a, b)) {
153            (x, y)
154        } else {
155            (a * x + b * y, y)
156        })
157    }
158}
159
160pub struct RangeSumRangeUpdate<T> {
161    _marker: PhantomData<fn() -> T>,
162}
163impl<T> LazyMapMonoid for RangeSumRangeUpdate<T>
164where
165    T: Copy + Zero + One + Add<Output = T> + Mul<Output = T> + PartialEq,
166{
167    type Key = T;
168    type Agg = (T, T);
169    type Act = Option<T>;
170    type AggMonoid = (AdditiveOperation<T>, AdditiveOperation<T>);
171    type ActMonoid = LastOperation<T>;
172    type KeyAct = UpdateAct<T>;
173    fn single_agg(key: &Self::Key) -> Self::Agg {
174        (*key, T::one())
175    }
176    fn act_agg(&(x, y): &Self::Agg, a: &Self::Act) -> Option<Self::Agg> {
177        Some((a.map(|a| a * y).unwrap_or(x), y))
178    }
179}
180
181pub struct RangeMaxRangeUpdate<T> {
182    _marker: PhantomData<fn() -> T>,
183}
184impl<T> LazyMapMonoid for RangeMaxRangeUpdate<T>
185where
186    T: Clone + PartialEq + Ord + Bounded,
187{
188    type Key = T;
189    type Agg = T;
190    type Act = Option<T>;
191    type AggMonoid = MaxOperation<T>;
192    type ActMonoid = LastOperation<T>;
193    type KeyAct = UpdateAct<T>;
194    fn single_agg(key: &Self::Key) -> Self::Agg {
195        key.clone()
196    }
197    fn act_agg(x: &Self::Agg, a: &Self::Act) -> Option<Self::Agg> {
198        Some(a.as_ref().unwrap_or(x).clone())
199    }
200}
201
202pub struct RangeMinRangeUpdate<T> {
203    _marker: PhantomData<fn() -> T>,
204}
205impl<T> LazyMapMonoid for RangeMinRangeUpdate<T>
206where
207    T: Clone + PartialEq + Ord + Bounded,
208{
209    type Key = T;
210    type Agg = T;
211    type Act = Option<T>;
212    type AggMonoid = MinOperation<T>;
213    type ActMonoid = LastOperation<T>;
214    type KeyAct = UpdateAct<T>;
215    fn single_agg(key: &Self::Key) -> Self::Agg {
216        key.clone()
217    }
218    fn act_agg(x: &Self::Agg, a: &Self::Act) -> Option<Self::Agg> {
219        Some(a.as_ref().unwrap_or(x).clone())
220    }
221}
222
223pub struct RangeMaxRangeAdd<T> {
224    _marker: PhantomData<fn() -> T>,
225}
226impl<T> LazyMapMonoid for RangeMaxRangeAdd<T>
227where
228    T: Clone + Ord + Bounded + Zero + Add<Output = T>,
229{
230    type Key = T;
231    type Agg = T;
232    type Act = T;
233    type AggMonoid = MaxOperation<T>;
234    type ActMonoid = AdditiveOperation<T>;
235    type KeyAct = FlattenAct<Self::ActMonoid>;
236    fn single_agg(key: &Self::Key) -> Self::Agg {
237        key.clone()
238    }
239    fn act_agg(x: &Self::Agg, a: &Self::Act) -> Option<Self::Agg> {
240        Some(if <Self::ActMonoid as Unital>::is_unit(a) {
241            x.clone()
242        } else {
243            x.clone() + a.clone()
244        })
245    }
246}
247
248pub struct RangeMinRangeAdd<T> {
249    _marker: PhantomData<fn() -> T>,
250}
251impl<T> LazyMapMonoid for RangeMinRangeAdd<T>
252where
253    T: Clone + Ord + Bounded + Zero + Add<Output = T>,
254{
255    type Key = T;
256    type Agg = T;
257    type Act = T;
258    type AggMonoid = MinOperation<T>;
259    type ActMonoid = AdditiveOperation<T>;
260    type KeyAct = FlattenAct<Self::ActMonoid>;
261    fn single_agg(key: &Self::Key) -> Self::Agg {
262        key.clone()
263    }
264    fn act_agg(x: &Self::Agg, a: &Self::Act) -> Option<Self::Agg> {
265        Some(if <Self::ActMonoid as Unital>::is_unit(a) {
266            x.clone()
267        } else {
268            x.clone() + a.clone()
269        })
270    }
271}
272
273#[derive(Debug, Clone, Copy, PartialEq, Eq)]
274pub struct RangeChminChmaxAdd<T> {
275    lb: T,
276    ub: T,
277    bias: T,
278}
279impl<T> RangeChminChmaxAdd<T>
280where
281    T: Zero + Bounded,
282{
283    pub fn chmin(x: T) -> Self {
284        Self {
285            lb: T::minimum(),
286            ub: x,
287            bias: T::zero(),
288        }
289    }
290    pub fn chmax(x: T) -> Self {
291        Self {
292            lb: x,
293            ub: T::maximum(),
294            bias: T::zero(),
295        }
296    }
297    pub fn add(x: T) -> Self {
298        Self {
299            lb: T::minimum(),
300            ub: T::maximum(),
301            bias: x,
302        }
303    }
304}
305impl<T> Magma for RangeChminChmaxAdd<T>
306where
307    T: Copy
308        + Zero
309        + One
310        + Ord
311        + Bounded
312        + Add<Output = T>
313        + Sub<Output = T>
314        + Mul<Output = T>
315        + PartialEq,
316{
317    type T = Self;
318    fn operate(x: &Self::T, y: &Self::T) -> Self::T {
319        Self {
320            lb: (x.lb + x.bias).min(y.ub).max(y.lb) - x.bias,
321            ub: (x.ub + x.bias).max(y.lb).min(y.ub) - x.bias,
322            bias: x.bias + y.bias,
323        }
324    }
325}
326impl<T> Associative for RangeChminChmaxAdd<T> where
327    T: Copy
328        + Zero
329        + One
330        + Ord
331        + Bounded
332        + Add<Output = T>
333        + Sub<Output = T>
334        + Mul<Output = T>
335        + PartialEq
336{
337}
338impl<T> Unital for RangeChminChmaxAdd<T>
339where
340    T: Copy
341        + Zero
342        + One
343        + Ord
344        + Bounded
345        + Add<Output = T>
346        + Sub<Output = T>
347        + Mul<Output = T>
348        + PartialEq,
349{
350    fn unit() -> Self::T {
351        Self {
352            lb: T::minimum(),
353            ub: T::maximum(),
354            bias: T::zero(),
355        }
356    }
357}
358
359#[derive(Debug, Clone, PartialEq, Eq)]
360pub struct RangeSumRangeChminChmaxAdd<T> {
361    min: T,
362    max: T,
363    min2: T,
364    max2: T,
365    pub sum: T,
366    size: T,
367    n_min: T,
368    n_max: T,
369}
370
371impl<T> RangeSumRangeChminChmaxAdd<T>
372where
373    T: Copy
374        + Zero
375        + One
376        + Ord
377        + Bounded
378        + Add<Output = T>
379        + Sub<Output = T>
380        + Mul<Output = T>
381        + PartialEq,
382{
383    pub fn single(key: T, size: T) -> Self {
384        Self {
385            min: key,
386            max: key,
387            min2: T::maximum(),
388            max2: T::minimum(),
389            sum: key * size,
390            size,
391            n_min: size,
392            n_max: size,
393        }
394    }
395}
396impl<T> Magma for RangeSumRangeChminChmaxAdd<T>
397where
398    T: Copy
399        + Zero
400        + One
401        + Ord
402        + Bounded
403        + Add<Output = T>
404        + Sub<Output = T>
405        + Mul<Output = T>
406        + PartialEq,
407{
408    type T = Self;
409    fn operate(x: &Self::T, y: &Self::T) -> Self::T {
410        Self {
411            min: x.min.min(y.min),
412            max: x.max.max(y.max),
413            min2: if x.min == y.min {
414                x.min2.min(y.min2)
415            } else if x.min2 <= y.min {
416                x.min2
417            } else if y.min2 <= x.min {
418                y.min2
419            } else {
420                x.min.max(y.min)
421            },
422            max2: if x.max == y.max {
423                x.max2.max(y.max2)
424            } else if x.max2 >= y.max {
425                x.max2
426            } else if y.max2 >= x.max {
427                y.max2
428            } else {
429                x.max.min(y.max)
430            },
431            sum: x.sum + y.sum,
432            size: x.size + y.size,
433            n_min: match x.min.cmp(&y.min) {
434                Ordering::Less => x.n_min,
435                Ordering::Equal => x.n_min + y.n_min,
436                Ordering::Greater => y.n_min,
437            },
438            n_max: match x.max.cmp(&y.max) {
439                Ordering::Less => y.n_max,
440                Ordering::Equal => x.n_max + y.n_max,
441                Ordering::Greater => x.n_max,
442            },
443        }
444    }
445}
446impl<T> Associative for RangeSumRangeChminChmaxAdd<T> where
447    T: Copy
448        + Zero
449        + One
450        + Ord
451        + Bounded
452        + Add<Output = T>
453        + Sub<Output = T>
454        + Mul<Output = T>
455        + PartialEq
456{
457}
458impl<T> Unital for RangeSumRangeChminChmaxAdd<T>
459where
460    T: Copy
461        + Zero
462        + One
463        + Ord
464        + Bounded
465        + Add<Output = T>
466        + Sub<Output = T>
467        + Mul<Output = T>
468        + PartialEq,
469{
470    fn unit() -> Self::T {
471        Self {
472            min: T::maximum(),
473            max: T::minimum(),
474            min2: T::maximum(),
475            max2: T::minimum(),
476            sum: T::zero(),
477            size: T::zero(),
478            n_min: T::zero(),
479            n_max: T::zero(),
480        }
481    }
482}
483
484impl<T> MonoidAct for RangeChminChmaxAdd<T>
485where
486    T: Copy
487        + Zero
488        + One
489        + Ord
490        + Bounded
491        + Add<Output = T>
492        + Sub<Output = T>
493        + Mul<Output = T>
494        + PartialEq,
495{
496    type Key = T;
497    type Act = RangeChminChmaxAdd<T>;
498    type ActMonoid = RangeChminChmaxAdd<T>;
499    fn act(x: &Self::Key, a: &Self::Act) -> Self::Key {
500        (*x).max(a.lb).min(a.ub) + a.bias
501    }
502}
503
504impl<T> LazyMapMonoid for RangeSumRangeChminChmaxAdd<T>
505where
506    T: Copy
507        + Zero
508        + One
509        + Ord
510        + Bounded
511        + Add<Output = T>
512        + Sub<Output = T>
513        + Mul<Output = T>
514        + PartialEq,
515{
516    type Key = T;
517    type Agg = Self;
518    type Act = RangeChminChmaxAdd<T>;
519    type AggMonoid = Self;
520    type ActMonoid = RangeChminChmaxAdd<T>;
521    type KeyAct = RangeChminChmaxAdd<T>;
522    fn single_agg(&key: &Self::Key) -> Self::Agg {
523        Self::single(key, T::one())
524    }
525    fn act_agg(x: &Self::Agg, a: &Self::Act) -> Option<Self::Agg> {
526        Some(if <Self::ActMonoid as Unital>::is_unit(a) {
527            x.clone()
528        } else if x.size.is_zero() {
529            Self::unit()
530        } else if x.min == x.max || a.lb == a.ub || a.lb >= x.max || a.ub <= x.min {
531            Self::single(x.min.max(a.lb).min(a.ub) + a.bias, x.size)
532        } else if x.min2 == x.max {
533            let mut x = x.clone();
534            let min = x.min.max(a.lb) + a.bias;
535            let max = x.max.min(a.ub) + a.bias;
536            x.min = min;
537            x.max2 = min;
538            x.max = max;
539            x.min2 = max;
540            x.sum = min * x.n_min + max * x.n_max;
541            x
542        } else if a.lb < x.min2 && x.max2 < a.ub {
543            let mut x = x.clone();
544            let min = x.min.max(a.lb);
545            let max = x.max.min(a.ub);
546            x.sum = x.sum + (min - x.min) * x.n_min + (max - x.max) * x.n_max + a.bias * x.size;
547            x.min = min + a.bias;
548            x.max = max + a.bias;
549            x.min2 = x.min2 + a.bias;
550            x.max2 = x.max2 + a.bias;
551            x
552        } else {
553            return None;
554        })
555    }
More examples
Hide additional examples
crates/competitive/src/data_structure/pairing_heap.rs (line 40)
39    fn propagate(&mut self) {
40        if !<A::ActMonoid as Unital>::is_unit(&self.lazy) {
41            let act = replace(&mut self.lazy, A::unit());
42            if let Some(node) = self.first_child.as_mut() {
43                node.apply(&act);
44            }
45            if let Some(node) = self.next_sibling.as_mut() {
46                node.apply(&act);
47            }
48        }
49    }
crates/competitive/src/algorithm/baby_step_giant_step.rs (line 9)
5pub fn baby_step_giant_step<M>(x: M::T, y: M::T, n: usize) -> Option<usize>
6where
7    M: Monoid<T: Eq + Hash>,
8{
9    if M::is_unit(&y) {
10        return Some(0);
11    }
12    let block_size = 1usize.max((n as f64).sqrt() as _);
13    let mut baby = HashSet::new();
14    let mut t = y.clone();
15    for _ in 0..block_size {
16        t = M::operate(&x, &t);
17        baby.insert(t.clone());
18    }
19    let g = M::pow(x.clone(), block_size);
20    let mut t = M::unit();
21    let mut fail = 0usize;
22    for k in (0..n).step_by(block_size) {
23        let nt = M::operate(&g, &t);
24        if baby.contains(&nt) {
25            for m in k..n.min(k + block_size) {
26                if t == y {
27                    return Some(m);
28                }
29                t = M::operate(&x, &t);
30            }
31            fail += 1;
32            if fail >= 2 {
33                break;
34            }
35        }
36        t = nt;
37    }
38    None
39}
Source

fn set_unit(x: &mut Self::T)

Dyn Compatibility§

This trait is not dyn compatible.

In older versions of Rust, dyn compatibility was called "object safety", so this trait is not object safe.

Implementations on Foreign Types§

Source§

impl Unital for ()

Source§

fn unit() -> Self::T

Source§

impl<A: Unital> Unital for (A,)

Source§

fn unit() -> Self::T

Source§

impl<A: Unital, B: Unital> Unital for (A, B)

Source§

fn unit() -> Self::T

Source§

impl<A: Unital, B: Unital, C: Unital> Unital for (A, B, C)

Source§

fn unit() -> Self::T

Source§

impl<A: Unital, B: Unital, C: Unital, D: Unital> Unital for (A, B, C, D)

Source§

fn unit() -> Self::T

Source§

impl<A: Unital, B: Unital, C: Unital, D: Unital, E: Unital> Unital for (A, B, C, D, E)

Source§

fn unit() -> Self::T

Source§

impl<A: Unital, B: Unital, C: Unital, D: Unital, E: Unital, F: Unital> Unital for (A, B, C, D, E, F)

Source§

fn unit() -> Self::T

Source§

impl<A: Unital, B: Unital, C: Unital, D: Unital, E: Unital, F: Unital, G: Unital> Unital for (A, B, C, D, E, F, G)

Source§

fn unit() -> Self::T

Source§

impl<A: Unital, B: Unital, C: Unital, D: Unital, E: Unital, F: Unital, G: Unital, H: Unital> Unital for (A, B, C, D, E, F, G, H)

Source§

fn unit() -> Self::T

Source§

impl<A: Unital, B: Unital, C: Unital, D: Unital, E: Unital, F: Unital, G: Unital, H: Unital, I: Unital> Unital for (A, B, C, D, E, F, G, H, I)

Source§

fn unit() -> Self::T

Source§

impl<A: Unital, B: Unital, C: Unital, D: Unital, E: Unital, F: Unital, G: Unital, H: Unital, I: Unital, J: Unital> Unital for (A, B, C, D, E, F, G, H, I, J)

Source§

fn unit() -> Self::T

Implementors§

Source§

impl Unital for Gf2_63

Source§

impl Unital for Mersenne61

Source§

impl Unital for PermutationOperation

Source§

impl Unital for Mersenne61Add

Source§

impl Unital for SumMinimum

Source§

impl<M> Unital for CountingOperation<M>
where M: Unital<T: PartialEq> + Idempotent,

Source§

impl<M> Unital for ReverseOperation<M>
where M: Unital,

Source§

impl<M, const N: usize> Unital for ArrayOperation<M, N>
where M: Unital,

Source§

impl<R> Unital for FloorPowerSum<R>
where R: SemiRing,

Source§

impl<R, const X: usize, const Y: usize> Unital for FloorSum<R, X, Y>
where R: SemiRing,

Source§

impl<T> Unital for AdditiveOperation<T>
where T: Clone + Zero + Add<Output = T>,

Source§

impl<T> Unital for BitAndOperation<T>
where T: Clone + BitAndIdentity,

Source§

impl<T> Unital for BitOrOperation<T>
where T: Clone + BitOrIdentity,

Source§

impl<T> Unital for BitXorOperation<T>
where T: Clone + BitXorIdentity,

Source§

impl<T> Unital for ConcatenateOperation<T>
where T: Clone,

Source§

impl<T> Unital for FindMajorityOperation<T>
where T: Clone + Eq,

Source§

impl<T> Unital for FirstOperation<T>
where T: Clone,

Source§

impl<T> Unital for LastOperation<T>
where T: Clone,

Source§

impl<T> Unital for LinearOperation<T>
where T: Clone + Zero + One + Add<Output = T> + Mul<Output = T>,

Source§

impl<T> Unital for LogicalLinearOperation<T>
where T: Clone + BitXorIdentity + BitAndIdentity + BitXor<Output = T> + BitAnd<Output = T>,

Source§

impl<T> Unital for MaxOperation<T>
where T: Clone + Ord + Bounded,

Source§

impl<T> Unital for MinOperation<T>
where T: Clone + Ord + Bounded,

Source§

impl<T> Unital for MinimumIntervalMovementOperation<T>
where T: Clone + Ord + Add<Output = T> + Sub<Output = T> + Zero + Bounded,

Source§

impl<T> Unital for MultiplicativeOperation<T>
where T: Clone + One + Mul<Output = T>,

Source§

impl<T> Unital for RangeChminChmaxAdd<T>
where T: Copy + Zero + One + Ord + Bounded + Add<Output = T> + Sub<Output = T> + Mul<Output = T> + PartialEq,

Source§

impl<T> Unital for RangeSumRangeChminChmaxAdd<T>
where T: Copy + Zero + One + Ord + Bounded + Add<Output = T> + Sub<Output = T> + Mul<Output = T> + PartialEq,

Source§

impl<T> Unital for SortedConcatenateOperation<T>
where T: Clone + Ord,

Source§

impl<const K: usize, T> Unital for BottomkOperation<K, T>
where T: Clone + Ord + Bounded,

Source§

impl<const K: usize, T> Unital for TopkOperation<K, T>
where T: Clone + Ord + Bounded,