1use super::*;
2use std::{
3 cmp::Ordering,
4 marker::PhantomData,
5 ops::{Add, Mul, Sub},
6};
7
8pub trait LazyMapMonoid {
9 type Key;
10 type Agg: Clone;
11 type Act: Clone + PartialEq;
12 type AggMonoid: Monoid<T = Self::Agg>;
13 type ActMonoid: Monoid<T = Self::Act>;
14 type KeyAct: MonoidAct<Key = Self::Key, Act = Self::Act, ActMonoid = Self::ActMonoid>;
15 fn single_agg(key: &Self::Key) -> Self::Agg;
16 fn toggle(_x: &mut Self::Agg) {}
17 #[inline]
18 fn is_act_unit(act: &Self::Act) -> bool {
19 <Self::ActMonoid as Unital>::is_unit(act)
20 }
21 fn act_agg(x: &Self::Agg, a: &Self::Act) -> Option<Self::Agg>;
22
23 fn act_key(x: &Self::Key, a: &Self::Act) -> Self::Key {
24 <Self::KeyAct as MonoidAct>::act(x, a)
25 }
26
27 #[inline]
28 fn agg_unit() -> Self::Agg {
29 <Self::AggMonoid as Unital>::unit()
30 }
31 #[inline]
32 fn act_unit() -> Self::Act {
33 <Self::ActMonoid as Unital>::unit()
34 }
35 #[inline]
36 fn agg_operate(x: &Self::Agg, y: &Self::Agg) -> Self::Agg {
37 <Self::AggMonoid as Magma>::operate(x, y)
38 }
39 #[inline]
40 fn act_operate(x: &Self::Act, y: &Self::Act) -> Self::Act {
41 <Self::ActMonoid as Magma>::operate(x, y)
42 }
43 #[inline]
44 fn agg_operate_assign(x: &mut Self::Agg, y: &Self::Agg) {
45 *x = <Self::AggMonoid as Magma>::operate(x, y);
46 }
47 #[inline]
48 fn act_operate_assign(x: &mut Self::Act, y: &Self::Act) {
49 *x = <Self::ActMonoid as Magma>::operate(x, y);
50 }
51}
52
53pub struct EmptyActLazy<M> {
54 _marker: PhantomData<fn() -> M>,
55}
56impl<M> LazyMapMonoid for EmptyActLazy<M>
57where
58 M: Monoid,
59{
60 type Key = M::T;
61 type Agg = M::T;
62 type Act = ();
63 type AggMonoid = M;
64 type ActMonoid = ();
65 type KeyAct = EmptyAct<M::T>;
66 fn single_agg(key: &Self::Key) -> Self::Agg {
67 key.clone()
68 }
69 fn act_agg(x: &Self::Agg, _a: &Self::Act) -> Option<Self::Agg> {
70 Some(x.clone())
71 }
72}
73
74pub struct EmptyAggActLazy<T> {
75 _marker: PhantomData<fn() -> T>,
76}
77impl<T> LazyMapMonoid for EmptyAggActLazy<T>
78where
79 T: Clone,
80{
81 type Key = T;
82 type Agg = ();
83 type Act = ();
84 type AggMonoid = ();
85 type ActMonoid = ();
86 type KeyAct = EmptyAct<T>;
87 fn single_agg(_key: &Self::Key) -> Self::Agg {}
88 fn act_agg(_x: &Self::Agg, _a: &Self::Act) -> Option<Self::Agg> {
89 Some(())
90 }
91}
92
93pub struct FlattenLazy<M> {
94 _marker: PhantomData<fn() -> M>,
95}
96impl<M> LazyMapMonoid for FlattenLazy<M>
97where
98 M: Monoid,
99 M::T: PartialEq,
100{
101 type Key = M::T;
102 type Agg = M::T;
103 type Act = M::T;
104 type AggMonoid = M;
105 type ActMonoid = M;
106 type KeyAct = FlattenAct<M>;
107 fn single_agg(key: &Self::Key) -> Self::Agg {
108 key.clone()
109 }
110 fn act_agg(x: &Self::Agg, a: &Self::Act) -> Option<Self::Agg> {
111 Some(M::operate(x, a))
112 }
113}
114
115pub struct RangeSumRangeAdd<T> {
116 _marker: PhantomData<fn() -> T>,
117}
118impl<T> LazyMapMonoid for RangeSumRangeAdd<T>
119where
120 T: Copy + Zero + One + Add<Output = T> + Mul<Output = T> + PartialEq,
121{
122 type Key = T;
123 type Agg = (T, T);
124 type Act = T;
125 type AggMonoid = (AdditiveOperation<T>, AdditiveOperation<T>);
126 type ActMonoid = AdditiveOperation<T>;
127 type KeyAct = FlattenAct<Self::ActMonoid>;
128 fn single_agg(key: &Self::Key) -> Self::Agg {
129 (*key, T::one())
130 }
131 fn act_agg(&(x, y): &Self::Agg, a: &Self::Act) -> Option<Self::Agg> {
132 Some(if Self::is_act_unit(a) {
133 (x, y)
134 } else {
135 let a = *a;
136 (x + a * y, y)
137 })
138 }
139}
140
141pub struct RangeSumRangeLinear<T> {
142 _marker: PhantomData<fn() -> T>,
143}
144impl<T> LazyMapMonoid for RangeSumRangeLinear<T>
145where
146 T: Copy + Zero + One + Add<Output = T> + Mul<Output = T> + PartialEq,
147{
148 type Key = T;
149 type Agg = (T, T);
150 type Act = (T, T);
151 type AggMonoid = (AdditiveOperation<T>, AdditiveOperation<T>);
152 type ActMonoid = LinearOperation<T>;
153 type KeyAct = LinearAct<T>;
154 fn single_agg(key: &Self::Key) -> Self::Agg {
155 (*key, T::one())
156 }
157 fn act_agg(&(x, y): &Self::Agg, &(a, b): &Self::Act) -> Option<Self::Agg> {
158 Some((a * x + b * y, y))
159 }
160}
161
162pub struct RangeSumRangeUpdate<T> {
163 _marker: PhantomData<fn() -> T>,
164}
165impl<T> LazyMapMonoid for RangeSumRangeUpdate<T>
166where
167 T: Copy + Zero + One + Add<Output = T> + Mul<Output = T> + PartialEq,
168{
169 type Key = T;
170 type Agg = (T, T);
171 type Act = Option<T>;
172 type AggMonoid = (AdditiveOperation<T>, AdditiveOperation<T>);
173 type ActMonoid = LastOperation<T>;
174 type KeyAct = UpdateAct<T>;
175 fn single_agg(key: &Self::Key) -> Self::Agg {
176 (*key, T::one())
177 }
178 fn act_agg(&(x, y): &Self::Agg, a: &Self::Act) -> Option<Self::Agg> {
179 Some((a.map(|a| a * y).unwrap_or(x), y))
180 }
181}
182
183pub struct RangeMaxRangeUpdate<T> {
184 _marker: PhantomData<fn() -> T>,
185}
186impl<T> LazyMapMonoid for RangeMaxRangeUpdate<T>
187where
188 T: Clone + PartialEq + Ord + Bounded,
189{
190 type Key = T;
191 type Agg = T;
192 type Act = Option<T>;
193 type AggMonoid = MaxOperation<T>;
194 type ActMonoid = LastOperation<T>;
195 type KeyAct = UpdateAct<T>;
196 fn single_agg(key: &Self::Key) -> Self::Agg {
197 key.clone()
198 }
199 fn act_agg(x: &Self::Agg, a: &Self::Act) -> Option<Self::Agg> {
200 Some(a.as_ref().unwrap_or(x).clone())
201 }
202}
203
204pub struct RangeMinRangeUpdate<T> {
205 _marker: PhantomData<fn() -> T>,
206}
207impl<T> LazyMapMonoid for RangeMinRangeUpdate<T>
208where
209 T: Clone + PartialEq + Ord + Bounded,
210{
211 type Key = T;
212 type Agg = T;
213 type Act = Option<T>;
214 type AggMonoid = MinOperation<T>;
215 type ActMonoid = LastOperation<T>;
216 type KeyAct = UpdateAct<T>;
217 fn single_agg(key: &Self::Key) -> Self::Agg {
218 key.clone()
219 }
220 fn act_agg(x: &Self::Agg, a: &Self::Act) -> Option<Self::Agg> {
221 Some(a.as_ref().unwrap_or(x).clone())
222 }
223}
224
225pub struct RangeMaxRangeAdd<T> {
226 _marker: PhantomData<fn() -> T>,
227}
228impl<T> LazyMapMonoid for RangeMaxRangeAdd<T>
229where
230 T: Clone + Ord + Bounded + Zero + Add<Output = T>,
231{
232 type Key = T;
233 type Agg = T;
234 type Act = T;
235 type AggMonoid = MaxOperation<T>;
236 type ActMonoid = AdditiveOperation<T>;
237 type KeyAct = FlattenAct<Self::ActMonoid>;
238 fn single_agg(key: &Self::Key) -> Self::Agg {
239 key.clone()
240 }
241 fn act_agg(x: &Self::Agg, a: &Self::Act) -> Option<Self::Agg> {
242 Some(if Self::is_act_unit(a) {
243 x.clone()
244 } else {
245 x.clone() + a.clone()
246 })
247 }
248}
249
250pub struct RangeMinRangeAdd<T> {
251 _marker: PhantomData<fn() -> T>,
252}
253impl<T> LazyMapMonoid for RangeMinRangeAdd<T>
254where
255 T: Clone + Ord + Bounded + Zero + Add<Output = T>,
256{
257 type Key = T;
258 type Agg = T;
259 type Act = T;
260 type AggMonoid = MinOperation<T>;
261 type ActMonoid = AdditiveOperation<T>;
262 type KeyAct = FlattenAct<Self::ActMonoid>;
263 fn single_agg(key: &Self::Key) -> Self::Agg {
264 key.clone()
265 }
266 fn act_agg(x: &Self::Agg, a: &Self::Act) -> Option<Self::Agg> {
267 Some(if Self::is_act_unit(a) {
268 x.clone()
269 } else {
270 x.clone() + a.clone()
271 })
272 }
273}
274
275pub struct RangeMinCountRangeAdd<T> {
276 _marker: PhantomData<fn() -> T>,
277}
278impl<T> LazyMapMonoid for RangeMinCountRangeAdd<T>
279where
280 T: Clone + Ord + Bounded + Zero + Add<Output = T>,
281{
282 type Key = T;
283 type Agg = (T, usize);
284 type Act = T;
285 type AggMonoid = CountingOperation<MinOperation<T>>;
286 type ActMonoid = AdditiveOperation<T>;
287 type KeyAct = FlattenAct<Self::ActMonoid>;
288 fn single_agg(key: &Self::Key) -> Self::Agg {
289 (key.clone(), 1)
290 }
291 fn act_agg(x: &Self::Agg, a: &Self::Act) -> Option<Self::Agg> {
292 Some(if x.1 == 0 {
293 x.clone()
294 } else {
295 (x.0.clone() + a.clone(), x.1)
296 })
297 }
298}
299
300#[derive(Debug, Clone, Copy, PartialEq, Eq)]
301pub struct RangeChminChmaxAdd<T> {
302 lb: T,
303 ub: T,
304 bias: T,
305}
306impl<T> RangeChminChmaxAdd<T>
307where
308 T: Zero + Bounded,
309{
310 pub fn chmin(x: T) -> Self {
311 Self {
312 lb: T::minimum(),
313 ub: x,
314 bias: T::zero(),
315 }
316 }
317 pub fn chmax(x: T) -> Self {
318 Self {
319 lb: x,
320 ub: T::maximum(),
321 bias: T::zero(),
322 }
323 }
324 pub fn add(x: T) -> Self {
325 Self {
326 lb: T::minimum(),
327 ub: T::maximum(),
328 bias: x,
329 }
330 }
331}
332impl<T> Magma for RangeChminChmaxAdd<T>
333where
334 T: Copy
335 + Zero
336 + One
337 + Ord
338 + Bounded
339 + Add<Output = T>
340 + Sub<Output = T>
341 + Mul<Output = T>
342 + PartialEq,
343{
344 type T = Self;
345 fn operate(x: &Self::T, y: &Self::T) -> Self::T {
346 Self {
347 lb: (x.lb + x.bias).min(y.ub).max(y.lb) - x.bias,
348 ub: (x.ub + x.bias).max(y.lb).min(y.ub) - x.bias,
349 bias: x.bias + y.bias,
350 }
351 }
352}
353impl<T> Associative for RangeChminChmaxAdd<T> where
354 T: Copy
355 + Zero
356 + One
357 + Ord
358 + Bounded
359 + Add<Output = T>
360 + Sub<Output = T>
361 + Mul<Output = T>
362 + PartialEq
363{
364}
365impl<T> Unital for RangeChminChmaxAdd<T>
366where
367 T: Copy
368 + Zero
369 + One
370 + Ord
371 + Bounded
372 + Add<Output = T>
373 + Sub<Output = T>
374 + Mul<Output = T>
375 + PartialEq,
376{
377 fn unit() -> Self::T {
378 Self {
379 lb: T::minimum(),
380 ub: T::maximum(),
381 bias: T::zero(),
382 }
383 }
384}
385
386#[derive(Debug, Clone, PartialEq, Eq)]
387pub struct RangeSumRangeChminChmaxAdd<T> {
388 min: T,
389 max: T,
390 min2: T,
391 max2: T,
392 pub sum: T,
393 size: T,
394 n_min: T,
395 n_max: T,
396}
397
398impl<T> RangeSumRangeChminChmaxAdd<T>
399where
400 T: Copy
401 + Zero
402 + One
403 + Ord
404 + Bounded
405 + Add<Output = T>
406 + Sub<Output = T>
407 + Mul<Output = T>
408 + PartialEq,
409{
410 pub fn single(key: T, size: T) -> Self {
411 Self {
412 min: key,
413 max: key,
414 min2: T::maximum(),
415 max2: T::minimum(),
416 sum: key * size,
417 size,
418 n_min: size,
419 n_max: size,
420 }
421 }
422}
423impl<T> Magma for RangeSumRangeChminChmaxAdd<T>
424where
425 T: Copy
426 + Zero
427 + One
428 + Ord
429 + Bounded
430 + Add<Output = T>
431 + Sub<Output = T>
432 + Mul<Output = T>
433 + PartialEq,
434{
435 type T = Self;
436 fn operate(x: &Self::T, y: &Self::T) -> Self::T {
437 Self {
438 min: x.min.min(y.min),
439 max: x.max.max(y.max),
440 min2: if x.min == y.min {
441 x.min2.min(y.min2)
442 } else if x.min2 <= y.min {
443 x.min2
444 } else if y.min2 <= x.min {
445 y.min2
446 } else {
447 x.min.max(y.min)
448 },
449 max2: if x.max == y.max {
450 x.max2.max(y.max2)
451 } else if x.max2 >= y.max {
452 x.max2
453 } else if y.max2 >= x.max {
454 y.max2
455 } else {
456 x.max.min(y.max)
457 },
458 sum: x.sum + y.sum,
459 size: x.size + y.size,
460 n_min: match x.min.cmp(&y.min) {
461 Ordering::Less => x.n_min,
462 Ordering::Equal => x.n_min + y.n_min,
463 Ordering::Greater => y.n_min,
464 },
465 n_max: match x.max.cmp(&y.max) {
466 Ordering::Less => y.n_max,
467 Ordering::Equal => x.n_max + y.n_max,
468 Ordering::Greater => x.n_max,
469 },
470 }
471 }
472}
473impl<T> Associative for RangeSumRangeChminChmaxAdd<T> where
474 T: Copy
475 + Zero
476 + One
477 + Ord
478 + Bounded
479 + Add<Output = T>
480 + Sub<Output = T>
481 + Mul<Output = T>
482 + PartialEq
483{
484}
485impl<T> Unital for RangeSumRangeChminChmaxAdd<T>
486where
487 T: Copy
488 + Zero
489 + One
490 + Ord
491 + Bounded
492 + Add<Output = T>
493 + Sub<Output = T>
494 + Mul<Output = T>
495 + PartialEq,
496{
497 fn unit() -> Self::T {
498 Self {
499 min: T::maximum(),
500 max: T::minimum(),
501 min2: T::maximum(),
502 max2: T::minimum(),
503 sum: T::zero(),
504 size: T::zero(),
505 n_min: T::zero(),
506 n_max: T::zero(),
507 }
508 }
509}
510
511impl<T> MonoidAct for RangeChminChmaxAdd<T>
512where
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 type Key = T;
524 type Act = RangeChminChmaxAdd<T>;
525 type ActMonoid = RangeChminChmaxAdd<T>;
526 fn act(x: &Self::Key, a: &Self::Act) -> Self::Key {
527 (*x).max(a.lb).min(a.ub) + a.bias
528 }
529}
530
531impl<T> LazyMapMonoid for RangeSumRangeChminChmaxAdd<T>
532where
533 T: Copy
534 + Zero
535 + One
536 + Ord
537 + Bounded
538 + Add<Output = T>
539 + Sub<Output = T>
540 + Mul<Output = T>
541 + PartialEq,
542{
543 type Key = T;
544 type Agg = Self;
545 type Act = RangeChminChmaxAdd<T>;
546 type AggMonoid = Self;
547 type ActMonoid = RangeChminChmaxAdd<T>;
548 type KeyAct = RangeChminChmaxAdd<T>;
549 fn single_agg(&key: &Self::Key) -> Self::Agg {
550 Self::single(key, T::one())
551 }
552 fn act_agg(x: &Self::Agg, a: &Self::Act) -> Option<Self::Agg> {
553 Some(if Self::is_act_unit(a) {
554 x.clone()
555 } else if x.size.is_zero() {
556 Self::unit()
557 } else if x.min == x.max || a.lb == a.ub || a.lb >= x.max || a.ub <= x.min {
558 Self::single(x.min.max(a.lb).min(a.ub) + a.bias, x.size)
559 } else if x.min2 == x.max {
560 let mut x = x.clone();
561 let min = x.min.max(a.lb) + a.bias;
562 let max = x.max.min(a.ub) + a.bias;
563 x.min = min;
564 x.max2 = min;
565 x.max = max;
566 x.min2 = max;
567 x.sum = min * x.n_min + max * x.n_max;
568 x
569 } else if a.lb < x.min2 && x.max2 < a.ub {
570 let mut x = x.clone();
571 let min = x.min.max(a.lb);
572 let max = x.max.min(a.ub);
573 x.sum = x.sum + (min - x.min) * x.n_min + (max - x.max) * x.n_max + a.bias * x.size;
574 x.min = min + a.bias;
575 x.max = max + a.bias;
576 x.min2 = x.min2 + a.bias;
577 x.max2 = x.max2 + a.bias;
578 x
579 } else {
580 return None;
581 })
582 }
583}