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