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;
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 fn act_agg(x: &Self::Agg, a: &Self::Act) -> Option<Self::Agg>;
18
19 fn act_key(x: &Self::Key, a: &Self::Act) -> Self::Key {
20 <Self::KeyAct as MonoidAct>::act(x, a)
21 }
22
23 #[inline]
24 fn agg_unit() -> Self::Agg {
25 <Self::AggMonoid as Unital>::unit()
26 }
27 #[inline]
28 fn act_unit() -> Self::Act {
29 <Self::ActMonoid as Unital>::unit()
30 }
31 #[inline]
32 fn agg_operate(x: &Self::Agg, y: &Self::Agg) -> Self::Agg {
33 <Self::AggMonoid as Magma>::operate(x, y)
34 }
35 #[inline]
36 fn act_operate(x: &Self::Act, y: &Self::Act) -> Self::Act {
37 <Self::ActMonoid as Magma>::operate(x, y)
38 }
39 #[inline]
40 fn agg_operate_assign(x: &mut Self::Agg, y: &Self::Agg) {
41 *x = <Self::AggMonoid as Magma>::operate(x, y);
42 }
43 #[inline]
44 fn act_operate_assign(x: &mut Self::Act, y: &Self::Act) {
45 *x = <Self::ActMonoid as Magma>::operate(x, y);
46 }
47}
48
49pub struct EmptyActLazy<M> {
50 _marker: PhantomData<fn() -> M>,
51}
52impl<M> LazyMapMonoid for EmptyActLazy<M>
53where
54 M: Monoid,
55{
56 type Key = M::T;
57 type Agg = M::T;
58 type Act = ();
59 type AggMonoid = M;
60 type ActMonoid = ();
61 type KeyAct = EmptyAct<M::T>;
62 fn single_agg(key: &Self::Key) -> Self::Agg {
63 key.clone()
64 }
65 fn act_agg(x: &Self::Agg, _a: &Self::Act) -> Option<Self::Agg> {
66 Some(x.clone())
67 }
68}
69
70pub struct EmptyAggActLazy<T> {
71 _marker: PhantomData<fn() -> T>,
72}
73impl<T> LazyMapMonoid for EmptyAggActLazy<T>
74where
75 T: Clone,
76{
77 type Key = T;
78 type Agg = ();
79 type Act = ();
80 type AggMonoid = ();
81 type ActMonoid = ();
82 type KeyAct = EmptyAct<T>;
83 fn single_agg(_key: &Self::Key) -> Self::Agg {}
84 fn act_agg(_x: &Self::Agg, _a: &Self::Act) -> Option<Self::Agg> {
85 Some(())
86 }
87}
88
89pub struct FlattenLazy<M> {
90 _marker: PhantomData<fn() -> M>,
91}
92impl<M> LazyMapMonoid for FlattenLazy<M>
93where
94 M: Monoid,
95{
96 type Key = M::T;
97 type Agg = M::T;
98 type Act = M::T;
99 type AggMonoid = M;
100 type ActMonoid = M;
101 type KeyAct = FlattenAct<M>;
102 fn single_agg(key: &Self::Key) -> Self::Agg {
103 key.clone()
104 }
105 fn act_agg(x: &Self::Agg, a: &Self::Act) -> Option<Self::Agg> {
106 Some(M::operate(x, a))
107 }
108}
109
110pub struct RangeSumRangeAdd<T> {
111 _marker: PhantomData<fn() -> T>,
112}
113impl<T> LazyMapMonoid for RangeSumRangeAdd<T>
114where
115 T: Copy + Zero + One + Add<Output = T> + Mul<Output = T> + PartialEq,
116{
117 type Key = T;
118 type Agg = (T, T);
119 type Act = T;
120 type AggMonoid = (AdditiveOperation<T>, AdditiveOperation<T>);
121 type ActMonoid = AdditiveOperation<T>;
122 type KeyAct = FlattenAct<Self::ActMonoid>;
123 fn single_agg(key: &Self::Key) -> Self::Agg {
124 (*key, T::one())
125 }
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 }
556}