pub trait LazyMapMonoid {
type Key;
type Agg: Clone;
type Act: Clone + PartialEq;
type AggMonoid: Monoid<T = Self::Agg>;
type ActMonoid: Monoid<T = Self::Act>;
type KeyAct: MonoidAct<Key = Self::Key, Act = Self::Act, ActMonoid = Self::ActMonoid>;
// Required methods
fn single_agg(key: &Self::Key) -> Self::Agg;
fn act_agg(x: &Self::Agg, a: &Self::Act) -> Option<Self::Agg>;
// Provided methods
fn toggle(_x: &mut Self::Agg) { ... }
fn is_act_unit(act: &Self::Act) -> bool { ... }
fn act_key(x: &Self::Key, a: &Self::Act) -> Self::Key { ... }
fn agg_unit() -> Self::Agg { ... }
fn act_unit() -> Self::Act { ... }
fn agg_operate(x: &Self::Agg, y: &Self::Agg) -> Self::Agg { ... }
fn act_operate(x: &Self::Act, y: &Self::Act) -> Self::Act { ... }
fn agg_operate_assign(x: &mut Self::Agg, y: &Self::Agg) { ... }
fn act_operate_assign(x: &mut Self::Act, y: &Self::Act) { ... }
}Required Associated Types§
type Key
type Agg: Clone
type Act: Clone + PartialEq
type AggMonoid: Monoid<T = Self::Agg>
type ActMonoid: Monoid<T = Self::Act>
type KeyAct: MonoidAct<Key = Self::Key, Act = Self::Act, ActMonoid = Self::ActMonoid>
Required Methods§
fn single_agg(key: &Self::Key) -> Self::Agg
fn act_agg(x: &Self::Agg, a: &Self::Act) -> Option<Self::Agg>
Provided Methods§
Sourcefn toggle(_x: &mut Self::Agg)
fn toggle(_x: &mut Self::Agg)
Examples found in repository?
More examples
Sourcefn is_act_unit(act: &Self::Act) -> bool
fn is_act_unit(act: &Self::Act) -> bool
Examples found in repository?
crates/competitive/src/algebra/lazy_map.rs (line 132)
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 }More examples
crates/competitive/src/tree/link_cut_tree.rs (line 471)
470 fn top_down(data: &mut Self::Data, children: [Option<&mut Self::Data>; 2]) {
471 if L::is_act_unit(&data.value.act) {
472 return;
473 }
474 let action = replace(&mut data.value.act, L::act_unit());
475 for child in children.into_iter().flatten() {
476 Self::apply_non_unit(child, &action);
477 }
478 }
479
480 fn bottom_up(data: &mut Self::Data, children: [Option<&Self::Data>; 2]) {
481 let mut aggregate = L::single_agg(&data.value.key);
482 if let Some(left) = children[0] {
483 aggregate = L::agg_operate(&left.value.agg, &aggregate);
484 }
485 if let Some(right) = children[1] {
486 aggregate = L::agg_operate(&aggregate, &right.value.agg);
487 }
488 data.value.agg = aggregate;
489 }
490
491 fn reverse(data: &mut Self::Data) {
492 L::toggle(&mut data.value.agg);
493 }
494}
495
496impl<L> LinkCutTreePathFold for PathLinkCutTreeSpec<L>
497where
498 L: LazyMapMonoid,
499{
500 type Path = L::Agg;
501
502 fn fold_path(data: &Self::Data) -> Self::Path {
503 data.value.agg.clone()
504 }
505}
506
507impl<L> LinkCutTreePathUpdate for PathLinkCutTreeSpec<L>
508where
509 L: LazyMapMonoid,
510{
511 type PathAction = L::Act;
512
513 fn update_path(data: &mut Self::Data, action: &Self::PathAction) {
514 if !L::is_act_unit(action) {
515 Self::apply_non_unit(data, action);
516 }
517 }crates/competitive/src/data_structure/lazy_segment_tree.rs (line 84)
83 fn update_at(&mut self, k: usize, x: &M::Act) {
84 if M::is_act_unit(x) {
85 return;
86 }
87 let nx = M::act_agg(&self.seg[k], x);
88 if k < self.n {
89 self.lazy[k] = M::act_operate(&self.lazy[k], x);
90 }
91 if let Some(nx) = nx {
92 self.seg[k] = nx;
93 } else if k < self.n {
94 self.propagate_at(k);
95 self.recalc_at(k);
96 } else {
97 panic!("act failed on leaf");
98 }
99 }
100 #[inline]
101 fn recalc_at(&mut self, k: usize) {
102 self.seg[k] = M::agg_operate(&self.seg[2 * k], &self.seg[2 * k + 1]);
103 }
104 #[inline]
105 fn propagate_at(&mut self, k: usize) {
106 debug_assert!(k < self.n);
107 let x = replace(&mut self.lazy[k], M::act_unit());
108 if M::is_act_unit(&x) {
109 return;
110 }
111 self.update_at(2 * k, &x);
112 self.update_at(2 * k + 1, &x);
113 }
114 #[inline]
115 fn propagate(&mut self, k: usize) {
116 for i in (1..=self.n.trailing_zeros()).rev() {
117 self.propagate_at(k >> i);
118 }
119 }
120 #[inline]
121 fn recalc(&mut self, mut k: usize) {
122 while k > 1 {
123 k >>= 1;
124 self.recalc_at(k);
125 }
126 }
127 pub fn update<R>(&mut self, range: R, x: M::Act)
128 where
129 R: RangeBounds<usize>,
130 {
131 let range = range.to_range_bounded(0, self.len).expect("invalid range");
132 if range.is_empty() || M::is_act_unit(&x) {
133 return;
134 }
135 let mut a = range.start + self.n;
136 let mut b = range.end + self.n;
137 for i in (1..=self.n.trailing_zeros()).rev() {
138 if (a >> i) << i != a {
139 self.propagate_at(a >> i);
140 }
141 if (b >> i) << i != b {
142 self.propagate_at((b - 1) >> i);
143 }
144 }
145 while a < b {
146 if a & 1 != 0 {
147 self.update_at(a, &x);
148 a += 1;
149 }
150 if b & 1 != 0 {
151 b -= 1;
152 self.update_at(b, &x);
153 }
154 a /= 2;
155 b /= 2;
156 }
157 let a = range.start + self.n;
158 let b = range.end + self.n;
159 for i in 1..=self.n.trailing_zeros() {
160 if (a >> i) << i != a {
161 self.recalc_at(a >> i);
162 }
163 if (b >> i) << i != b {
164 self.recalc_at((b - 1) >> i);
165 }
166 }
167 }crates/competitive/src/data_structure/lazy_segment_tree_map.rs (line 56)
55 fn update_at(&mut self, k: usize, x: &M::Act) {
56 if M::is_act_unit(x) {
57 return;
58 }
59 let n = self.n;
60 let a = self.get_mut(k);
61 let nx = M::act_agg(&a.0, x);
62 if k < n {
63 a.1 = M::act_operate(&a.1, x);
64 }
65 if let Some(nx) = nx {
66 a.0 = nx;
67 } else if k < n {
68 self.propagate_at(k);
69 self.recalc_at(k);
70 } else {
71 panic!("act failed on leaf");
72 }
73 }
74 #[inline]
75 fn recalc_at(&mut self, k: usize) {
76 let x = match (self.seg.get(&(2 * k)), self.seg.get(&(2 * k + 1))) {
77 (None, None) => M::agg_unit(),
78 (None, Some((y, _))) => y.clone(),
79 (Some((x, _)), None) => x.clone(),
80 (Some((x, _)), Some((y, _))) => M::agg_operate(x, y),
81 };
82 self.get_mut(k).0 = x;
83 }
84 #[inline]
85 fn propagate_at(&mut self, k: usize) {
86 debug_assert!(k < self.n);
87 let x = match self.seg.get_mut(&k) {
88 Some((_, x)) => replace(x, M::act_unit()),
89 None => M::act_unit(),
90 };
91 if M::is_act_unit(&x) {
92 return;
93 }
94 self.update_at(2 * k, &x);
95 self.update_at(2 * k + 1, &x);
96 }
97 #[inline]
98 fn propagate(&mut self, k: usize, right: bool, nofilt: bool) {
99 let right = right as usize;
100 for i in (1..(k + 1 - right).next_power_of_two().trailing_zeros()).rev() {
101 if nofilt || (k >> i) << i != k {
102 self.propagate_at((k - right) >> i);
103 }
104 }
105 }
106 #[inline]
107 fn recalc(&mut self, k: usize, right: bool, nofilt: bool) {
108 let right = right as usize;
109 for i in 1..(k + 1 - right).next_power_of_two().trailing_zeros() {
110 if nofilt || (k >> i) << i != k {
111 self.recalc_at((k - right) >> i);
112 }
113 }
114 }
115 pub fn update<R>(&mut self, range: R, x: M::Act)
116 where
117 R: RangeBounds<usize>,
118 {
119 let range = range.to_range_bounded(0, self.n).expect("invalid range");
120 if M::is_act_unit(&x) {
121 return;
122 }
123 let mut a = range.start + self.n;
124 let mut b = range.end + self.n;
125 self.propagate(a, false, false);
126 self.propagate(b, true, false);
127 while a < b {
128 if a & 1 != 0 {
129 self.update_at(a, &x);
130 a += 1;
131 }
132 if b & 1 != 0 {
133 b -= 1;
134 self.update_at(b, &x);
135 }
136 a /= 2;
137 b /= 2;
138 }
139 self.recalc(range.start + self.n, false, false);
140 self.recalc(range.end + self.n, true, false);
141 }crates/competitive/src/data_structure/implicit_splay_tree.rs (line 84)
83 fn update_act(mut node: BstDataMutRef<'_, Self>, act: &T::Act) {
84 if T::is_act_unit(act) {
85 return;
86 }
87 T::act_operate_assign(&mut node.data_mut().value.act, act);
88 node.data_mut().value.key = T::act_key(&node.reborrow().into_data().value.key, act);
89 if let Some(agg) = T::act_agg(&node.reborrow().into_data().value.agg, act) {
90 node.data_mut().value.agg = agg;
91 } else {
92 Self::top_down(node.reborrow_datamut());
93 Self::bottom_up(node);
94 }
95 }
96
97 fn reverse(mut node: BstDataMutRef<'_, Self>) {
98 node.swap_children();
99 let data = node.data_mut();
100 T::toggle(&mut data.value.agg);
101 data.rev ^= true;
102 }
103}
104
105impl<T> BstSpec for ImplicitSplayTreeSpec<T>
106where
107 T: LazyMapMonoid,
108{
109 type Parent = WithNoParent<Self::Data>;
110 type Data = ImplicitSplayTreeData<T>;
111
112 fn top_down(mut node: BstDataMutRef<'_, Self>) {
113 if !T::is_act_unit(&node.reborrow().into_data().value.act) {
114 let act = replace(&mut node.data_mut().value.act, T::act_unit());
115 if let Ok(left) = node.reborrow_datamut().left().descend() {
116 Self::update_act(left, &act);
117 }
118 if let Ok(right) = node.reborrow_datamut().right().descend() {
119 Self::update_act(right, &act);
120 }
121 }
122 if node.reborrow().into_data().rev {
123 node.data_mut().rev = false;
124 if let Ok(left) = node.reborrow_datamut().left().descend() {
125 Self::reverse(left);
126 }
127 if let Ok(right) = node.reborrow_datamut().right().descend() {
128 Self::reverse(right);
129 }
130 }
131 }crates/competitive/src/data_structure/implicit_treap.rs (line 85)
84 fn update_act(mut node: BstDataMutRef<'_, Self>, act: &T::Act) {
85 if T::is_act_unit(act) {
86 return;
87 }
88 T::act_operate_assign(&mut node.data_mut().value.act, act);
89 node.data_mut().value.key = T::act_key(&node.reborrow().into_data().value.key, act);
90 if let Some(agg) = T::act_agg(&node.reborrow().into_data().value.agg, act) {
91 node.data_mut().value.agg = agg;
92 } else {
93 Self::top_down(node.reborrow_datamut());
94 Self::bottom_up(node);
95 }
96 }
97
98 fn reverse(mut node: BstDataMutRef<'_, Self>) {
99 node.swap_children();
100 let data = node.data_mut();
101 T::toggle(&mut data.value.agg);
102 data.rev ^= true;
103 }
104}
105
106impl<T> BstSpec for ImplicitTreapSpec<T>
107where
108 T: LazyMapMonoid,
109{
110 type Parent = WithNoParent<Self::Data>;
111 type Data = ImplicitTreapData<T>;
112
113 fn top_down(mut node: BstDataMutRef<'_, Self>) {
114 if !T::is_act_unit(&node.reborrow().into_data().value.act) {
115 let act = replace(&mut node.data_mut().value.act, T::act_unit());
116 if let Ok(left) = node.reborrow_datamut().left().descend() {
117 Self::update_act(left, &act);
118 }
119 if let Ok(right) = node.reborrow_datamut().right().descend() {
120 Self::update_act(right, &act);
121 }
122 }
123 if node.reborrow().into_data().rev {
124 node.data_mut().rev = false;
125 if let Ok(left) = node.reborrow_datamut().left().descend() {
126 Self::reverse(left);
127 }
128 if let Ok(right) = node.reborrow_datamut().right().descend() {
129 Self::reverse(right);
130 }
131 }
132 }Additional examples can be found in:
Sourcefn act_key(x: &Self::Key, a: &Self::Act) -> Self::Key
fn act_key(x: &Self::Key, a: &Self::Act) -> Self::Key
Examples found in repository?
More examples
crates/competitive/src/data_structure/implicit_splay_tree.rs (line 88)
83 fn update_act(mut node: BstDataMutRef<'_, Self>, act: &T::Act) {
84 if T::is_act_unit(act) {
85 return;
86 }
87 T::act_operate_assign(&mut node.data_mut().value.act, act);
88 node.data_mut().value.key = T::act_key(&node.reborrow().into_data().value.key, act);
89 if let Some(agg) = T::act_agg(&node.reborrow().into_data().value.agg, act) {
90 node.data_mut().value.agg = agg;
91 } else {
92 Self::top_down(node.reborrow_datamut());
93 Self::bottom_up(node);
94 }
95 }crates/competitive/src/data_structure/implicit_treap.rs (line 89)
84 fn update_act(mut node: BstDataMutRef<'_, Self>, act: &T::Act) {
85 if T::is_act_unit(act) {
86 return;
87 }
88 T::act_operate_assign(&mut node.data_mut().value.act, act);
89 node.data_mut().value.key = T::act_key(&node.reborrow().into_data().value.key, act);
90 if let Some(agg) = T::act_agg(&node.reborrow().into_data().value.agg, act) {
91 node.data_mut().value.agg = agg;
92 } else {
93 Self::top_down(node.reborrow_datamut());
94 Self::bottom_up(node);
95 }
96 }crates/competitive/src/data_structure/binary_search_tree/data.rs (line 152)
143 pub fn update_act<Spec>(mut node: BstDataMutRef<'_, Spec>, act: &L::Act)
144 where
145 Spec: BstSpec<Data: BstDataAccess<marker::LazyMap, Value = Self>>,
146 {
147 if L::is_act_unit(act) {
148 return;
149 }
150 L::act_operate_assign(&mut node.data_mut().bst_data_mut().act, act);
151 node.data_mut().bst_data_mut().key =
152 L::act_key(&node.reborrow().into_data().bst_data().key, act);
153 if let Some(nxlazy) = L::act_agg(&node.reborrow().into_data().bst_data().agg, act) {
154 node.data_mut().bst_data_mut().agg = nxlazy;
155 } else {
156 Self::top_down(node.reborrow_datamut());
157 Self::bottom_up(node.reborrow_datamut());
158 }
159 }Sourcefn agg_unit() -> Self::Agg
fn agg_unit() -> Self::Agg
Examples found in repository?
crates/competitive/src/data_structure/lazy_segment_tree_map.rs (line 52)
51 fn get_mut(&mut self, k: usize) -> &mut (M::Agg, M::Act) {
52 self.seg.entry(k).or_insert((M::agg_unit(), M::act_unit()))
53 }
54 #[inline]
55 fn update_at(&mut self, k: usize, x: &M::Act) {
56 if M::is_act_unit(x) {
57 return;
58 }
59 let n = self.n;
60 let a = self.get_mut(k);
61 let nx = M::act_agg(&a.0, x);
62 if k < n {
63 a.1 = M::act_operate(&a.1, x);
64 }
65 if let Some(nx) = nx {
66 a.0 = nx;
67 } else if k < n {
68 self.propagate_at(k);
69 self.recalc_at(k);
70 } else {
71 panic!("act failed on leaf");
72 }
73 }
74 #[inline]
75 fn recalc_at(&mut self, k: usize) {
76 let x = match (self.seg.get(&(2 * k)), self.seg.get(&(2 * k + 1))) {
77 (None, None) => M::agg_unit(),
78 (None, Some((y, _))) => y.clone(),
79 (Some((x, _)), None) => x.clone(),
80 (Some((x, _)), Some((y, _))) => M::agg_operate(x, y),
81 };
82 self.get_mut(k).0 = x;
83 }
84 #[inline]
85 fn propagate_at(&mut self, k: usize) {
86 debug_assert!(k < self.n);
87 let x = match self.seg.get_mut(&k) {
88 Some((_, x)) => replace(x, M::act_unit()),
89 None => M::act_unit(),
90 };
91 if M::is_act_unit(&x) {
92 return;
93 }
94 self.update_at(2 * k, &x);
95 self.update_at(2 * k + 1, &x);
96 }
97 #[inline]
98 fn propagate(&mut self, k: usize, right: bool, nofilt: bool) {
99 let right = right as usize;
100 for i in (1..(k + 1 - right).next_power_of_two().trailing_zeros()).rev() {
101 if nofilt || (k >> i) << i != k {
102 self.propagate_at((k - right) >> i);
103 }
104 }
105 }
106 #[inline]
107 fn recalc(&mut self, k: usize, right: bool, nofilt: bool) {
108 let right = right as usize;
109 for i in 1..(k + 1 - right).next_power_of_two().trailing_zeros() {
110 if nofilt || (k >> i) << i != k {
111 self.recalc_at((k - right) >> i);
112 }
113 }
114 }
115 pub fn update<R>(&mut self, range: R, x: M::Act)
116 where
117 R: RangeBounds<usize>,
118 {
119 let range = range.to_range_bounded(0, self.n).expect("invalid range");
120 if M::is_act_unit(&x) {
121 return;
122 }
123 let mut a = range.start + self.n;
124 let mut b = range.end + self.n;
125 self.propagate(a, false, false);
126 self.propagate(b, true, false);
127 while a < b {
128 if a & 1 != 0 {
129 self.update_at(a, &x);
130 a += 1;
131 }
132 if b & 1 != 0 {
133 b -= 1;
134 self.update_at(b, &x);
135 }
136 a /= 2;
137 b /= 2;
138 }
139 self.recalc(range.start + self.n, false, false);
140 self.recalc(range.end + self.n, true, false);
141 }
142 pub fn fold<R>(&mut self, range: R) -> M::Agg
143 where
144 R: RangeBounds<usize>,
145 {
146 let range = range.to_range_bounded(0, self.n).expect("invalid range");
147 let mut l = range.start + self.n;
148 let mut r = range.end + self.n;
149 self.propagate(l, false, true);
150 self.propagate(r, true, true);
151 let mut vl = M::agg_unit();
152 let mut vr = M::agg_unit();
153 while l < r {
154 if l & 1 != 0 {
155 if let Some((x, _)) = self.seg.get(&l) {
156 vl = M::agg_operate(&vl, x);
157 }
158 l += 1;
159 }
160 if r & 1 != 0 {
161 r -= 1;
162 if let Some((x, _)) = self.seg.get(&r) {
163 vr = M::agg_operate(x, &vr);
164 }
165 }
166 l /= 2;
167 r /= 2;
168 }
169 M::agg_operate(&vl, &vr)
170 }
171 pub fn set(&mut self, k: usize, x: M::Agg) {
172 let k = k + self.n;
173 self.propagate(k, false, true);
174 *self.get_mut(k) = (x, M::act_unit());
175 self.recalc(k, false, true);
176 }
177 pub fn get(&mut self, k: usize) -> M::Agg {
178 assert!(k < self.n);
179 let k = k + self.n;
180 self.propagate(k, false, true);
181 self.seg
182 .get(&k)
183 .map(|(x, _)| x.clone())
184 .unwrap_or_else(M::agg_unit)
185 }
186 pub fn fold_all(&mut self) -> M::Agg {
187 self.fold(0..self.n)
188 }
189 fn partition_point_perfect<P>(
190 &mut self,
191 mut pos: usize,
192 mut acc: M::Agg,
193 mut pred: P,
194 ) -> (usize, M::Agg)
195 where
196 P: FnMut(&M::Agg) -> bool,
197 {
198 while pos < self.n {
199 self.propagate_at(pos);
200 pos <<= 1;
201 let nacc = match self.seg.get(&pos) {
202 Some((x, _)) => M::agg_operate(&acc, x),
203 None => acc.clone(),
204 };
205 if pred(&nacc) {
206 acc = nacc;
207 pos += 1;
208 }
209 }
210 (pos - self.n, acc)
211 }
212 fn rpartition_point_perfect<P>(
213 &mut self,
214 mut pos: usize,
215 mut acc: M::Agg,
216 mut pred: P,
217 ) -> (usize, M::Agg)
218 where
219 P: FnMut(&M::Agg) -> bool,
220 {
221 while pos < self.n {
222 self.propagate_at(pos);
223 pos = pos * 2 + 1;
224 let nacc = match self.seg.get(&pos) {
225 Some((x, _)) => M::agg_operate(x, &acc),
226 None => acc.clone(),
227 };
228 if pred(&nacc) {
229 acc = nacc;
230 pos -= 1;
231 }
232 }
233 (pos - self.n, acc)
234 }
235 pub fn partition_point_acc<P>(&mut self, left: usize, mut pred: P) -> usize
236 where
237 P: FnMut(&M::Agg) -> bool,
238 {
239 let mut acc = M::agg_unit();
240 if left == self.n {
241 return self.n;
242 }
243 let mut l = left + self.n;
244 let r = 2 * self.n;
245 self.propagate(l, false, true);
246 self.propagate(r, true, true);
247 let mut k = 0usize;
248 while l < r >> k {
249 if l & 1 != 0 {
250 let nacc = match self.seg.get(&l) {
251 Some((x, _)) => M::agg_operate(&acc, x),
252 None => acc.clone(),
253 };
254 if !pred(&nacc) {
255 return self.partition_point_perfect(l, acc, pred).0;
256 }
257 acc = nacc;
258 l += 1;
259 }
260 l >>= 1;
261 k += 1;
262 }
263 for k in (0..k).rev() {
264 let r = r >> k;
265 if r & 1 != 0 {
266 let nacc = match self.seg.get(&(r - 1)) {
267 Some((x, _)) => M::agg_operate(&acc, x),
268 None => acc.clone(),
269 };
270 if !pred(&nacc) {
271 return self.partition_point_perfect(r - 1, acc, pred).0;
272 }
273 acc = nacc;
274 }
275 }
276 self.n
277 }
278 pub fn rpartition_point_acc<P>(&mut self, right: usize, mut pred: P) -> usize
279 where
280 P: FnMut(&M::Agg) -> bool,
281 {
282 let mut acc = M::agg_unit();
283 if right == 0 {
284 return 0;
285 }
286 let mut l = self.n;
287 let mut r = right + self.n;
288 self.propagate(l, false, true);
289 self.propagate(r, true, true);
290 let mut c = 0usize;
291 let mut k = 0usize;
292 while l >> k < r {
293 c <<= 1;
294 if l & (1 << k) != 0 {
295 l += 1 << k;
296 c += 1;
297 }
298 if r & 1 != 0 {
299 r -= 1;
300 let nacc = match self.seg.get(&r) {
301 Some((x, _)) => M::agg_operate(x, &acc),
302 None => acc.clone(),
303 };
304 if !pred(&nacc) {
305 return self.rpartition_point_perfect(r, acc, pred).0 + 1;
306 }
307 acc = nacc;
308 }
309 r >>= 1;
310 k += 1;
311 }
312 for k in (0..k).rev() {
313 if c & 1 != 0 {
314 l -= 1 << k;
315 let l = l >> k;
316 let nacc = match self.seg.get(&l) {
317 Some((x, _)) => M::agg_operate(x, &acc),
318 None => acc.clone(),
319 };
320 if !pred(&nacc) {
321 return self.rpartition_point_perfect(l, acc, pred).0 + 1;
322 }
323 acc = nacc;
324 }
325 c >>= 1;
326 }
327 0
328 }More examples
crates/competitive/src/data_structure/binary_search_tree/seeker.rs (line 151)
149 pub fn new(f: F) -> Self {
150 Self {
151 acc: L::agg_unit(),
152 f,
153 _marker: PhantomData,
154 }
155 }
156}
157
158impl<Spec, L, F> BstSeeker for SeekByAccCond<Spec, L, F>
159where
160 Spec: BstSpec<Data: BstDataAccess<data::marker::LazyMap, Value = LazyMapElement<L>>>,
161 L: LazyMapMonoid,
162 F: FnMut(&L::Agg) -> bool,
163{
164 type Spec = Spec;
165
166 fn bst_seek(&mut self, node: BstImmutRef<'_, Self::Spec>) -> Ordering {
167 if let Ok(left) = node.reborrow().left().descend() {
168 let left_agg = &left.into_data().bst_data().agg;
169 let nagg = L::agg_operate(&self.acc, left_agg);
170 if (self.f)(&nagg) {
171 return Ordering::Greater;
172 }
173 let nagg = L::agg_operate(
174 &nagg,
175 &L::single_agg(&node.reborrow().into_data().bst_data().key),
176 );
177 if (self.f)(&nagg) {
178 Ordering::Equal
179 } else {
180 self.acc = nagg;
181 Ordering::Less
182 }
183 } else {
184 let nagg = L::agg_operate(
185 &self.acc,
186 &L::single_agg(&node.reborrow().into_data().bst_data().key),
187 );
188 if (self.f)(&nagg) {
189 Ordering::Equal
190 } else {
191 self.acc = nagg;
192 Ordering::Less
193 }
194 }
195 }
196}
197
198pub struct SeekByRaccCond<Spec, L, F>
199where
200 L: LazyMapMonoid,
201{
202 acc: L::Agg,
203 f: F,
204 _marker: PhantomData<fn() -> (Spec, L)>,
205}
206
207impl<Spec, L, F> SeekByRaccCond<Spec, L, F>
208where
209 L: LazyMapMonoid,
210 F: FnMut(&L::Agg) -> bool,
211{
212 pub fn new(f: F) -> Self {
213 Self {
214 acc: L::agg_unit(),
215 f,
216 _marker: PhantomData,
217 }
218 }crates/competitive/src/data_structure/binary_trie.rs (line 25)
21 fn new(parent: usize) -> Self {
22 Self {
23 child: [usize::MAX; 2],
24 parent,
25 agg: M::agg_unit(),
26 lazy: M::act_unit(),
27 }
28 }
29}
30
31pub struct BinaryTrie<M>
32where
33 M: LazyMapMonoid,
34{
35 bit_len: usize,
36 max_key: u64,
37 len: usize,
38 xor_mask: u64,
39 nodes: Vec<Node<M>>,
40}
41
42impl<M> BinaryTrie<M>
43where
44 M: LazyMapMonoid,
45{
46 pub fn new(bit_len: usize) -> Self {
47 Self::with_capacity(bit_len, 0)
48 }
49
50 pub fn with_capacity(bit_len: usize, capacity: usize) -> Self {
51 assert!(bit_len <= 64);
52 let max_key = if bit_len == 64 {
53 u64::MAX
54 } else {
55 (1u64 << bit_len) - 1
56 };
57 let mut nodes = Vec::with_capacity(
58 capacity
59 .saturating_mul(bit_len.saturating_add(1))
60 .saturating_add(1),
61 );
62 nodes.push(Node::new(usize::MAX));
63 Self {
64 bit_len,
65 max_key,
66 len: 0,
67 xor_mask: 0,
68 nodes,
69 }
70 }
71
72 pub fn len(&self) -> usize {
73 self.len
74 }
75
76 pub fn is_empty(&self) -> bool {
77 self.len() == 0
78 }
79
80 pub fn clear(&mut self) {
81 self.len = 0;
82 self.xor_mask = 0;
83 self.nodes.clear();
84 self.nodes.push(Node::new(usize::MAX));
85 }
86
87 pub fn set(&mut self, key: u64, value: M::Agg) {
88 self.modify_or_insert(key, |x| *x = value);
89 }
90
91 pub fn modify_or_insert(&mut self, key: u64, f: impl FnOnce(&mut M::Agg)) {
92 assert!(key <= self.max_key);
93 if self.bit_len == 0 {
94 if self.is_empty() {
95 self.len = 1;
96 }
97 f(&mut self.nodes[0].agg);
98 return;
99 }
100
101 let key = key ^ self.xor_mask;
102 let mut inserted = false;
103 let mut node = 0;
104 for d in (0..self.bit_len).rev() {
105 self.push_at(node, d + 1);
106 let bit = ((key >> d) & 1) as usize;
107 if self.nodes[node].child[bit] == usize::MAX {
108 inserted = true;
109 let next = self.nodes.len();
110 self.nodes[node].child[bit] = next;
111 self.nodes.push(Node::new(node));
112 }
113 node = self.nodes[node].child[bit];
114 }
115
116 if inserted {
117 self.len += 1;
118 }
119 self.nodes[node].lazy = M::act_unit();
120 f(&mut self.nodes[node].agg);
121 self.recalc_up(node);
122 }
123
124 pub fn get(&mut self, key: u64) -> Option<M::Agg> {
125 assert!(key <= self.max_key);
126 if self.is_empty() {
127 return None;
128 }
129 if self.bit_len == 0 {
130 return Some(self.nodes[0].agg.clone());
131 }
132
133 let key = key ^ self.xor_mask;
134 let mut node = 0;
135 for d in (0..self.bit_len).rev() {
136 let bit = ((key >> d) & 1) as usize;
137 let next = self.nodes[node].child[bit];
138 if next == usize::MAX {
139 return None;
140 }
141 self.push_at(node, d + 1);
142 node = next;
143 }
144 Some(self.nodes[node].agg.clone())
145 }
146
147 pub fn update<R>(&mut self, range: R, act: M::Act)
148 where
149 R: RangeBounds<u64>,
150 {
151 let Some(range) = self.range_to_bounds(range) else {
152 return;
153 };
154 if self.is_empty() {
155 return;
156 }
157
158 let (ql, qr) = range;
159 if ql == 0 && qr == self.max_key {
160 self.apply_at(0, self.bit_len, &act);
161 return;
162 }
163
164 let mut l = ql;
165 loop {
166 let depth = (l.trailing_zeros() as usize)
167 .min(self.bit_len)
168 .min(63 - (qr - l + 1).leading_zeros() as usize);
169 let r = l | ((1u64 << depth) - 1);
170
171 let mut node = 0;
172 for d in (depth..self.bit_len).rev() {
173 self.push_at(node, d + 1);
174 node = self.nodes[node].child[(((l ^ self.xor_mask) >> d) & 1) as usize];
175 if node == usize::MAX {
176 break;
177 }
178 }
179 if node != usize::MAX {
180 self.apply_at(node, depth, &act);
181 self.recalc_up(node);
182 }
183 if r == qr {
184 break;
185 }
186 l = r + 1;
187 }
188 }
189
190 pub fn fold<R>(&mut self, range: R) -> M::Agg
191 where
192 R: RangeBounds<u64>,
193 {
194 let Some(range) = self.range_to_bounds(range) else {
195 return M::agg_unit();
196 };
197
198 let (ql, qr) = range;
199 if ql == 0 && qr == self.max_key {
200 return self.nodes[0].agg.clone();
201 }
202
203 let mut res = M::agg_unit();
204 let mut l = ql;
205 loop {
206 let depth = (l.trailing_zeros() as usize)
207 .min(self.bit_len)
208 .min(63 - (qr - l + 1).leading_zeros() as usize);
209 let r = l | ((1u64 << depth) - 1);
210
211 let mut node = 0;
212 for d in (depth..self.bit_len).rev() {
213 self.push_at(node, d + 1);
214 node = self.nodes[node].child[(((l ^ self.xor_mask) >> d) & 1) as usize];
215 if node == usize::MAX {
216 break;
217 }
218 }
219 if node != usize::MAX {
220 res = M::agg_operate(&res, &self.nodes[node].agg);
221 }
222 if r == qr {
223 break;
224 }
225 l = r + 1;
226 }
227 res
228 }
229
230 fn apply_at(&mut self, node: usize, depth: usize, act: &M::Act) {
231 if M::is_act_unit(act) {
232 return;
233 }
234 if let Some(agg) = M::act_agg(&self.nodes[node].agg, act) {
235 self.nodes[node].agg = agg;
236 if depth > 0 {
237 M::act_operate_assign(&mut self.nodes[node].lazy, act);
238 }
239 } else if depth == 0 {
240 panic!("act failed on leaf");
241 } else {
242 self.push_at(node, depth);
243 for child in self.nodes[node].child {
244 if child != usize::MAX {
245 self.apply_at(child, depth - 1, act);
246 }
247 }
248 self.recalc_at(node);
249 }
250 }
251
252 fn push_at(&mut self, node: usize, depth: usize) {
253 let act = replace(&mut self.nodes[node].lazy, M::act_unit());
254 if M::is_act_unit(&act) {
255 return;
256 }
257 let child = self.nodes[node].child;
258 for child in child {
259 if child != usize::MAX {
260 self.apply_at(child, depth - 1, &act);
261 }
262 }
263 }
264
265 fn recalc_at(&mut self, node: usize) {
266 let mut agg = M::agg_unit();
267 for child in self.nodes[node].child {
268 if child != usize::MAX {
269 agg = M::agg_operate(&agg, &self.nodes[child].agg);
270 }
271 }
272 self.nodes[node].agg = agg;
273 }crates/competitive/src/data_structure/lazy_segment_tree.rs (line 52)
50 pub fn new(len: usize) -> Self {
51 let n = len.next_power_of_two();
52 let seg = vec![M::agg_unit(); 2 * n];
53 let lazy = vec![M::act_unit(); n];
54 Self { len, n, seg, lazy }
55 }
56 pub fn from_vec(v: Vec<M::Agg>) -> Self {
57 let len = v.len();
58 let n = len.next_power_of_two();
59 let mut seg = vec![M::agg_unit(); 2 * n];
60 for (i, x) in v.into_iter().enumerate() {
61 seg[i + n] = x;
62 }
63 for i in (1..n).rev() {
64 seg[i] = M::agg_operate(&seg[2 * i], &seg[2 * i + 1]);
65 }
66 let lazy = vec![M::act_unit(); n];
67 Self { len, n, seg, lazy }
68 }
69 pub fn from_keys(keys: impl ExactSizeIterator<Item = M::Key>) -> Self {
70 let len = keys.len();
71 let n = len.next_power_of_two();
72 let mut seg = vec![M::agg_unit(); 2 * n];
73 for (i, key) in keys.enumerate() {
74 seg[i + n] = M::single_agg(&key);
75 }
76 for i in (1..n).rev() {
77 seg[i] = M::agg_operate(&seg[2 * i], &seg[2 * i + 1]);
78 }
79 let lazy = vec![M::act_unit(); n];
80 Self { len, n, seg, lazy }
81 }
82 #[inline]
83 fn update_at(&mut self, k: usize, x: &M::Act) {
84 if M::is_act_unit(x) {
85 return;
86 }
87 let nx = M::act_agg(&self.seg[k], x);
88 if k < self.n {
89 self.lazy[k] = M::act_operate(&self.lazy[k], x);
90 }
91 if let Some(nx) = nx {
92 self.seg[k] = nx;
93 } else if k < self.n {
94 self.propagate_at(k);
95 self.recalc_at(k);
96 } else {
97 panic!("act failed on leaf");
98 }
99 }
100 #[inline]
101 fn recalc_at(&mut self, k: usize) {
102 self.seg[k] = M::agg_operate(&self.seg[2 * k], &self.seg[2 * k + 1]);
103 }
104 #[inline]
105 fn propagate_at(&mut self, k: usize) {
106 debug_assert!(k < self.n);
107 let x = replace(&mut self.lazy[k], M::act_unit());
108 if M::is_act_unit(&x) {
109 return;
110 }
111 self.update_at(2 * k, &x);
112 self.update_at(2 * k + 1, &x);
113 }
114 #[inline]
115 fn propagate(&mut self, k: usize) {
116 for i in (1..=self.n.trailing_zeros()).rev() {
117 self.propagate_at(k >> i);
118 }
119 }
120 #[inline]
121 fn recalc(&mut self, mut k: usize) {
122 while k > 1 {
123 k >>= 1;
124 self.recalc_at(k);
125 }
126 }
127 pub fn update<R>(&mut self, range: R, x: M::Act)
128 where
129 R: RangeBounds<usize>,
130 {
131 let range = range.to_range_bounded(0, self.len).expect("invalid range");
132 if range.is_empty() || M::is_act_unit(&x) {
133 return;
134 }
135 let mut a = range.start + self.n;
136 let mut b = range.end + self.n;
137 for i in (1..=self.n.trailing_zeros()).rev() {
138 if (a >> i) << i != a {
139 self.propagate_at(a >> i);
140 }
141 if (b >> i) << i != b {
142 self.propagate_at((b - 1) >> i);
143 }
144 }
145 while a < b {
146 if a & 1 != 0 {
147 self.update_at(a, &x);
148 a += 1;
149 }
150 if b & 1 != 0 {
151 b -= 1;
152 self.update_at(b, &x);
153 }
154 a /= 2;
155 b /= 2;
156 }
157 let a = range.start + self.n;
158 let b = range.end + self.n;
159 for i in 1..=self.n.trailing_zeros() {
160 if (a >> i) << i != a {
161 self.recalc_at(a >> i);
162 }
163 if (b >> i) << i != b {
164 self.recalc_at((b - 1) >> i);
165 }
166 }
167 }
168 pub fn fold<R>(&mut self, range: R) -> M::Agg
169 where
170 R: RangeBounds<usize>,
171 {
172 let range = range.to_range_bounded(0, self.len).expect("invalid range");
173 if range.is_empty() {
174 return M::agg_unit();
175 }
176 if let Some(result) = (|| {
177 let mut left_index = range.start + self.n - 1;
178 let mut right_index = range.end + self.n;
179 let mut left = M::agg_unit();
180 let mut right = M::agg_unit();
181 let mut has_left = false;
182 let mut has_right = false;
183 for _ in 0..(left_index ^ right_index).ilog2() {
184 if left_index & 1 == 0 {
185 left = M::agg_operate(&left, &self.seg[left_index ^ 1]);
186 has_left = true;
187 }
188 if right_index & 1 != 0 {
189 right = M::agg_operate(&self.seg[right_index ^ 1], &right);
190 has_right = true;
191 }
192 left_index >>= 1;
193 right_index >>= 1;
194 if has_left {
195 left = M::act_agg(&left, &self.lazy[left_index])?;
196 }
197 if has_right && right_index < self.n {
198 right = M::act_agg(&right, &self.lazy[right_index])?;
199 }
200 }
201 let mut result = M::agg_operate(&left, &right);
202 while left_index > 1 {
203 left_index >>= 1;
204 result = M::act_agg(&result, &self.lazy[left_index])?;
205 }
206 Some(result)
207 })() {
208 return result;
209 }
210 let mut l = range.start + self.n;
211 let mut r = range.end + self.n;
212 self.propagate(l);
213 self.propagate(r - 1);
214 let mut vl = M::agg_unit();
215 let mut vr = M::agg_unit();
216 while l < r {
217 if l & 1 != 0 {
218 vl = M::agg_operate(&vl, &self.seg[l]);
219 l += 1;
220 }
221 if r & 1 != 0 {
222 r -= 1;
223 vr = M::agg_operate(&self.seg[r], &vr);
224 }
225 l /= 2;
226 r /= 2;
227 }
228 M::agg_operate(&vl, &vr)
229 }
230 pub fn set(&mut self, k: usize, x: M::Agg) {
231 assert!(k < self.len);
232 let k = k + self.n;
233 self.propagate(k);
234 self.seg[k] = x;
235 self.recalc(k);
236 }
237 pub fn get(&mut self, k: usize) -> M::Agg {
238 self.fold(k..k + 1)
239 }
240 pub fn fold_all(&self) -> M::Agg {
241 self.seg[1].clone()
242 }
243 pub fn partition_point_acc<P>(&mut self, left: usize, mut pred: P) -> usize
244 where
245 P: FnMut(&M::Agg) -> bool,
246 {
247 let mut acc = M::agg_unit();
248 if left == self.len {
249 return self.len;
250 }
251 let mut k = left + self.n;
252 self.propagate(k);
253 loop {
254 while k & 1 == 0 {
255 k >>= 1;
256 }
257 let nacc = M::agg_operate(&acc, &self.seg[k]);
258 if !pred(&nacc) {
259 while k < self.n {
260 self.propagate_at(k);
261 k <<= 1;
262 let nacc = M::agg_operate(&acc, &self.seg[k]);
263 if pred(&nacc) {
264 acc = nacc;
265 k += 1;
266 }
267 }
268 return k - self.n;
269 }
270 acc = nacc;
271 k += 1;
272 if k.is_power_of_two() {
273 return self.len;
274 }
275 }
276 }
277 pub fn rpartition_point_acc<P>(&mut self, right: usize, mut pred: P) -> usize
278 where
279 P: FnMut(&M::Agg) -> bool,
280 {
281 let mut acc = M::agg_unit();
282 if right == 0 {
283 return 0;
284 }
285 let mut k = right + self.n;
286 self.propagate(k - 1);
287 loop {
288 k -= 1;
289 while k > 1 && k & 1 != 0 {
290 k >>= 1;
291 }
292 let nacc = M::agg_operate(&self.seg[k], &acc);
293 if !pred(&nacc) {
294 while k < self.n {
295 self.propagate_at(k);
296 k = 2 * k + 1;
297 let nacc = M::agg_operate(&self.seg[k], &acc);
298 if pred(&nacc) {
299 acc = nacc;
300 k -= 1;
301 }
302 }
303 return k + 1 - self.n;
304 }
305 acc = nacc;
306 if k.is_power_of_two() {
307 return 0;
308 }
309 }
310 }Sourcefn act_unit() -> Self::Act
fn act_unit() -> Self::Act
Examples found in repository?
crates/competitive/src/data_structure/lazy_segment_tree_map.rs (line 52)
51 fn get_mut(&mut self, k: usize) -> &mut (M::Agg, M::Act) {
52 self.seg.entry(k).or_insert((M::agg_unit(), M::act_unit()))
53 }
54 #[inline]
55 fn update_at(&mut self, k: usize, x: &M::Act) {
56 if M::is_act_unit(x) {
57 return;
58 }
59 let n = self.n;
60 let a = self.get_mut(k);
61 let nx = M::act_agg(&a.0, x);
62 if k < n {
63 a.1 = M::act_operate(&a.1, x);
64 }
65 if let Some(nx) = nx {
66 a.0 = nx;
67 } else if k < n {
68 self.propagate_at(k);
69 self.recalc_at(k);
70 } else {
71 panic!("act failed on leaf");
72 }
73 }
74 #[inline]
75 fn recalc_at(&mut self, k: usize) {
76 let x = match (self.seg.get(&(2 * k)), self.seg.get(&(2 * k + 1))) {
77 (None, None) => M::agg_unit(),
78 (None, Some((y, _))) => y.clone(),
79 (Some((x, _)), None) => x.clone(),
80 (Some((x, _)), Some((y, _))) => M::agg_operate(x, y),
81 };
82 self.get_mut(k).0 = x;
83 }
84 #[inline]
85 fn propagate_at(&mut self, k: usize) {
86 debug_assert!(k < self.n);
87 let x = match self.seg.get_mut(&k) {
88 Some((_, x)) => replace(x, M::act_unit()),
89 None => M::act_unit(),
90 };
91 if M::is_act_unit(&x) {
92 return;
93 }
94 self.update_at(2 * k, &x);
95 self.update_at(2 * k + 1, &x);
96 }
97 #[inline]
98 fn propagate(&mut self, k: usize, right: bool, nofilt: bool) {
99 let right = right as usize;
100 for i in (1..(k + 1 - right).next_power_of_two().trailing_zeros()).rev() {
101 if nofilt || (k >> i) << i != k {
102 self.propagate_at((k - right) >> i);
103 }
104 }
105 }
106 #[inline]
107 fn recalc(&mut self, k: usize, right: bool, nofilt: bool) {
108 let right = right as usize;
109 for i in 1..(k + 1 - right).next_power_of_two().trailing_zeros() {
110 if nofilt || (k >> i) << i != k {
111 self.recalc_at((k - right) >> i);
112 }
113 }
114 }
115 pub fn update<R>(&mut self, range: R, x: M::Act)
116 where
117 R: RangeBounds<usize>,
118 {
119 let range = range.to_range_bounded(0, self.n).expect("invalid range");
120 if M::is_act_unit(&x) {
121 return;
122 }
123 let mut a = range.start + self.n;
124 let mut b = range.end + self.n;
125 self.propagate(a, false, false);
126 self.propagate(b, true, false);
127 while a < b {
128 if a & 1 != 0 {
129 self.update_at(a, &x);
130 a += 1;
131 }
132 if b & 1 != 0 {
133 b -= 1;
134 self.update_at(b, &x);
135 }
136 a /= 2;
137 b /= 2;
138 }
139 self.recalc(range.start + self.n, false, false);
140 self.recalc(range.end + self.n, true, false);
141 }
142 pub fn fold<R>(&mut self, range: R) -> M::Agg
143 where
144 R: RangeBounds<usize>,
145 {
146 let range = range.to_range_bounded(0, self.n).expect("invalid range");
147 let mut l = range.start + self.n;
148 let mut r = range.end + self.n;
149 self.propagate(l, false, true);
150 self.propagate(r, true, true);
151 let mut vl = M::agg_unit();
152 let mut vr = M::agg_unit();
153 while l < r {
154 if l & 1 != 0 {
155 if let Some((x, _)) = self.seg.get(&l) {
156 vl = M::agg_operate(&vl, x);
157 }
158 l += 1;
159 }
160 if r & 1 != 0 {
161 r -= 1;
162 if let Some((x, _)) = self.seg.get(&r) {
163 vr = M::agg_operate(x, &vr);
164 }
165 }
166 l /= 2;
167 r /= 2;
168 }
169 M::agg_operate(&vl, &vr)
170 }
171 pub fn set(&mut self, k: usize, x: M::Agg) {
172 let k = k + self.n;
173 self.propagate(k, false, true);
174 *self.get_mut(k) = (x, M::act_unit());
175 self.recalc(k, false, true);
176 }More examples
crates/competitive/src/data_structure/binary_search_tree/data.rs (line 139)
134 pub fn from_key(key: L::Key) -> Self {
135 let agg = L::single_agg(&key);
136 Self {
137 key,
138 agg,
139 act: L::act_unit(),
140 }
141 }
142
143 pub fn update_act<Spec>(mut node: BstDataMutRef<'_, Spec>, act: &L::Act)
144 where
145 Spec: BstSpec<Data: BstDataAccess<marker::LazyMap, Value = Self>>,
146 {
147 if L::is_act_unit(act) {
148 return;
149 }
150 L::act_operate_assign(&mut node.data_mut().bst_data_mut().act, act);
151 node.data_mut().bst_data_mut().key =
152 L::act_key(&node.reborrow().into_data().bst_data().key, act);
153 if let Some(nxlazy) = L::act_agg(&node.reborrow().into_data().bst_data().agg, act) {
154 node.data_mut().bst_data_mut().agg = nxlazy;
155 } else {
156 Self::top_down(node.reborrow_datamut());
157 Self::bottom_up(node.reborrow_datamut());
158 }
159 }
160
161 pub fn top_down<Spec>(mut node: BstDataMutRef<'_, Spec>)
162 where
163 Spec: BstSpec<Data: BstDataAccess<marker::LazyMap, Value = Self>>,
164 {
165 if L::is_act_unit(&node.reborrow().into_data().bst_data().act) {
166 return;
167 }
168 let act = replace(&mut node.data_mut().bst_data_mut().act, L::act_unit());
169 if let Ok(left) = node.reborrow_datamut().left().descend() {
170 Self::update_act(left, &act);
171 }
172 if let Ok(right) = node.reborrow_datamut().right().descend() {
173 Self::update_act(right, &act);
174 }
175 }crates/competitive/src/data_structure/binary_trie.rs (line 26)
21 fn new(parent: usize) -> Self {
22 Self {
23 child: [usize::MAX; 2],
24 parent,
25 agg: M::agg_unit(),
26 lazy: M::act_unit(),
27 }
28 }
29}
30
31pub struct BinaryTrie<M>
32where
33 M: LazyMapMonoid,
34{
35 bit_len: usize,
36 max_key: u64,
37 len: usize,
38 xor_mask: u64,
39 nodes: Vec<Node<M>>,
40}
41
42impl<M> BinaryTrie<M>
43where
44 M: LazyMapMonoid,
45{
46 pub fn new(bit_len: usize) -> Self {
47 Self::with_capacity(bit_len, 0)
48 }
49
50 pub fn with_capacity(bit_len: usize, capacity: usize) -> Self {
51 assert!(bit_len <= 64);
52 let max_key = if bit_len == 64 {
53 u64::MAX
54 } else {
55 (1u64 << bit_len) - 1
56 };
57 let mut nodes = Vec::with_capacity(
58 capacity
59 .saturating_mul(bit_len.saturating_add(1))
60 .saturating_add(1),
61 );
62 nodes.push(Node::new(usize::MAX));
63 Self {
64 bit_len,
65 max_key,
66 len: 0,
67 xor_mask: 0,
68 nodes,
69 }
70 }
71
72 pub fn len(&self) -> usize {
73 self.len
74 }
75
76 pub fn is_empty(&self) -> bool {
77 self.len() == 0
78 }
79
80 pub fn clear(&mut self) {
81 self.len = 0;
82 self.xor_mask = 0;
83 self.nodes.clear();
84 self.nodes.push(Node::new(usize::MAX));
85 }
86
87 pub fn set(&mut self, key: u64, value: M::Agg) {
88 self.modify_or_insert(key, |x| *x = value);
89 }
90
91 pub fn modify_or_insert(&mut self, key: u64, f: impl FnOnce(&mut M::Agg)) {
92 assert!(key <= self.max_key);
93 if self.bit_len == 0 {
94 if self.is_empty() {
95 self.len = 1;
96 }
97 f(&mut self.nodes[0].agg);
98 return;
99 }
100
101 let key = key ^ self.xor_mask;
102 let mut inserted = false;
103 let mut node = 0;
104 for d in (0..self.bit_len).rev() {
105 self.push_at(node, d + 1);
106 let bit = ((key >> d) & 1) as usize;
107 if self.nodes[node].child[bit] == usize::MAX {
108 inserted = true;
109 let next = self.nodes.len();
110 self.nodes[node].child[bit] = next;
111 self.nodes.push(Node::new(node));
112 }
113 node = self.nodes[node].child[bit];
114 }
115
116 if inserted {
117 self.len += 1;
118 }
119 self.nodes[node].lazy = M::act_unit();
120 f(&mut self.nodes[node].agg);
121 self.recalc_up(node);
122 }
123
124 pub fn get(&mut self, key: u64) -> Option<M::Agg> {
125 assert!(key <= self.max_key);
126 if self.is_empty() {
127 return None;
128 }
129 if self.bit_len == 0 {
130 return Some(self.nodes[0].agg.clone());
131 }
132
133 let key = key ^ self.xor_mask;
134 let mut node = 0;
135 for d in (0..self.bit_len).rev() {
136 let bit = ((key >> d) & 1) as usize;
137 let next = self.nodes[node].child[bit];
138 if next == usize::MAX {
139 return None;
140 }
141 self.push_at(node, d + 1);
142 node = next;
143 }
144 Some(self.nodes[node].agg.clone())
145 }
146
147 pub fn update<R>(&mut self, range: R, act: M::Act)
148 where
149 R: RangeBounds<u64>,
150 {
151 let Some(range) = self.range_to_bounds(range) else {
152 return;
153 };
154 if self.is_empty() {
155 return;
156 }
157
158 let (ql, qr) = range;
159 if ql == 0 && qr == self.max_key {
160 self.apply_at(0, self.bit_len, &act);
161 return;
162 }
163
164 let mut l = ql;
165 loop {
166 let depth = (l.trailing_zeros() as usize)
167 .min(self.bit_len)
168 .min(63 - (qr - l + 1).leading_zeros() as usize);
169 let r = l | ((1u64 << depth) - 1);
170
171 let mut node = 0;
172 for d in (depth..self.bit_len).rev() {
173 self.push_at(node, d + 1);
174 node = self.nodes[node].child[(((l ^ self.xor_mask) >> d) & 1) as usize];
175 if node == usize::MAX {
176 break;
177 }
178 }
179 if node != usize::MAX {
180 self.apply_at(node, depth, &act);
181 self.recalc_up(node);
182 }
183 if r == qr {
184 break;
185 }
186 l = r + 1;
187 }
188 }
189
190 pub fn fold<R>(&mut self, range: R) -> M::Agg
191 where
192 R: RangeBounds<u64>,
193 {
194 let Some(range) = self.range_to_bounds(range) else {
195 return M::agg_unit();
196 };
197
198 let (ql, qr) = range;
199 if ql == 0 && qr == self.max_key {
200 return self.nodes[0].agg.clone();
201 }
202
203 let mut res = M::agg_unit();
204 let mut l = ql;
205 loop {
206 let depth = (l.trailing_zeros() as usize)
207 .min(self.bit_len)
208 .min(63 - (qr - l + 1).leading_zeros() as usize);
209 let r = l | ((1u64 << depth) - 1);
210
211 let mut node = 0;
212 for d in (depth..self.bit_len).rev() {
213 self.push_at(node, d + 1);
214 node = self.nodes[node].child[(((l ^ self.xor_mask) >> d) & 1) as usize];
215 if node == usize::MAX {
216 break;
217 }
218 }
219 if node != usize::MAX {
220 res = M::agg_operate(&res, &self.nodes[node].agg);
221 }
222 if r == qr {
223 break;
224 }
225 l = r + 1;
226 }
227 res
228 }
229
230 fn apply_at(&mut self, node: usize, depth: usize, act: &M::Act) {
231 if M::is_act_unit(act) {
232 return;
233 }
234 if let Some(agg) = M::act_agg(&self.nodes[node].agg, act) {
235 self.nodes[node].agg = agg;
236 if depth > 0 {
237 M::act_operate_assign(&mut self.nodes[node].lazy, act);
238 }
239 } else if depth == 0 {
240 panic!("act failed on leaf");
241 } else {
242 self.push_at(node, depth);
243 for child in self.nodes[node].child {
244 if child != usize::MAX {
245 self.apply_at(child, depth - 1, act);
246 }
247 }
248 self.recalc_at(node);
249 }
250 }
251
252 fn push_at(&mut self, node: usize, depth: usize) {
253 let act = replace(&mut self.nodes[node].lazy, M::act_unit());
254 if M::is_act_unit(&act) {
255 return;
256 }
257 let child = self.nodes[node].child;
258 for child in child {
259 if child != usize::MAX {
260 self.apply_at(child, depth - 1, &act);
261 }
262 }
263 }crates/competitive/src/data_structure/lazy_segment_tree.rs (line 53)
50 pub fn new(len: usize) -> Self {
51 let n = len.next_power_of_two();
52 let seg = vec![M::agg_unit(); 2 * n];
53 let lazy = vec![M::act_unit(); n];
54 Self { len, n, seg, lazy }
55 }
56 pub fn from_vec(v: Vec<M::Agg>) -> Self {
57 let len = v.len();
58 let n = len.next_power_of_two();
59 let mut seg = vec![M::agg_unit(); 2 * n];
60 for (i, x) in v.into_iter().enumerate() {
61 seg[i + n] = x;
62 }
63 for i in (1..n).rev() {
64 seg[i] = M::agg_operate(&seg[2 * i], &seg[2 * i + 1]);
65 }
66 let lazy = vec![M::act_unit(); n];
67 Self { len, n, seg, lazy }
68 }
69 pub fn from_keys(keys: impl ExactSizeIterator<Item = M::Key>) -> Self {
70 let len = keys.len();
71 let n = len.next_power_of_two();
72 let mut seg = vec![M::agg_unit(); 2 * n];
73 for (i, key) in keys.enumerate() {
74 seg[i + n] = M::single_agg(&key);
75 }
76 for i in (1..n).rev() {
77 seg[i] = M::agg_operate(&seg[2 * i], &seg[2 * i + 1]);
78 }
79 let lazy = vec![M::act_unit(); n];
80 Self { len, n, seg, lazy }
81 }
82 #[inline]
83 fn update_at(&mut self, k: usize, x: &M::Act) {
84 if M::is_act_unit(x) {
85 return;
86 }
87 let nx = M::act_agg(&self.seg[k], x);
88 if k < self.n {
89 self.lazy[k] = M::act_operate(&self.lazy[k], x);
90 }
91 if let Some(nx) = nx {
92 self.seg[k] = nx;
93 } else if k < self.n {
94 self.propagate_at(k);
95 self.recalc_at(k);
96 } else {
97 panic!("act failed on leaf");
98 }
99 }
100 #[inline]
101 fn recalc_at(&mut self, k: usize) {
102 self.seg[k] = M::agg_operate(&self.seg[2 * k], &self.seg[2 * k + 1]);
103 }
104 #[inline]
105 fn propagate_at(&mut self, k: usize) {
106 debug_assert!(k < self.n);
107 let x = replace(&mut self.lazy[k], M::act_unit());
108 if M::is_act_unit(&x) {
109 return;
110 }
111 self.update_at(2 * k, &x);
112 self.update_at(2 * k + 1, &x);
113 }crates/competitive/src/data_structure/implicit_splay_tree.rs (line 114)
112 fn top_down(mut node: BstDataMutRef<'_, Self>) {
113 if !T::is_act_unit(&node.reborrow().into_data().value.act) {
114 let act = replace(&mut node.data_mut().value.act, T::act_unit());
115 if let Ok(left) = node.reborrow_datamut().left().descend() {
116 Self::update_act(left, &act);
117 }
118 if let Ok(right) = node.reborrow_datamut().right().descend() {
119 Self::update_act(right, &act);
120 }
121 }
122 if node.reborrow().into_data().rev {
123 node.data_mut().rev = false;
124 if let Ok(left) = node.reborrow_datamut().left().descend() {
125 Self::reverse(left);
126 }
127 if let Ok(right) = node.reborrow_datamut().right().descend() {
128 Self::reverse(right);
129 }
130 }
131 }Additional examples can be found in:
Sourcefn agg_operate(x: &Self::Agg, y: &Self::Agg) -> Self::Agg
fn agg_operate(x: &Self::Agg, y: &Self::Agg) -> Self::Agg
Examples found in repository?
crates/competitive/src/data_structure/lazy_segment_tree_map.rs (line 80)
75 fn recalc_at(&mut self, k: usize) {
76 let x = match (self.seg.get(&(2 * k)), self.seg.get(&(2 * k + 1))) {
77 (None, None) => M::agg_unit(),
78 (None, Some((y, _))) => y.clone(),
79 (Some((x, _)), None) => x.clone(),
80 (Some((x, _)), Some((y, _))) => M::agg_operate(x, y),
81 };
82 self.get_mut(k).0 = x;
83 }
84 #[inline]
85 fn propagate_at(&mut self, k: usize) {
86 debug_assert!(k < self.n);
87 let x = match self.seg.get_mut(&k) {
88 Some((_, x)) => replace(x, M::act_unit()),
89 None => M::act_unit(),
90 };
91 if M::is_act_unit(&x) {
92 return;
93 }
94 self.update_at(2 * k, &x);
95 self.update_at(2 * k + 1, &x);
96 }
97 #[inline]
98 fn propagate(&mut self, k: usize, right: bool, nofilt: bool) {
99 let right = right as usize;
100 for i in (1..(k + 1 - right).next_power_of_two().trailing_zeros()).rev() {
101 if nofilt || (k >> i) << i != k {
102 self.propagate_at((k - right) >> i);
103 }
104 }
105 }
106 #[inline]
107 fn recalc(&mut self, k: usize, right: bool, nofilt: bool) {
108 let right = right as usize;
109 for i in 1..(k + 1 - right).next_power_of_two().trailing_zeros() {
110 if nofilt || (k >> i) << i != k {
111 self.recalc_at((k - right) >> i);
112 }
113 }
114 }
115 pub fn update<R>(&mut self, range: R, x: M::Act)
116 where
117 R: RangeBounds<usize>,
118 {
119 let range = range.to_range_bounded(0, self.n).expect("invalid range");
120 if M::is_act_unit(&x) {
121 return;
122 }
123 let mut a = range.start + self.n;
124 let mut b = range.end + self.n;
125 self.propagate(a, false, false);
126 self.propagate(b, true, false);
127 while a < b {
128 if a & 1 != 0 {
129 self.update_at(a, &x);
130 a += 1;
131 }
132 if b & 1 != 0 {
133 b -= 1;
134 self.update_at(b, &x);
135 }
136 a /= 2;
137 b /= 2;
138 }
139 self.recalc(range.start + self.n, false, false);
140 self.recalc(range.end + self.n, true, false);
141 }
142 pub fn fold<R>(&mut self, range: R) -> M::Agg
143 where
144 R: RangeBounds<usize>,
145 {
146 let range = range.to_range_bounded(0, self.n).expect("invalid range");
147 let mut l = range.start + self.n;
148 let mut r = range.end + self.n;
149 self.propagate(l, false, true);
150 self.propagate(r, true, true);
151 let mut vl = M::agg_unit();
152 let mut vr = M::agg_unit();
153 while l < r {
154 if l & 1 != 0 {
155 if let Some((x, _)) = self.seg.get(&l) {
156 vl = M::agg_operate(&vl, x);
157 }
158 l += 1;
159 }
160 if r & 1 != 0 {
161 r -= 1;
162 if let Some((x, _)) = self.seg.get(&r) {
163 vr = M::agg_operate(x, &vr);
164 }
165 }
166 l /= 2;
167 r /= 2;
168 }
169 M::agg_operate(&vl, &vr)
170 }
171 pub fn set(&mut self, k: usize, x: M::Agg) {
172 let k = k + self.n;
173 self.propagate(k, false, true);
174 *self.get_mut(k) = (x, M::act_unit());
175 self.recalc(k, false, true);
176 }
177 pub fn get(&mut self, k: usize) -> M::Agg {
178 assert!(k < self.n);
179 let k = k + self.n;
180 self.propagate(k, false, true);
181 self.seg
182 .get(&k)
183 .map(|(x, _)| x.clone())
184 .unwrap_or_else(M::agg_unit)
185 }
186 pub fn fold_all(&mut self) -> M::Agg {
187 self.fold(0..self.n)
188 }
189 fn partition_point_perfect<P>(
190 &mut self,
191 mut pos: usize,
192 mut acc: M::Agg,
193 mut pred: P,
194 ) -> (usize, M::Agg)
195 where
196 P: FnMut(&M::Agg) -> bool,
197 {
198 while pos < self.n {
199 self.propagate_at(pos);
200 pos <<= 1;
201 let nacc = match self.seg.get(&pos) {
202 Some((x, _)) => M::agg_operate(&acc, x),
203 None => acc.clone(),
204 };
205 if pred(&nacc) {
206 acc = nacc;
207 pos += 1;
208 }
209 }
210 (pos - self.n, acc)
211 }
212 fn rpartition_point_perfect<P>(
213 &mut self,
214 mut pos: usize,
215 mut acc: M::Agg,
216 mut pred: P,
217 ) -> (usize, M::Agg)
218 where
219 P: FnMut(&M::Agg) -> bool,
220 {
221 while pos < self.n {
222 self.propagate_at(pos);
223 pos = pos * 2 + 1;
224 let nacc = match self.seg.get(&pos) {
225 Some((x, _)) => M::agg_operate(x, &acc),
226 None => acc.clone(),
227 };
228 if pred(&nacc) {
229 acc = nacc;
230 pos -= 1;
231 }
232 }
233 (pos - self.n, acc)
234 }
235 pub fn partition_point_acc<P>(&mut self, left: usize, mut pred: P) -> usize
236 where
237 P: FnMut(&M::Agg) -> bool,
238 {
239 let mut acc = M::agg_unit();
240 if left == self.n {
241 return self.n;
242 }
243 let mut l = left + self.n;
244 let r = 2 * self.n;
245 self.propagate(l, false, true);
246 self.propagate(r, true, true);
247 let mut k = 0usize;
248 while l < r >> k {
249 if l & 1 != 0 {
250 let nacc = match self.seg.get(&l) {
251 Some((x, _)) => M::agg_operate(&acc, x),
252 None => acc.clone(),
253 };
254 if !pred(&nacc) {
255 return self.partition_point_perfect(l, acc, pred).0;
256 }
257 acc = nacc;
258 l += 1;
259 }
260 l >>= 1;
261 k += 1;
262 }
263 for k in (0..k).rev() {
264 let r = r >> k;
265 if r & 1 != 0 {
266 let nacc = match self.seg.get(&(r - 1)) {
267 Some((x, _)) => M::agg_operate(&acc, x),
268 None => acc.clone(),
269 };
270 if !pred(&nacc) {
271 return self.partition_point_perfect(r - 1, acc, pred).0;
272 }
273 acc = nacc;
274 }
275 }
276 self.n
277 }
278 pub fn rpartition_point_acc<P>(&mut self, right: usize, mut pred: P) -> usize
279 where
280 P: FnMut(&M::Agg) -> bool,
281 {
282 let mut acc = M::agg_unit();
283 if right == 0 {
284 return 0;
285 }
286 let mut l = self.n;
287 let mut r = right + self.n;
288 self.propagate(l, false, true);
289 self.propagate(r, true, true);
290 let mut c = 0usize;
291 let mut k = 0usize;
292 while l >> k < r {
293 c <<= 1;
294 if l & (1 << k) != 0 {
295 l += 1 << k;
296 c += 1;
297 }
298 if r & 1 != 0 {
299 r -= 1;
300 let nacc = match self.seg.get(&r) {
301 Some((x, _)) => M::agg_operate(x, &acc),
302 None => acc.clone(),
303 };
304 if !pred(&nacc) {
305 return self.rpartition_point_perfect(r, acc, pred).0 + 1;
306 }
307 acc = nacc;
308 }
309 r >>= 1;
310 k += 1;
311 }
312 for k in (0..k).rev() {
313 if c & 1 != 0 {
314 l -= 1 << k;
315 let l = l >> k;
316 let nacc = match self.seg.get(&l) {
317 Some((x, _)) => M::agg_operate(x, &acc),
318 None => acc.clone(),
319 };
320 if !pred(&nacc) {
321 return self.rpartition_point_perfect(l, acc, pred).0 + 1;
322 }
323 acc = nacc;
324 }
325 c >>= 1;
326 }
327 0
328 }More examples
crates/competitive/src/data_structure/lazy_segment_tree.rs (line 64)
56 pub fn from_vec(v: Vec<M::Agg>) -> Self {
57 let len = v.len();
58 let n = len.next_power_of_two();
59 let mut seg = vec![M::agg_unit(); 2 * n];
60 for (i, x) in v.into_iter().enumerate() {
61 seg[i + n] = x;
62 }
63 for i in (1..n).rev() {
64 seg[i] = M::agg_operate(&seg[2 * i], &seg[2 * i + 1]);
65 }
66 let lazy = vec![M::act_unit(); n];
67 Self { len, n, seg, lazy }
68 }
69 pub fn from_keys(keys: impl ExactSizeIterator<Item = M::Key>) -> Self {
70 let len = keys.len();
71 let n = len.next_power_of_two();
72 let mut seg = vec![M::agg_unit(); 2 * n];
73 for (i, key) in keys.enumerate() {
74 seg[i + n] = M::single_agg(&key);
75 }
76 for i in (1..n).rev() {
77 seg[i] = M::agg_operate(&seg[2 * i], &seg[2 * i + 1]);
78 }
79 let lazy = vec![M::act_unit(); n];
80 Self { len, n, seg, lazy }
81 }
82 #[inline]
83 fn update_at(&mut self, k: usize, x: &M::Act) {
84 if M::is_act_unit(x) {
85 return;
86 }
87 let nx = M::act_agg(&self.seg[k], x);
88 if k < self.n {
89 self.lazy[k] = M::act_operate(&self.lazy[k], x);
90 }
91 if let Some(nx) = nx {
92 self.seg[k] = nx;
93 } else if k < self.n {
94 self.propagate_at(k);
95 self.recalc_at(k);
96 } else {
97 panic!("act failed on leaf");
98 }
99 }
100 #[inline]
101 fn recalc_at(&mut self, k: usize) {
102 self.seg[k] = M::agg_operate(&self.seg[2 * k], &self.seg[2 * k + 1]);
103 }
104 #[inline]
105 fn propagate_at(&mut self, k: usize) {
106 debug_assert!(k < self.n);
107 let x = replace(&mut self.lazy[k], M::act_unit());
108 if M::is_act_unit(&x) {
109 return;
110 }
111 self.update_at(2 * k, &x);
112 self.update_at(2 * k + 1, &x);
113 }
114 #[inline]
115 fn propagate(&mut self, k: usize) {
116 for i in (1..=self.n.trailing_zeros()).rev() {
117 self.propagate_at(k >> i);
118 }
119 }
120 #[inline]
121 fn recalc(&mut self, mut k: usize) {
122 while k > 1 {
123 k >>= 1;
124 self.recalc_at(k);
125 }
126 }
127 pub fn update<R>(&mut self, range: R, x: M::Act)
128 where
129 R: RangeBounds<usize>,
130 {
131 let range = range.to_range_bounded(0, self.len).expect("invalid range");
132 if range.is_empty() || M::is_act_unit(&x) {
133 return;
134 }
135 let mut a = range.start + self.n;
136 let mut b = range.end + self.n;
137 for i in (1..=self.n.trailing_zeros()).rev() {
138 if (a >> i) << i != a {
139 self.propagate_at(a >> i);
140 }
141 if (b >> i) << i != b {
142 self.propagate_at((b - 1) >> i);
143 }
144 }
145 while a < b {
146 if a & 1 != 0 {
147 self.update_at(a, &x);
148 a += 1;
149 }
150 if b & 1 != 0 {
151 b -= 1;
152 self.update_at(b, &x);
153 }
154 a /= 2;
155 b /= 2;
156 }
157 let a = range.start + self.n;
158 let b = range.end + self.n;
159 for i in 1..=self.n.trailing_zeros() {
160 if (a >> i) << i != a {
161 self.recalc_at(a >> i);
162 }
163 if (b >> i) << i != b {
164 self.recalc_at((b - 1) >> i);
165 }
166 }
167 }
168 pub fn fold<R>(&mut self, range: R) -> M::Agg
169 where
170 R: RangeBounds<usize>,
171 {
172 let range = range.to_range_bounded(0, self.len).expect("invalid range");
173 if range.is_empty() {
174 return M::agg_unit();
175 }
176 if let Some(result) = (|| {
177 let mut left_index = range.start + self.n - 1;
178 let mut right_index = range.end + self.n;
179 let mut left = M::agg_unit();
180 let mut right = M::agg_unit();
181 let mut has_left = false;
182 let mut has_right = false;
183 for _ in 0..(left_index ^ right_index).ilog2() {
184 if left_index & 1 == 0 {
185 left = M::agg_operate(&left, &self.seg[left_index ^ 1]);
186 has_left = true;
187 }
188 if right_index & 1 != 0 {
189 right = M::agg_operate(&self.seg[right_index ^ 1], &right);
190 has_right = true;
191 }
192 left_index >>= 1;
193 right_index >>= 1;
194 if has_left {
195 left = M::act_agg(&left, &self.lazy[left_index])?;
196 }
197 if has_right && right_index < self.n {
198 right = M::act_agg(&right, &self.lazy[right_index])?;
199 }
200 }
201 let mut result = M::agg_operate(&left, &right);
202 while left_index > 1 {
203 left_index >>= 1;
204 result = M::act_agg(&result, &self.lazy[left_index])?;
205 }
206 Some(result)
207 })() {
208 return result;
209 }
210 let mut l = range.start + self.n;
211 let mut r = range.end + self.n;
212 self.propagate(l);
213 self.propagate(r - 1);
214 let mut vl = M::agg_unit();
215 let mut vr = M::agg_unit();
216 while l < r {
217 if l & 1 != 0 {
218 vl = M::agg_operate(&vl, &self.seg[l]);
219 l += 1;
220 }
221 if r & 1 != 0 {
222 r -= 1;
223 vr = M::agg_operate(&self.seg[r], &vr);
224 }
225 l /= 2;
226 r /= 2;
227 }
228 M::agg_operate(&vl, &vr)
229 }
230 pub fn set(&mut self, k: usize, x: M::Agg) {
231 assert!(k < self.len);
232 let k = k + self.n;
233 self.propagate(k);
234 self.seg[k] = x;
235 self.recalc(k);
236 }
237 pub fn get(&mut self, k: usize) -> M::Agg {
238 self.fold(k..k + 1)
239 }
240 pub fn fold_all(&self) -> M::Agg {
241 self.seg[1].clone()
242 }
243 pub fn partition_point_acc<P>(&mut self, left: usize, mut pred: P) -> usize
244 where
245 P: FnMut(&M::Agg) -> bool,
246 {
247 let mut acc = M::agg_unit();
248 if left == self.len {
249 return self.len;
250 }
251 let mut k = left + self.n;
252 self.propagate(k);
253 loop {
254 while k & 1 == 0 {
255 k >>= 1;
256 }
257 let nacc = M::agg_operate(&acc, &self.seg[k]);
258 if !pred(&nacc) {
259 while k < self.n {
260 self.propagate_at(k);
261 k <<= 1;
262 let nacc = M::agg_operate(&acc, &self.seg[k]);
263 if pred(&nacc) {
264 acc = nacc;
265 k += 1;
266 }
267 }
268 return k - self.n;
269 }
270 acc = nacc;
271 k += 1;
272 if k.is_power_of_two() {
273 return self.len;
274 }
275 }
276 }
277 pub fn rpartition_point_acc<P>(&mut self, right: usize, mut pred: P) -> usize
278 where
279 P: FnMut(&M::Agg) -> bool,
280 {
281 let mut acc = M::agg_unit();
282 if right == 0 {
283 return 0;
284 }
285 let mut k = right + self.n;
286 self.propagate(k - 1);
287 loop {
288 k -= 1;
289 while k > 1 && k & 1 != 0 {
290 k >>= 1;
291 }
292 let nacc = M::agg_operate(&self.seg[k], &acc);
293 if !pred(&nacc) {
294 while k < self.n {
295 self.propagate_at(k);
296 k = 2 * k + 1;
297 let nacc = M::agg_operate(&self.seg[k], &acc);
298 if pred(&nacc) {
299 acc = nacc;
300 k -= 1;
301 }
302 }
303 return k + 1 - self.n;
304 }
305 acc = nacc;
306 if k.is_power_of_two() {
307 return 0;
308 }
309 }
310 }crates/competitive/src/data_structure/binary_search_tree/data.rs (line 183)
177 pub fn bottom_up<Spec>(mut node: BstDataMutRef<'_, Spec>)
178 where
179 Spec: BstSpec<Data: BstDataAccess<marker::LazyMap, Value = Self>>,
180 {
181 let mut agg = L::single_agg(&node.reborrow().into_data().bst_data().key);
182 if let Ok(left) = node.reborrow().left().descend() {
183 agg = L::agg_operate(&left.into_data().bst_data().agg, &agg);
184 }
185 if let Ok(right) = node.reborrow().right().descend() {
186 agg = L::agg_operate(&agg, &right.into_data().bst_data().agg);
187 }
188 node.data_mut().bst_data_mut().agg = agg;
189 }crates/competitive/src/data_structure/implicit_splay_tree.rs (line 138)
133 fn bottom_up(mut node: BstDataMutRef<'_, Self>) {
134 let mut agg = T::single_agg(&node.reborrow().into_data().value.key);
135 let mut size = 1;
136 if let Ok(left) = node.reborrow().left().descend() {
137 let data = left.into_data();
138 agg = T::agg_operate(&data.value.agg, &agg);
139 size += data.size;
140 }
141 if let Ok(right) = node.reborrow().right().descend() {
142 let data = right.into_data();
143 agg = T::agg_operate(&agg, &data.value.agg);
144 size += data.size;
145 }
146 let data = node.data_mut();
147 data.value.agg = agg;
148 data.size = size;
149 }crates/competitive/src/data_structure/implicit_treap.rs (line 139)
134 fn bottom_up(mut node: BstDataMutRef<'_, Self>) {
135 let mut agg = T::single_agg(&node.reborrow().into_data().value.key);
136 let mut size = 1;
137 if let Ok(left) = node.reborrow().left().descend() {
138 let data = left.into_data();
139 agg = T::agg_operate(&data.value.agg, &agg);
140 size += data.size;
141 }
142 if let Ok(right) = node.reborrow().right().descend() {
143 let data = right.into_data();
144 agg = T::agg_operate(&agg, &data.value.agg);
145 size += data.size;
146 }
147 let data = node.data_mut();
148 data.value.agg = agg;
149 data.size = size;
150 }Additional examples can be found in:
Sourcefn act_operate(x: &Self::Act, y: &Self::Act) -> Self::Act
fn act_operate(x: &Self::Act, y: &Self::Act) -> Self::Act
Examples found in repository?
crates/competitive/src/data_structure/lazy_segment_tree.rs (line 89)
83 fn update_at(&mut self, k: usize, x: &M::Act) {
84 if M::is_act_unit(x) {
85 return;
86 }
87 let nx = M::act_agg(&self.seg[k], x);
88 if k < self.n {
89 self.lazy[k] = M::act_operate(&self.lazy[k], x);
90 }
91 if let Some(nx) = nx {
92 self.seg[k] = nx;
93 } else if k < self.n {
94 self.propagate_at(k);
95 self.recalc_at(k);
96 } else {
97 panic!("act failed on leaf");
98 }
99 }More examples
crates/competitive/src/data_structure/lazy_segment_tree_map.rs (line 63)
55 fn update_at(&mut self, k: usize, x: &M::Act) {
56 if M::is_act_unit(x) {
57 return;
58 }
59 let n = self.n;
60 let a = self.get_mut(k);
61 let nx = M::act_agg(&a.0, x);
62 if k < n {
63 a.1 = M::act_operate(&a.1, x);
64 }
65 if let Some(nx) = nx {
66 a.0 = nx;
67 } else if k < n {
68 self.propagate_at(k);
69 self.recalc_at(k);
70 } else {
71 panic!("act failed on leaf");
72 }
73 }fn agg_operate_assign(x: &mut Self::Agg, y: &Self::Agg)
Sourcefn act_operate_assign(x: &mut Self::Act, y: &Self::Act)
fn act_operate_assign(x: &mut Self::Act, y: &Self::Act)
Examples found in repository?
More examples
crates/competitive/src/data_structure/implicit_splay_tree.rs (line 87)
83 fn update_act(mut node: BstDataMutRef<'_, Self>, act: &T::Act) {
84 if T::is_act_unit(act) {
85 return;
86 }
87 T::act_operate_assign(&mut node.data_mut().value.act, act);
88 node.data_mut().value.key = T::act_key(&node.reborrow().into_data().value.key, act);
89 if let Some(agg) = T::act_agg(&node.reborrow().into_data().value.agg, act) {
90 node.data_mut().value.agg = agg;
91 } else {
92 Self::top_down(node.reborrow_datamut());
93 Self::bottom_up(node);
94 }
95 }crates/competitive/src/data_structure/implicit_treap.rs (line 88)
84 fn update_act(mut node: BstDataMutRef<'_, Self>, act: &T::Act) {
85 if T::is_act_unit(act) {
86 return;
87 }
88 T::act_operate_assign(&mut node.data_mut().value.act, act);
89 node.data_mut().value.key = T::act_key(&node.reborrow().into_data().value.key, act);
90 if let Some(agg) = T::act_agg(&node.reborrow().into_data().value.agg, act) {
91 node.data_mut().value.agg = agg;
92 } else {
93 Self::top_down(node.reborrow_datamut());
94 Self::bottom_up(node);
95 }
96 }crates/competitive/src/data_structure/binary_trie.rs (line 237)
230 fn apply_at(&mut self, node: usize, depth: usize, act: &M::Act) {
231 if M::is_act_unit(act) {
232 return;
233 }
234 if let Some(agg) = M::act_agg(&self.nodes[node].agg, act) {
235 self.nodes[node].agg = agg;
236 if depth > 0 {
237 M::act_operate_assign(&mut self.nodes[node].lazy, act);
238 }
239 } else if depth == 0 {
240 panic!("act failed on leaf");
241 } else {
242 self.push_at(node, depth);
243 for child in self.nodes[node].child {
244 if child != usize::MAX {
245 self.apply_at(child, depth - 1, act);
246 }
247 }
248 self.recalc_at(node);
249 }
250 }crates/competitive/src/data_structure/binary_search_tree/data.rs (line 150)
143 pub fn update_act<Spec>(mut node: BstDataMutRef<'_, Spec>, act: &L::Act)
144 where
145 Spec: BstSpec<Data: BstDataAccess<marker::LazyMap, Value = Self>>,
146 {
147 if L::is_act_unit(act) {
148 return;
149 }
150 L::act_operate_assign(&mut node.data_mut().bst_data_mut().act, act);
151 node.data_mut().bst_data_mut().key =
152 L::act_key(&node.reborrow().into_data().bst_data().key, act);
153 if let Some(nxlazy) = L::act_agg(&node.reborrow().into_data().bst_data().agg, act) {
154 node.data_mut().bst_data_mut().agg = nxlazy;
155 } else {
156 Self::top_down(node.reborrow_datamut());
157 Self::bottom_up(node.reborrow_datamut());
158 }
159 }Dyn Compatibility§
This trait is not dyn compatible.
In older versions of Rust, dyn compatibility was called "object safety".