pub trait MonoidAction {
type Key;
type Agg: Clone;
type Act: Clone;
type AggMonoid: Monoid<T = Self::Agg>;
type ActMonoid: Monoid<T = Self::Act>;
// Required methods
fn single_agg(key: &Self::Key) -> Self::Agg;
fn act_key(x: &Self::Key, a: &Self::Act) -> Self::Key;
fn act_agg(x: &Self::Agg, a: &Self::Act) -> Option<Self::Agg>;
// Provided methods
fn toggle(_x: &mut Self::Agg) { ... }
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
type AggMonoid: Monoid<T = Self::Agg>
type ActMonoid: Monoid<T = Self::Act>
Required Methods§
fn single_agg(key: &Self::Key) -> Self::Agg
fn act_key(x: &Self::Key, a: &Self::Act) -> Self::Key
fn act_agg(x: &Self::Agg, a: &Self::Act) -> Option<Self::Agg>
Provided Methods§
Sourcefn agg_unit() -> Self::Agg
fn agg_unit() -> Self::Agg
Examples found in repository?
crates/competitive/src/data_structure/lazy_segment_tree.rs (line 47)
46 pub fn new(n: usize) -> Self {
47 let seg = vec![(M::agg_unit(), M::act_unit()); 2 * n];
48 Self { n, seg }
49 }
50 pub fn from_vec(v: Vec<M::Agg>) -> Self {
51 let n = v.len();
52 let mut seg = vec![(M::agg_unit(), M::act_unit()); 2 * n];
53 for (i, x) in v.into_iter().enumerate() {
54 seg[i + n].0 = x;
55 }
56 for i in (1..n).rev() {
57 seg[i].0 = M::agg_operate(&seg[2 * i].0, &seg[2 * i + 1].0);
58 }
59 Self { n, seg }
60 }
61 pub fn from_keys(keys: impl ExactSizeIterator<Item = M::Key>) -> Self {
62 let n = keys.len();
63 let mut seg = vec![(M::agg_unit(), M::act_unit()); 2 * n];
64 for (i, key) in keys.enumerate() {
65 seg[i + n].0 = M::single_agg(&key);
66 }
67 for i in (1..n).rev() {
68 seg[i].0 = M::agg_operate(&seg[2 * i].0, &seg[2 * i + 1].0);
69 }
70 Self { n, seg }
71 }
72 #[inline]
73 fn update_at(&mut self, k: usize, x: &M::Act) {
74 let nx = M::act_agg(&self.seg[k].0, x);
75 if k < self.n {
76 self.seg[k].1 = M::act_operate(&self.seg[k].1, x);
77 }
78 if let Some(nx) = nx {
79 self.seg[k].0 = nx;
80 } else if k < self.n {
81 self.propagate_at(k);
82 self.recalc_at(k);
83 } else {
84 panic!("act failed on leaf");
85 }
86 }
87 #[inline]
88 fn recalc_at(&mut self, k: usize) {
89 self.seg[k].0 = M::agg_operate(&self.seg[2 * k].0, &self.seg[2 * k + 1].0);
90 }
91 #[inline]
92 fn propagate_at(&mut self, k: usize) {
93 debug_assert!(k < self.n);
94 let x = replace(&mut self.seg[k].1, M::act_unit());
95 self.update_at(2 * k, &x);
96 self.update_at(2 * k + 1, &x);
97 }
98 #[inline]
99 fn propagate(&mut self, k: usize, right: bool, nofilt: bool) {
100 let right = right as usize;
101 for i in (1..(k + 1 - right).next_power_of_two().trailing_zeros()).rev() {
102 if nofilt || (k >> i) << i != k {
103 self.propagate_at((k - right) >> i);
104 }
105 }
106 }
107 #[inline]
108 fn recalc(&mut self, k: usize, right: bool, nofilt: bool) {
109 let right = right as usize;
110 for i in 1..(k + 1 - right).next_power_of_two().trailing_zeros() {
111 if nofilt || (k >> i) << i != k {
112 self.recalc_at((k - right) >> i);
113 }
114 }
115 }
116 pub fn update<R>(&mut self, range: R, x: M::Act)
117 where
118 R: RangeBounds<usize>,
119 {
120 let range = range.to_range_bounded(0, self.n).expect("invalid range");
121 let mut a = range.start + self.n;
122 let mut b = range.end + self.n;
123 self.propagate(a, false, false);
124 self.propagate(b, true, false);
125 while a < b {
126 if a & 1 != 0 {
127 self.update_at(a, &x);
128 a += 1;
129 }
130 if b & 1 != 0 {
131 b -= 1;
132 self.update_at(b, &x);
133 }
134 a /= 2;
135 b /= 2;
136 }
137 self.recalc(range.start + self.n, false, false);
138 self.recalc(range.end + self.n, true, false);
139 }
140 pub fn fold<R>(&mut self, range: R) -> M::Agg
141 where
142 R: RangeBounds<usize>,
143 {
144 let range = range.to_range_bounded(0, self.n).expect("invalid range");
145 let mut l = range.start + self.n;
146 let mut r = range.end + self.n;
147 self.propagate(l, false, true);
148 self.propagate(r, true, true);
149 let mut vl = M::agg_unit();
150 let mut vr = M::agg_unit();
151 while l < r {
152 if l & 1 != 0 {
153 vl = M::agg_operate(&vl, &self.seg[l].0);
154 l += 1;
155 }
156 if r & 1 != 0 {
157 r -= 1;
158 vr = M::agg_operate(&self.seg[r].0, &vr);
159 }
160 l /= 2;
161 r /= 2;
162 }
163 M::agg_operate(&vl, &vr)
164 }
165 pub fn set(&mut self, k: usize, x: M::Agg) {
166 let k = k + self.n;
167 self.propagate(k, false, true);
168 self.seg[k] = (x, M::act_unit());
169 self.recalc(k, false, true);
170 }
171 pub fn get(&mut self, k: usize) -> M::Agg {
172 self.fold(k..k + 1)
173 }
174 pub fn fold_all(&mut self) -> M::Agg {
175 self.fold(0..self.n)
176 }
177 fn bisect_perfect<P>(&mut self, mut pos: usize, mut acc: M::Agg, p: P) -> (usize, M::Agg)
178 where
179 P: Fn(&M::Agg) -> bool,
180 {
181 while pos < self.n {
182 self.propagate_at(pos);
183 pos <<= 1;
184 let nacc = M::agg_operate(&acc, &self.seg[pos].0);
185 if !p(&nacc) {
186 acc = nacc;
187 pos += 1;
188 }
189 }
190 (pos - self.n, acc)
191 }
192 fn rbisect_perfect<P>(&mut self, mut pos: usize, mut acc: M::Agg, p: P) -> (usize, M::Agg)
193 where
194 P: Fn(&M::Agg) -> bool,
195 {
196 while pos < self.n {
197 self.propagate_at(pos);
198 pos = pos * 2 + 1;
199 let nacc = M::agg_operate(&self.seg[pos].0, &acc);
200 if !p(&nacc) {
201 acc = nacc;
202 pos -= 1;
203 }
204 }
205 (pos - self.n, acc)
206 }
207 /// Returns the first index that satisfies a accumlative predicate.
208 pub fn position_acc<R, P>(&mut self, range: R, p: P) -> Option<usize>
209 where
210 R: RangeBounds<usize>,
211 P: Fn(&M::Agg) -> bool,
212 {
213 let range = range.to_range_bounded(0, self.n).expect("invalid range");
214 let mut l = range.start + self.n;
215 let r = range.end + self.n;
216 self.propagate(l, false, true);
217 self.propagate(r, true, true);
218 let mut k = 0usize;
219 let mut acc = M::agg_unit();
220 while l < r >> k {
221 if l & 1 != 0 {
222 let nacc = M::agg_operate(&acc, &self.seg[l].0);
223 if p(&nacc) {
224 return Some(self.bisect_perfect(l, acc, p).0);
225 }
226 acc = nacc;
227 l += 1;
228 }
229 l >>= 1;
230 k += 1;
231 }
232 for k in (0..k).rev() {
233 let r = r >> k;
234 if r & 1 != 0 {
235 let nacc = M::agg_operate(&acc, &self.seg[r - 1].0);
236 if p(&nacc) {
237 return Some(self.bisect_perfect(r - 1, acc, p).0);
238 }
239 acc = nacc;
240 }
241 }
242 None
243 }
244 /// Returns the last index that satisfies a accumlative predicate.
245 pub fn rposition_acc<R, P>(&mut self, range: R, p: P) -> Option<usize>
246 where
247 R: RangeBounds<usize>,
248 P: Fn(&M::Agg) -> bool,
249 {
250 let range = range.to_range_bounded(0, self.n).expect("invalid range");
251 let mut l = range.start + self.n;
252 let mut r = range.end + self.n;
253 self.propagate(l, false, true);
254 self.propagate(r, true, true);
255 let mut c = 0usize;
256 let mut k = 0usize;
257 let mut acc = M::agg_unit();
258 while l >> k < r {
259 c <<= 1;
260 if l & (1 << k) != 0 {
261 l += 1 << k;
262 c += 1;
263 }
264 if r & 1 != 0 {
265 r -= 1;
266 let nacc = M::agg_operate(&self.seg[r].0, &acc);
267 if p(&nacc) {
268 return Some(self.rbisect_perfect(r, acc, p).0);
269 }
270 acc = nacc;
271 }
272 r >>= 1;
273 k += 1;
274 }
275 for k in (0..k).rev() {
276 if c & 1 != 0 {
277 l -= 1 << k;
278 let l = l >> k;
279 let nacc = M::agg_operate(&self.seg[l].0, &acc);
280 if p(&nacc) {
281 return Some(self.rbisect_perfect(l, acc, p).0);
282 }
283 acc = nacc;
284 }
285 c >>= 1;
286 }
287 None
288 }More examples
crates/competitive/src/data_structure/lazy_segment_tree_map.rs (line 58)
57 fn get_mut(&mut self, k: usize) -> &mut (M::Agg, M::Act) {
58 self.seg.entry(k).or_insert((M::agg_unit(), M::act_unit()))
59 }
60 #[inline]
61 fn update_at(&mut self, k: usize, x: &M::Act) {
62 let n = self.n;
63 let a = self.get_mut(k);
64 let nx = M::act_agg(&a.0, x);
65 if k < n {
66 a.1 = M::act_operate(&a.1, x);
67 }
68 if let Some(nx) = nx {
69 a.0 = nx;
70 } else if k < n {
71 self.propagate_at(k);
72 self.recalc_at(k);
73 } else {
74 panic!("act failed on leaf");
75 }
76 }
77 #[inline]
78 fn recalc_at(&mut self, k: usize) {
79 let x = match (self.seg.get(&(2 * k)), self.seg.get(&(2 * k + 1))) {
80 (None, None) => M::agg_unit(),
81 (None, Some((y, _))) => y.clone(),
82 (Some((x, _)), None) => x.clone(),
83 (Some((x, _)), Some((y, _))) => M::agg_operate(x, y),
84 };
85 self.get_mut(k).0 = x;
86 }
87 #[inline]
88 fn propagate_at(&mut self, k: usize) {
89 debug_assert!(k < self.n);
90 let x = match self.seg.get_mut(&k) {
91 Some((_, x)) => replace(x, M::act_unit()),
92 None => M::act_unit(),
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 let mut a = range.start + self.n;
121 let mut b = range.end + self.n;
122 self.propagate(a, false, false);
123 self.propagate(b, true, false);
124 while a < b {
125 if a & 1 != 0 {
126 self.update_at(a, &x);
127 a += 1;
128 }
129 if b & 1 != 0 {
130 b -= 1;
131 self.update_at(b, &x);
132 }
133 a /= 2;
134 b /= 2;
135 }
136 self.recalc(range.start + self.n, false, false);
137 self.recalc(range.end + self.n, true, false);
138 }
139 pub fn fold<R>(&mut self, range: R) -> M::Agg
140 where
141 R: RangeBounds<usize>,
142 {
143 let range = range.to_range_bounded(0, self.n).expect("invalid range");
144 let mut l = range.start + self.n;
145 let mut r = range.end + self.n;
146 self.propagate(l, false, true);
147 self.propagate(r, true, true);
148 let mut vl = M::agg_unit();
149 let mut vr = M::agg_unit();
150 while l < r {
151 if l & 1 != 0 {
152 if let Some((x, _)) = self.seg.get(&l) {
153 vl = M::agg_operate(&vl, x);
154 }
155 l += 1;
156 }
157 if r & 1 != 0 {
158 r -= 1;
159 if let Some((x, _)) = self.seg.get(&r) {
160 vr = M::agg_operate(x, &vr);
161 }
162 }
163 l /= 2;
164 r /= 2;
165 }
166 M::agg_operate(&vl, &vr)
167 }
168 pub fn set(&mut self, k: usize, x: M::Agg) {
169 let k = k + self.n;
170 self.propagate(k, false, true);
171 *self.get_mut(k) = (x, M::act_unit());
172 self.recalc(k, false, true);
173 }
174 pub fn get(&mut self, k: usize) -> M::Agg {
175 self.fold(k..k + 1)
176 }
177 pub fn fold_all(&mut self) -> M::Agg {
178 self.fold(0..self.n)
179 }
180 fn bisect_perfect<P>(&mut self, mut pos: usize, mut acc: M::Agg, p: P) -> (usize, M::Agg)
181 where
182 P: Fn(&M::Agg) -> bool,
183 {
184 while pos < self.n {
185 self.propagate_at(pos);
186 pos <<= 1;
187 let nacc = match self.seg.get(&pos) {
188 Some((x, _)) => M::agg_operate(&acc, x),
189 None => acc.clone(),
190 };
191 if !p(&nacc) {
192 acc = nacc;
193 pos += 1;
194 }
195 }
196 (pos - self.n, acc)
197 }
198 fn rbisect_perfect<P>(&mut self, mut pos: usize, mut acc: M::Agg, p: P) -> (usize, M::Agg)
199 where
200 P: Fn(&M::Agg) -> bool,
201 {
202 while pos < self.n {
203 self.propagate_at(pos);
204 pos = pos * 2 + 1;
205 let nacc = match self.seg.get(&pos) {
206 Some((x, _)) => M::agg_operate(x, &acc),
207 None => acc.clone(),
208 };
209 if !p(&nacc) {
210 acc = nacc;
211 pos -= 1;
212 }
213 }
214 (pos - self.n, acc)
215 }
216 /// Returns the first index that satisfies a accumlative predicate.
217 pub fn position_acc<R, P>(&mut self, range: R, p: P) -> Option<usize>
218 where
219 R: RangeBounds<usize>,
220 P: Fn(&M::Agg) -> bool,
221 {
222 let range = range.to_range_bounded(0, self.n).expect("invalid range");
223 let mut l = range.start + self.n;
224 let r = range.end + self.n;
225 self.propagate(l, false, true);
226 self.propagate(r, true, true);
227 let mut k = 0usize;
228 let mut acc = M::agg_unit();
229 while l < r >> k {
230 if l & 1 != 0 {
231 let nacc = match self.seg.get(&l) {
232 Some((x, _)) => M::agg_operate(&acc, x),
233 None => acc.clone(),
234 };
235 if p(&nacc) {
236 return Some(self.bisect_perfect(l, acc, p).0);
237 }
238 acc = nacc;
239 l += 1;
240 }
241 l >>= 1;
242 k += 1;
243 }
244 for k in (0..k).rev() {
245 let r = r >> k;
246 if r & 1 != 0 {
247 let nacc = match self.seg.get(&(r - 1)) {
248 Some((x, _)) => M::agg_operate(&acc, x),
249 None => acc.clone(),
250 };
251 if p(&nacc) {
252 return Some(self.bisect_perfect(r - 1, acc, p).0);
253 }
254 acc = nacc;
255 }
256 }
257 None
258 }
259 /// Returns the last index that satisfies a accumlative predicate.
260 pub fn rposition_acc<R, P>(&mut self, range: R, p: P) -> Option<usize>
261 where
262 R: RangeBounds<usize>,
263 P: Fn(&M::Agg) -> bool,
264 {
265 let range = range.to_range_bounded(0, self.n).expect("invalid range");
266 let mut l = range.start + self.n;
267 let mut r = range.end + self.n;
268 self.propagate(l, false, true);
269 self.propagate(r, true, true);
270 let mut c = 0usize;
271 let mut k = 0usize;
272 let mut acc = M::agg_unit();
273 while l >> k < r {
274 c <<= 1;
275 if l & (1 << k) != 0 {
276 l += 1 << k;
277 c += 1;
278 }
279 if r & 1 != 0 {
280 r -= 1;
281 let nacc = match self.seg.get(&r) {
282 Some((x, _)) => M::agg_operate(x, &acc),
283 None => acc.clone(),
284 };
285 if p(&nacc) {
286 return Some(self.rbisect_perfect(r, acc, p).0);
287 }
288 acc = nacc;
289 }
290 r >>= 1;
291 k += 1;
292 }
293 for k in (0..k).rev() {
294 if c & 1 != 0 {
295 l -= 1 << k;
296 let l = l >> k;
297 let nacc = match self.seg.get(&l) {
298 Some((x, _)) => M::agg_operate(x, &acc),
299 None => acc.clone(),
300 };
301 if p(&nacc) {
302 return Some(self.rbisect_perfect(l, acc, p).0);
303 }
304 acc = nacc;
305 }
306 c >>= 1;
307 }
308 None
309 }crates/competitive/src/data_structure/splay_tree/sequence.rs (line 159)
157 fn new(f: F) -> Self {
158 Self {
159 acc: T::agg_unit(),
160 f,
161 _marker: PhantomData,
162 }
163 }
164}
165impl<F, T> SplaySeeker for SeekByAccCond<F, T>
166where
167 F: FnMut(&T::Agg) -> bool,
168 T: MonoidAction,
169{
170 type S = LazyAggSplay<T>;
171 fn splay_seek(&mut self, node: NodeRef<marker::Immut<'_>, Self::S>) -> Ordering {
172 if let Some(lagg) = node.left().map(|l| &l.data().agg) {
173 let nacc = T::agg_operate(&self.acc, lagg);
174 if (self.f)(&nacc) {
175 return Ordering::Less;
176 }
177 self.acc = nacc;
178 };
179 self.acc = T::agg_operate(&self.acc, &T::single_agg(&node.data().key));
180 if (self.f)(&self.acc) {
181 Ordering::Equal
182 } else {
183 Ordering::Greater
184 }
185 }
186}
187
188struct SeekByRaccCond<F, T>
189where
190 T: MonoidAction,
191{
192 acc: T::Agg,
193 f: F,
194 _marker: PhantomData<fn() -> T>,
195}
196impl<F, T> SeekByRaccCond<F, T>
197where
198 T: MonoidAction,
199{
200 fn new(f: F) -> Self {
201 Self {
202 acc: T::agg_unit(),
203 f,
204 _marker: PhantomData,
205 }
206 }
207}
208impl<F, T> SplaySeeker for SeekByRaccCond<F, T>
209where
210 F: FnMut(&T::Agg) -> bool,
211 T: MonoidAction,
212{
213 type S = LazyAggSplay<T>;
214 fn splay_seek(&mut self, node: NodeRef<marker::Immut<'_>, Self::S>) -> Ordering {
215 if let Some(lagg) = node.right().map(|r| &r.data().agg) {
216 let nacc = T::agg_operate(lagg, &self.acc);
217 if (self.f)(&nacc) {
218 return Ordering::Greater;
219 }
220 self.acc = nacc;
221 };
222 self.acc = T::agg_operate(&T::single_agg(&node.data().key), &self.acc);
223 if (self.f)(&self.acc) {
224 Ordering::Equal
225 } else {
226 Ordering::Less
227 }
228 }
229}
230
231pub struct SplaySequence<T, A = MemoryPool<Node<LazyAggElement<T>>>>
232where
233 T: MonoidAction,
234 A: Allocator<Node<LazyAggElement<T>>>,
235{
236 root: Root<LazyAggSplay<T>>,
237 length: usize,
238 alloc: ManuallyDrop<A>,
239}
240
241impl<T, A> Debug for SplaySequence<T, A>
242where
243 T: MonoidAction,
244 T::Key: Debug,
245 T::Agg: Debug,
246 T::Act: Debug,
247 A: Allocator<Node<LazyAggElement<T>>>,
248{
249 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
250 f.debug_struct("SplayMap")
251 .field("root", &self.root)
252 .field("length", &self.length)
253 .finish()
254 }
255}
256
257impl<T, A> Drop for SplaySequence<T, A>
258where
259 T: MonoidAction,
260 A: Allocator<Node<LazyAggElement<T>>>,
261{
262 fn drop(&mut self) {
263 unsafe {
264 while let Some(node) = self.root.take_first() {
265 self.alloc.deallocate(node.into_dying().into_inner());
266 }
267 ManuallyDrop::drop(&mut self.alloc);
268 }
269 }
270}
271
272impl<T, A> Default for SplaySequence<T, A>
273where
274 T: MonoidAction,
275 A: Allocator<Node<LazyAggElement<T>>> + Default,
276{
277 fn default() -> Self {
278 Self {
279 root: Root::default(),
280 length: 0,
281 alloc: Default::default(),
282 }
283 }
284}
285
286impl<T> SplaySequence<T>
287where
288 T: MonoidAction,
289{
290 pub fn new() -> Self {
291 Default::default()
292 }
293 pub fn with_capacity(capacity: usize) -> Self {
294 Self {
295 root: Root::default(),
296 length: 0,
297 alloc: ManuallyDrop::new(MemoryPool::with_capacity(capacity)),
298 }
299 }
300 pub fn len(&self) -> usize {
301 self.length
302 }
303 pub fn is_empty(&self) -> bool {
304 self.length == 0
305 }
306}
307impl<T, A> SplaySequence<T, A>
308where
309 T: MonoidAction,
310 A: Allocator<Node<LazyAggElement<T>>>,
311{
312 fn range<R>(&mut self, range: R) -> NodeRange<'_, LazyAggSplay<T>>
313 where
314 R: RangeBounds<usize>,
315 {
316 let start = match range.start_bound() {
317 Bound::Included(&index) => Bound::Included(SeekBySize::new(index)),
318 Bound::Excluded(&index) => Bound::Excluded(SeekBySize::new(index)),
319 Bound::Unbounded => Bound::Unbounded,
320 };
321 let end = match range.end_bound() {
322 Bound::Included(&index) => Bound::Included(SeekBySize::new(index)),
323 Bound::Excluded(&index) => Bound::Excluded(SeekBySize::new(index)),
324 Bound::Unbounded => Bound::Unbounded,
325 };
326 self.root.range(start, end)
327 }
328 pub fn update<R>(&mut self, range: R, x: T::Act)
329 where
330 R: RangeBounds<usize>,
331 {
332 if let Some(root) = self.range(range).root_mut().root_data_mut() {
333 LazyAggSplay::<T>::update_lazy(root, &x);
334 }
335 }
336 pub fn fold<R>(&mut self, range: R) -> T::Agg
337 where
338 R: RangeBounds<usize>,
339 {
340 if let Some(root) = self.range(range).root().root() {
341 root.data().agg.clone()
342 } else {
343 T::agg_unit()
344 }
345 }Sourcefn act_unit() -> Self::Act
fn act_unit() -> Self::Act
Examples found in repository?
crates/competitive/src/data_structure/lazy_segment_tree.rs (line 47)
46 pub fn new(n: usize) -> Self {
47 let seg = vec![(M::agg_unit(), M::act_unit()); 2 * n];
48 Self { n, seg }
49 }
50 pub fn from_vec(v: Vec<M::Agg>) -> Self {
51 let n = v.len();
52 let mut seg = vec![(M::agg_unit(), M::act_unit()); 2 * n];
53 for (i, x) in v.into_iter().enumerate() {
54 seg[i + n].0 = x;
55 }
56 for i in (1..n).rev() {
57 seg[i].0 = M::agg_operate(&seg[2 * i].0, &seg[2 * i + 1].0);
58 }
59 Self { n, seg }
60 }
61 pub fn from_keys(keys: impl ExactSizeIterator<Item = M::Key>) -> Self {
62 let n = keys.len();
63 let mut seg = vec![(M::agg_unit(), M::act_unit()); 2 * n];
64 for (i, key) in keys.enumerate() {
65 seg[i + n].0 = M::single_agg(&key);
66 }
67 for i in (1..n).rev() {
68 seg[i].0 = M::agg_operate(&seg[2 * i].0, &seg[2 * i + 1].0);
69 }
70 Self { n, seg }
71 }
72 #[inline]
73 fn update_at(&mut self, k: usize, x: &M::Act) {
74 let nx = M::act_agg(&self.seg[k].0, x);
75 if k < self.n {
76 self.seg[k].1 = M::act_operate(&self.seg[k].1, x);
77 }
78 if let Some(nx) = nx {
79 self.seg[k].0 = nx;
80 } else if k < self.n {
81 self.propagate_at(k);
82 self.recalc_at(k);
83 } else {
84 panic!("act failed on leaf");
85 }
86 }
87 #[inline]
88 fn recalc_at(&mut self, k: usize) {
89 self.seg[k].0 = M::agg_operate(&self.seg[2 * k].0, &self.seg[2 * k + 1].0);
90 }
91 #[inline]
92 fn propagate_at(&mut self, k: usize) {
93 debug_assert!(k < self.n);
94 let x = replace(&mut self.seg[k].1, M::act_unit());
95 self.update_at(2 * k, &x);
96 self.update_at(2 * k + 1, &x);
97 }
98 #[inline]
99 fn propagate(&mut self, k: usize, right: bool, nofilt: bool) {
100 let right = right as usize;
101 for i in (1..(k + 1 - right).next_power_of_two().trailing_zeros()).rev() {
102 if nofilt || (k >> i) << i != k {
103 self.propagate_at((k - right) >> i);
104 }
105 }
106 }
107 #[inline]
108 fn recalc(&mut self, k: usize, right: bool, nofilt: bool) {
109 let right = right as usize;
110 for i in 1..(k + 1 - right).next_power_of_two().trailing_zeros() {
111 if nofilt || (k >> i) << i != k {
112 self.recalc_at((k - right) >> i);
113 }
114 }
115 }
116 pub fn update<R>(&mut self, range: R, x: M::Act)
117 where
118 R: RangeBounds<usize>,
119 {
120 let range = range.to_range_bounded(0, self.n).expect("invalid range");
121 let mut a = range.start + self.n;
122 let mut b = range.end + self.n;
123 self.propagate(a, false, false);
124 self.propagate(b, true, false);
125 while a < b {
126 if a & 1 != 0 {
127 self.update_at(a, &x);
128 a += 1;
129 }
130 if b & 1 != 0 {
131 b -= 1;
132 self.update_at(b, &x);
133 }
134 a /= 2;
135 b /= 2;
136 }
137 self.recalc(range.start + self.n, false, false);
138 self.recalc(range.end + self.n, true, false);
139 }
140 pub fn fold<R>(&mut self, range: R) -> M::Agg
141 where
142 R: RangeBounds<usize>,
143 {
144 let range = range.to_range_bounded(0, self.n).expect("invalid range");
145 let mut l = range.start + self.n;
146 let mut r = range.end + self.n;
147 self.propagate(l, false, true);
148 self.propagate(r, true, true);
149 let mut vl = M::agg_unit();
150 let mut vr = M::agg_unit();
151 while l < r {
152 if l & 1 != 0 {
153 vl = M::agg_operate(&vl, &self.seg[l].0);
154 l += 1;
155 }
156 if r & 1 != 0 {
157 r -= 1;
158 vr = M::agg_operate(&self.seg[r].0, &vr);
159 }
160 l /= 2;
161 r /= 2;
162 }
163 M::agg_operate(&vl, &vr)
164 }
165 pub fn set(&mut self, k: usize, x: M::Agg) {
166 let k = k + self.n;
167 self.propagate(k, false, true);
168 self.seg[k] = (x, M::act_unit());
169 self.recalc(k, false, true);
170 }More examples
crates/competitive/src/data_structure/lazy_segment_tree_map.rs (line 58)
57 fn get_mut(&mut self, k: usize) -> &mut (M::Agg, M::Act) {
58 self.seg.entry(k).or_insert((M::agg_unit(), M::act_unit()))
59 }
60 #[inline]
61 fn update_at(&mut self, k: usize, x: &M::Act) {
62 let n = self.n;
63 let a = self.get_mut(k);
64 let nx = M::act_agg(&a.0, x);
65 if k < n {
66 a.1 = M::act_operate(&a.1, x);
67 }
68 if let Some(nx) = nx {
69 a.0 = nx;
70 } else if k < n {
71 self.propagate_at(k);
72 self.recalc_at(k);
73 } else {
74 panic!("act failed on leaf");
75 }
76 }
77 #[inline]
78 fn recalc_at(&mut self, k: usize) {
79 let x = match (self.seg.get(&(2 * k)), self.seg.get(&(2 * k + 1))) {
80 (None, None) => M::agg_unit(),
81 (None, Some((y, _))) => y.clone(),
82 (Some((x, _)), None) => x.clone(),
83 (Some((x, _)), Some((y, _))) => M::agg_operate(x, y),
84 };
85 self.get_mut(k).0 = x;
86 }
87 #[inline]
88 fn propagate_at(&mut self, k: usize) {
89 debug_assert!(k < self.n);
90 let x = match self.seg.get_mut(&k) {
91 Some((_, x)) => replace(x, M::act_unit()),
92 None => M::act_unit(),
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 let mut a = range.start + self.n;
121 let mut b = range.end + self.n;
122 self.propagate(a, false, false);
123 self.propagate(b, true, false);
124 while a < b {
125 if a & 1 != 0 {
126 self.update_at(a, &x);
127 a += 1;
128 }
129 if b & 1 != 0 {
130 b -= 1;
131 self.update_at(b, &x);
132 }
133 a /= 2;
134 b /= 2;
135 }
136 self.recalc(range.start + self.n, false, false);
137 self.recalc(range.end + self.n, true, false);
138 }
139 pub fn fold<R>(&mut self, range: R) -> M::Agg
140 where
141 R: RangeBounds<usize>,
142 {
143 let range = range.to_range_bounded(0, self.n).expect("invalid range");
144 let mut l = range.start + self.n;
145 let mut r = range.end + self.n;
146 self.propagate(l, false, true);
147 self.propagate(r, true, true);
148 let mut vl = M::agg_unit();
149 let mut vr = M::agg_unit();
150 while l < r {
151 if l & 1 != 0 {
152 if let Some((x, _)) = self.seg.get(&l) {
153 vl = M::agg_operate(&vl, x);
154 }
155 l += 1;
156 }
157 if r & 1 != 0 {
158 r -= 1;
159 if let Some((x, _)) = self.seg.get(&r) {
160 vr = M::agg_operate(x, &vr);
161 }
162 }
163 l /= 2;
164 r /= 2;
165 }
166 M::agg_operate(&vl, &vr)
167 }
168 pub fn set(&mut self, k: usize, x: M::Agg) {
169 let k = k + self.n;
170 self.propagate(k, false, true);
171 *self.get_mut(k) = (x, M::act_unit());
172 self.recalc(k, false, true);
173 }crates/competitive/src/data_structure/splay_tree/sequence.rs (line 65)
64 fn propagate(node: NodeRef<marker::DataMut<'_>, Self>) -> NodeRef<marker::DataMut<'_>, Self> {
65 let lazy = replace(&mut node.data_mut().lazy, T::act_unit());
66 if let Some(left) = node.left() {
67 Self::update_lazy(left, &lazy);
68 }
69 if let Some(right) = node.right() {
70 Self::update_lazy(right, &lazy);
71 }
72 if replace(&mut node.data_mut().rev, false) {
73 if let Some(left) = node.left() {
74 Self::reverse(left);
75 }
76 if let Some(right) = node.right() {
77 Self::reverse(right);
78 }
79 }
80 node
81 }
82 fn recalc(node: NodeRef<marker::DataMut<'_>, Self>) -> NodeRef<marker::DataMut<'_>, Self> {
83 let mut agg = T::single_agg(&node.data().key);
84 let mut size = 1;
85 if let Some(left) = node.left() {
86 let data = left.data();
87 agg = T::agg_operate(&data.agg, &agg);
88 // agg = <T::AggMonoid as Magma>::operate(&data.agg, &agg);
89 size += data.size;
90 }
91 if let Some(right) = node.right() {
92 let data = right.data();
93 agg = T::agg_operate(&agg, &data.agg);
94 size += data.size;
95 }
96 let data = node.data_mut();
97 data.agg = agg;
98 data.size = size;
99 node
100 }
101}
102impl<T> SplaySpec for LazyAggSplay<T>
103where
104 T: MonoidAction,
105{
106 type T = LazyAggElement<T>;
107 fn has_bottom_up() -> bool {
108 true
109 }
110 fn top_down(node: NodeRef<marker::DataMut<'_>, Self>) {
111 Self::propagate(node);
112 }
113 fn bottom_up(node: NodeRef<marker::DataMut<'_>, Self>) {
114 Self::recalc(node);
115 }
116}
117
118struct SeekBySize<T> {
119 index: usize,
120 _marker: PhantomData<fn() -> T>,
121}
122impl<T> SeekBySize<T> {
123 fn new(index: usize) -> Self {
124 Self {
125 index,
126 _marker: PhantomData,
127 }
128 }
129}
130impl<T> SplaySeeker for SeekBySize<T>
131where
132 T: MonoidAction,
133{
134 type S = LazyAggSplay<T>;
135 fn splay_seek(&mut self, node: NodeRef<marker::Immut<'_>, Self::S>) -> Ordering {
136 let lsize = node.left().map(|l| l.data().size).unwrap_or_default();
137 let ord = self.index.cmp(&lsize);
138 if matches!(ord, Ordering::Greater) {
139 self.index -= lsize + 1;
140 }
141 ord
142 }
143}
144
145struct SeekByAccCond<F, T>
146where
147 T: MonoidAction,
148{
149 acc: T::Agg,
150 f: F,
151 _marker: PhantomData<fn() -> T>,
152}
153impl<F, T> SeekByAccCond<F, T>
154where
155 T: MonoidAction,
156{
157 fn new(f: F) -> Self {
158 Self {
159 acc: T::agg_unit(),
160 f,
161 _marker: PhantomData,
162 }
163 }
164}
165impl<F, T> SplaySeeker for SeekByAccCond<F, T>
166where
167 F: FnMut(&T::Agg) -> bool,
168 T: MonoidAction,
169{
170 type S = LazyAggSplay<T>;
171 fn splay_seek(&mut self, node: NodeRef<marker::Immut<'_>, Self::S>) -> Ordering {
172 if let Some(lagg) = node.left().map(|l| &l.data().agg) {
173 let nacc = T::agg_operate(&self.acc, lagg);
174 if (self.f)(&nacc) {
175 return Ordering::Less;
176 }
177 self.acc = nacc;
178 };
179 self.acc = T::agg_operate(&self.acc, &T::single_agg(&node.data().key));
180 if (self.f)(&self.acc) {
181 Ordering::Equal
182 } else {
183 Ordering::Greater
184 }
185 }
186}
187
188struct SeekByRaccCond<F, T>
189where
190 T: MonoidAction,
191{
192 acc: T::Agg,
193 f: F,
194 _marker: PhantomData<fn() -> T>,
195}
196impl<F, T> SeekByRaccCond<F, T>
197where
198 T: MonoidAction,
199{
200 fn new(f: F) -> Self {
201 Self {
202 acc: T::agg_unit(),
203 f,
204 _marker: PhantomData,
205 }
206 }
207}
208impl<F, T> SplaySeeker for SeekByRaccCond<F, T>
209where
210 F: FnMut(&T::Agg) -> bool,
211 T: MonoidAction,
212{
213 type S = LazyAggSplay<T>;
214 fn splay_seek(&mut self, node: NodeRef<marker::Immut<'_>, Self::S>) -> Ordering {
215 if let Some(lagg) = node.right().map(|r| &r.data().agg) {
216 let nacc = T::agg_operate(lagg, &self.acc);
217 if (self.f)(&nacc) {
218 return Ordering::Greater;
219 }
220 self.acc = nacc;
221 };
222 self.acc = T::agg_operate(&T::single_agg(&node.data().key), &self.acc);
223 if (self.f)(&self.acc) {
224 Ordering::Equal
225 } else {
226 Ordering::Less
227 }
228 }
229}
230
231pub struct SplaySequence<T, A = MemoryPool<Node<LazyAggElement<T>>>>
232where
233 T: MonoidAction,
234 A: Allocator<Node<LazyAggElement<T>>>,
235{
236 root: Root<LazyAggSplay<T>>,
237 length: usize,
238 alloc: ManuallyDrop<A>,
239}
240
241impl<T, A> Debug for SplaySequence<T, A>
242where
243 T: MonoidAction,
244 T::Key: Debug,
245 T::Agg: Debug,
246 T::Act: Debug,
247 A: Allocator<Node<LazyAggElement<T>>>,
248{
249 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
250 f.debug_struct("SplayMap")
251 .field("root", &self.root)
252 .field("length", &self.length)
253 .finish()
254 }
255}
256
257impl<T, A> Drop for SplaySequence<T, A>
258where
259 T: MonoidAction,
260 A: Allocator<Node<LazyAggElement<T>>>,
261{
262 fn drop(&mut self) {
263 unsafe {
264 while let Some(node) = self.root.take_first() {
265 self.alloc.deallocate(node.into_dying().into_inner());
266 }
267 ManuallyDrop::drop(&mut self.alloc);
268 }
269 }
270}
271
272impl<T, A> Default for SplaySequence<T, A>
273where
274 T: MonoidAction,
275 A: Allocator<Node<LazyAggElement<T>>> + Default,
276{
277 fn default() -> Self {
278 Self {
279 root: Root::default(),
280 length: 0,
281 alloc: Default::default(),
282 }
283 }
284}
285
286impl<T> SplaySequence<T>
287where
288 T: MonoidAction,
289{
290 pub fn new() -> Self {
291 Default::default()
292 }
293 pub fn with_capacity(capacity: usize) -> Self {
294 Self {
295 root: Root::default(),
296 length: 0,
297 alloc: ManuallyDrop::new(MemoryPool::with_capacity(capacity)),
298 }
299 }
300 pub fn len(&self) -> usize {
301 self.length
302 }
303 pub fn is_empty(&self) -> bool {
304 self.length == 0
305 }
306}
307impl<T, A> SplaySequence<T, A>
308where
309 T: MonoidAction,
310 A: Allocator<Node<LazyAggElement<T>>>,
311{
312 fn range<R>(&mut self, range: R) -> NodeRange<'_, LazyAggSplay<T>>
313 where
314 R: RangeBounds<usize>,
315 {
316 let start = match range.start_bound() {
317 Bound::Included(&index) => Bound::Included(SeekBySize::new(index)),
318 Bound::Excluded(&index) => Bound::Excluded(SeekBySize::new(index)),
319 Bound::Unbounded => Bound::Unbounded,
320 };
321 let end = match range.end_bound() {
322 Bound::Included(&index) => Bound::Included(SeekBySize::new(index)),
323 Bound::Excluded(&index) => Bound::Excluded(SeekBySize::new(index)),
324 Bound::Unbounded => Bound::Unbounded,
325 };
326 self.root.range(start, end)
327 }
328 pub fn update<R>(&mut self, range: R, x: T::Act)
329 where
330 R: RangeBounds<usize>,
331 {
332 if let Some(root) = self.range(range).root_mut().root_data_mut() {
333 LazyAggSplay::<T>::update_lazy(root, &x);
334 }
335 }
336 pub fn fold<R>(&mut self, range: R) -> T::Agg
337 where
338 R: RangeBounds<usize>,
339 {
340 if let Some(root) = self.range(range).root().root() {
341 root.data().agg.clone()
342 } else {
343 T::agg_unit()
344 }
345 }
346 pub fn reverse<R>(&mut self, range: R)
347 where
348 R: RangeBounds<usize>,
349 {
350 if let Some(root) = self.range(range).root_mut().root_data_mut() {
351 LazyAggSplay::<T>::reverse(root);
352 }
353 }
354 pub fn get(&mut self, index: usize) -> Option<&T::Key> {
355 self.root.splay_by(SeekBySize::new(index))?;
356 self.root.root().map(|root| &root.data().key)
357 }
358 pub fn modify<F>(&mut self, index: usize, f: F)
359 where
360 F: FnOnce(&T::Key) -> T::Key,
361 {
362 self.root.splay_by(SeekBySize::new(index)).unwrap();
363 let data = self.root.root_data_mut().unwrap().data_mut();
364 data.key = f(&data.key);
365 LazyAggSplay::<T>::bottom_up(self.root.root_data_mut().unwrap());
366 }
367 pub fn insert(&mut self, index: usize, x: T::Key) {
368 assert!(index <= self.length);
369 self.root.splay_by(SeekBySize::new(index));
370 let agg = T::single_agg(&x);
371 unsafe {
372 let node = NodeRef::from_data(
373 LazyAggElement {
374 key: x,
375 agg,
376 lazy: T::act_unit(),
377 size: 1,
378 rev: false,
379 },
380 self.alloc.deref_mut(),
381 );
382 if index == self.length {
383 self.root.insert_right(node);
384 } else {
385 self.root.insert_left(node);
386 }
387 }
388 self.length += 1;
389 }
390 pub fn remove(&mut self, index: usize) -> Option<T::Key> {
391 if index >= self.length {
392 return None;
393 }
394 self.root.splay_by(SeekBySize::new(index));
395 self.length -= 1;
396 let node = self.root.take_root().unwrap().into_dying();
397 unsafe { Some(node.into_data(self.alloc.deref_mut()).key) }
398 }
399 pub fn position_acc<R, F>(&mut self, range: R, f: F) -> Option<usize>
400 where
401 R: RangeBounds<usize>,
402 F: FnMut(&T::Agg) -> bool,
403 {
404 let mut range = self.range(range);
405 let ord = range.root_mut().splay_by(SeekByAccCond::new(f));
406 if !matches!(ord, Some(Ordering::Equal)) {
407 return None;
408 }
409 let front_size = range.front().size();
410 let left_size = range.root().left_size();
411 Some(front_size + left_size)
412 }
413 pub fn rposition_acc<R, F>(&mut self, range: R, f: F) -> Option<usize>
414 where
415 R: RangeBounds<usize>,
416 F: FnMut(&T::Agg) -> bool,
417 {
418 let mut range = self.range(range);
419 let ord = range.root_mut().splay_by(SeekByRaccCond::new(f));
420 if !matches!(ord, Some(Ordering::Equal)) {
421 return None;
422 }
423 let front_size = range.front().size();
424 let left_size = range.root().left_size();
425 Some(front_size + left_size)
426 }
427 pub fn rotate_left(&mut self, mid: usize) {
428 assert!(mid <= self.length);
429 if mid != 0 || mid != self.length {
430 self.range(mid..).drop_rotate_left()
431 }
432 }
433 pub fn rotate_right(&mut self, k: usize) {
434 assert!(k <= self.length);
435 self.rotate_left(self.length - k);
436 }
437}
438
439impl<T, A> Extend<T::Key> for SplaySequence<T, A>
440where
441 T: MonoidAction,
442 A: Allocator<Node<LazyAggElement<T>>>,
443{
444 fn extend<I>(&mut self, iter: I)
445 where
446 I: IntoIterator<Item = T::Key>,
447 {
448 let nodes: Vec<_> = unsafe {
449 iter.into_iter()
450 .map(|key| {
451 let agg = T::single_agg(&key);
452 NodeRef::from_data(
453 LazyAggElement {
454 key,
455 agg,
456 lazy: T::act_unit(),
457 size: 1,
458 rev: false,
459 },
460 self.alloc.deref_mut(),
461 )
462 })
463 .collect()
464 };
465 self.length += nodes.len();
466 let mut root = unsafe { Root::from_single_nodes(nodes) };
467 self.root.append(&mut root);
468 }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 83)
78 fn recalc_at(&mut self, k: usize) {
79 let x = match (self.seg.get(&(2 * k)), self.seg.get(&(2 * k + 1))) {
80 (None, None) => M::agg_unit(),
81 (None, Some((y, _))) => y.clone(),
82 (Some((x, _)), None) => x.clone(),
83 (Some((x, _)), Some((y, _))) => M::agg_operate(x, y),
84 };
85 self.get_mut(k).0 = x;
86 }
87 #[inline]
88 fn propagate_at(&mut self, k: usize) {
89 debug_assert!(k < self.n);
90 let x = match self.seg.get_mut(&k) {
91 Some((_, x)) => replace(x, M::act_unit()),
92 None => M::act_unit(),
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 let mut a = range.start + self.n;
121 let mut b = range.end + self.n;
122 self.propagate(a, false, false);
123 self.propagate(b, true, false);
124 while a < b {
125 if a & 1 != 0 {
126 self.update_at(a, &x);
127 a += 1;
128 }
129 if b & 1 != 0 {
130 b -= 1;
131 self.update_at(b, &x);
132 }
133 a /= 2;
134 b /= 2;
135 }
136 self.recalc(range.start + self.n, false, false);
137 self.recalc(range.end + self.n, true, false);
138 }
139 pub fn fold<R>(&mut self, range: R) -> M::Agg
140 where
141 R: RangeBounds<usize>,
142 {
143 let range = range.to_range_bounded(0, self.n).expect("invalid range");
144 let mut l = range.start + self.n;
145 let mut r = range.end + self.n;
146 self.propagate(l, false, true);
147 self.propagate(r, true, true);
148 let mut vl = M::agg_unit();
149 let mut vr = M::agg_unit();
150 while l < r {
151 if l & 1 != 0 {
152 if let Some((x, _)) = self.seg.get(&l) {
153 vl = M::agg_operate(&vl, x);
154 }
155 l += 1;
156 }
157 if r & 1 != 0 {
158 r -= 1;
159 if let Some((x, _)) = self.seg.get(&r) {
160 vr = M::agg_operate(x, &vr);
161 }
162 }
163 l /= 2;
164 r /= 2;
165 }
166 M::agg_operate(&vl, &vr)
167 }
168 pub fn set(&mut self, k: usize, x: M::Agg) {
169 let k = k + self.n;
170 self.propagate(k, false, true);
171 *self.get_mut(k) = (x, M::act_unit());
172 self.recalc(k, false, true);
173 }
174 pub fn get(&mut self, k: usize) -> M::Agg {
175 self.fold(k..k + 1)
176 }
177 pub fn fold_all(&mut self) -> M::Agg {
178 self.fold(0..self.n)
179 }
180 fn bisect_perfect<P>(&mut self, mut pos: usize, mut acc: M::Agg, p: P) -> (usize, M::Agg)
181 where
182 P: Fn(&M::Agg) -> bool,
183 {
184 while pos < self.n {
185 self.propagate_at(pos);
186 pos <<= 1;
187 let nacc = match self.seg.get(&pos) {
188 Some((x, _)) => M::agg_operate(&acc, x),
189 None => acc.clone(),
190 };
191 if !p(&nacc) {
192 acc = nacc;
193 pos += 1;
194 }
195 }
196 (pos - self.n, acc)
197 }
198 fn rbisect_perfect<P>(&mut self, mut pos: usize, mut acc: M::Agg, p: P) -> (usize, M::Agg)
199 where
200 P: Fn(&M::Agg) -> bool,
201 {
202 while pos < self.n {
203 self.propagate_at(pos);
204 pos = pos * 2 + 1;
205 let nacc = match self.seg.get(&pos) {
206 Some((x, _)) => M::agg_operate(x, &acc),
207 None => acc.clone(),
208 };
209 if !p(&nacc) {
210 acc = nacc;
211 pos -= 1;
212 }
213 }
214 (pos - self.n, acc)
215 }
216 /// Returns the first index that satisfies a accumlative predicate.
217 pub fn position_acc<R, P>(&mut self, range: R, p: P) -> Option<usize>
218 where
219 R: RangeBounds<usize>,
220 P: Fn(&M::Agg) -> bool,
221 {
222 let range = range.to_range_bounded(0, self.n).expect("invalid range");
223 let mut l = range.start + self.n;
224 let r = range.end + self.n;
225 self.propagate(l, false, true);
226 self.propagate(r, true, true);
227 let mut k = 0usize;
228 let mut acc = M::agg_unit();
229 while l < r >> k {
230 if l & 1 != 0 {
231 let nacc = match self.seg.get(&l) {
232 Some((x, _)) => M::agg_operate(&acc, x),
233 None => acc.clone(),
234 };
235 if p(&nacc) {
236 return Some(self.bisect_perfect(l, acc, p).0);
237 }
238 acc = nacc;
239 l += 1;
240 }
241 l >>= 1;
242 k += 1;
243 }
244 for k in (0..k).rev() {
245 let r = r >> k;
246 if r & 1 != 0 {
247 let nacc = match self.seg.get(&(r - 1)) {
248 Some((x, _)) => M::agg_operate(&acc, x),
249 None => acc.clone(),
250 };
251 if p(&nacc) {
252 return Some(self.bisect_perfect(r - 1, acc, p).0);
253 }
254 acc = nacc;
255 }
256 }
257 None
258 }
259 /// Returns the last index that satisfies a accumlative predicate.
260 pub fn rposition_acc<R, P>(&mut self, range: R, p: P) -> Option<usize>
261 where
262 R: RangeBounds<usize>,
263 P: Fn(&M::Agg) -> bool,
264 {
265 let range = range.to_range_bounded(0, self.n).expect("invalid range");
266 let mut l = range.start + self.n;
267 let mut r = range.end + self.n;
268 self.propagate(l, false, true);
269 self.propagate(r, true, true);
270 let mut c = 0usize;
271 let mut k = 0usize;
272 let mut acc = M::agg_unit();
273 while l >> k < r {
274 c <<= 1;
275 if l & (1 << k) != 0 {
276 l += 1 << k;
277 c += 1;
278 }
279 if r & 1 != 0 {
280 r -= 1;
281 let nacc = match self.seg.get(&r) {
282 Some((x, _)) => M::agg_operate(x, &acc),
283 None => acc.clone(),
284 };
285 if p(&nacc) {
286 return Some(self.rbisect_perfect(r, acc, p).0);
287 }
288 acc = nacc;
289 }
290 r >>= 1;
291 k += 1;
292 }
293 for k in (0..k).rev() {
294 if c & 1 != 0 {
295 l -= 1 << k;
296 let l = l >> k;
297 let nacc = match self.seg.get(&l) {
298 Some((x, _)) => M::agg_operate(x, &acc),
299 None => acc.clone(),
300 };
301 if p(&nacc) {
302 return Some(self.rbisect_perfect(l, acc, p).0);
303 }
304 acc = nacc;
305 }
306 c >>= 1;
307 }
308 None
309 }More examples
crates/competitive/src/data_structure/lazy_segment_tree.rs (line 57)
50 pub fn from_vec(v: Vec<M::Agg>) -> Self {
51 let n = v.len();
52 let mut seg = vec![(M::agg_unit(), M::act_unit()); 2 * n];
53 for (i, x) in v.into_iter().enumerate() {
54 seg[i + n].0 = x;
55 }
56 for i in (1..n).rev() {
57 seg[i].0 = M::agg_operate(&seg[2 * i].0, &seg[2 * i + 1].0);
58 }
59 Self { n, seg }
60 }
61 pub fn from_keys(keys: impl ExactSizeIterator<Item = M::Key>) -> Self {
62 let n = keys.len();
63 let mut seg = vec![(M::agg_unit(), M::act_unit()); 2 * n];
64 for (i, key) in keys.enumerate() {
65 seg[i + n].0 = M::single_agg(&key);
66 }
67 for i in (1..n).rev() {
68 seg[i].0 = M::agg_operate(&seg[2 * i].0, &seg[2 * i + 1].0);
69 }
70 Self { n, seg }
71 }
72 #[inline]
73 fn update_at(&mut self, k: usize, x: &M::Act) {
74 let nx = M::act_agg(&self.seg[k].0, x);
75 if k < self.n {
76 self.seg[k].1 = M::act_operate(&self.seg[k].1, x);
77 }
78 if let Some(nx) = nx {
79 self.seg[k].0 = nx;
80 } else if k < self.n {
81 self.propagate_at(k);
82 self.recalc_at(k);
83 } else {
84 panic!("act failed on leaf");
85 }
86 }
87 #[inline]
88 fn recalc_at(&mut self, k: usize) {
89 self.seg[k].0 = M::agg_operate(&self.seg[2 * k].0, &self.seg[2 * k + 1].0);
90 }
91 #[inline]
92 fn propagate_at(&mut self, k: usize) {
93 debug_assert!(k < self.n);
94 let x = replace(&mut self.seg[k].1, M::act_unit());
95 self.update_at(2 * k, &x);
96 self.update_at(2 * k + 1, &x);
97 }
98 #[inline]
99 fn propagate(&mut self, k: usize, right: bool, nofilt: bool) {
100 let right = right as usize;
101 for i in (1..(k + 1 - right).next_power_of_two().trailing_zeros()).rev() {
102 if nofilt || (k >> i) << i != k {
103 self.propagate_at((k - right) >> i);
104 }
105 }
106 }
107 #[inline]
108 fn recalc(&mut self, k: usize, right: bool, nofilt: bool) {
109 let right = right as usize;
110 for i in 1..(k + 1 - right).next_power_of_two().trailing_zeros() {
111 if nofilt || (k >> i) << i != k {
112 self.recalc_at((k - right) >> i);
113 }
114 }
115 }
116 pub fn update<R>(&mut self, range: R, x: M::Act)
117 where
118 R: RangeBounds<usize>,
119 {
120 let range = range.to_range_bounded(0, self.n).expect("invalid range");
121 let mut a = range.start + self.n;
122 let mut b = range.end + self.n;
123 self.propagate(a, false, false);
124 self.propagate(b, true, false);
125 while a < b {
126 if a & 1 != 0 {
127 self.update_at(a, &x);
128 a += 1;
129 }
130 if b & 1 != 0 {
131 b -= 1;
132 self.update_at(b, &x);
133 }
134 a /= 2;
135 b /= 2;
136 }
137 self.recalc(range.start + self.n, false, false);
138 self.recalc(range.end + self.n, true, false);
139 }
140 pub fn fold<R>(&mut self, range: R) -> M::Agg
141 where
142 R: RangeBounds<usize>,
143 {
144 let range = range.to_range_bounded(0, self.n).expect("invalid range");
145 let mut l = range.start + self.n;
146 let mut r = range.end + self.n;
147 self.propagate(l, false, true);
148 self.propagate(r, true, true);
149 let mut vl = M::agg_unit();
150 let mut vr = M::agg_unit();
151 while l < r {
152 if l & 1 != 0 {
153 vl = M::agg_operate(&vl, &self.seg[l].0);
154 l += 1;
155 }
156 if r & 1 != 0 {
157 r -= 1;
158 vr = M::agg_operate(&self.seg[r].0, &vr);
159 }
160 l /= 2;
161 r /= 2;
162 }
163 M::agg_operate(&vl, &vr)
164 }
165 pub fn set(&mut self, k: usize, x: M::Agg) {
166 let k = k + self.n;
167 self.propagate(k, false, true);
168 self.seg[k] = (x, M::act_unit());
169 self.recalc(k, false, true);
170 }
171 pub fn get(&mut self, k: usize) -> M::Agg {
172 self.fold(k..k + 1)
173 }
174 pub fn fold_all(&mut self) -> M::Agg {
175 self.fold(0..self.n)
176 }
177 fn bisect_perfect<P>(&mut self, mut pos: usize, mut acc: M::Agg, p: P) -> (usize, M::Agg)
178 where
179 P: Fn(&M::Agg) -> bool,
180 {
181 while pos < self.n {
182 self.propagate_at(pos);
183 pos <<= 1;
184 let nacc = M::agg_operate(&acc, &self.seg[pos].0);
185 if !p(&nacc) {
186 acc = nacc;
187 pos += 1;
188 }
189 }
190 (pos - self.n, acc)
191 }
192 fn rbisect_perfect<P>(&mut self, mut pos: usize, mut acc: M::Agg, p: P) -> (usize, M::Agg)
193 where
194 P: Fn(&M::Agg) -> bool,
195 {
196 while pos < self.n {
197 self.propagate_at(pos);
198 pos = pos * 2 + 1;
199 let nacc = M::agg_operate(&self.seg[pos].0, &acc);
200 if !p(&nacc) {
201 acc = nacc;
202 pos -= 1;
203 }
204 }
205 (pos - self.n, acc)
206 }
207 /// Returns the first index that satisfies a accumlative predicate.
208 pub fn position_acc<R, P>(&mut self, range: R, p: P) -> Option<usize>
209 where
210 R: RangeBounds<usize>,
211 P: Fn(&M::Agg) -> bool,
212 {
213 let range = range.to_range_bounded(0, self.n).expect("invalid range");
214 let mut l = range.start + self.n;
215 let r = range.end + self.n;
216 self.propagate(l, false, true);
217 self.propagate(r, true, true);
218 let mut k = 0usize;
219 let mut acc = M::agg_unit();
220 while l < r >> k {
221 if l & 1 != 0 {
222 let nacc = M::agg_operate(&acc, &self.seg[l].0);
223 if p(&nacc) {
224 return Some(self.bisect_perfect(l, acc, p).0);
225 }
226 acc = nacc;
227 l += 1;
228 }
229 l >>= 1;
230 k += 1;
231 }
232 for k in (0..k).rev() {
233 let r = r >> k;
234 if r & 1 != 0 {
235 let nacc = M::agg_operate(&acc, &self.seg[r - 1].0);
236 if p(&nacc) {
237 return Some(self.bisect_perfect(r - 1, acc, p).0);
238 }
239 acc = nacc;
240 }
241 }
242 None
243 }
244 /// Returns the last index that satisfies a accumlative predicate.
245 pub fn rposition_acc<R, P>(&mut self, range: R, p: P) -> Option<usize>
246 where
247 R: RangeBounds<usize>,
248 P: Fn(&M::Agg) -> bool,
249 {
250 let range = range.to_range_bounded(0, self.n).expect("invalid range");
251 let mut l = range.start + self.n;
252 let mut r = range.end + self.n;
253 self.propagate(l, false, true);
254 self.propagate(r, true, true);
255 let mut c = 0usize;
256 let mut k = 0usize;
257 let mut acc = M::agg_unit();
258 while l >> k < r {
259 c <<= 1;
260 if l & (1 << k) != 0 {
261 l += 1 << k;
262 c += 1;
263 }
264 if r & 1 != 0 {
265 r -= 1;
266 let nacc = M::agg_operate(&self.seg[r].0, &acc);
267 if p(&nacc) {
268 return Some(self.rbisect_perfect(r, acc, p).0);
269 }
270 acc = nacc;
271 }
272 r >>= 1;
273 k += 1;
274 }
275 for k in (0..k).rev() {
276 if c & 1 != 0 {
277 l -= 1 << k;
278 let l = l >> k;
279 let nacc = M::agg_operate(&self.seg[l].0, &acc);
280 if p(&nacc) {
281 return Some(self.rbisect_perfect(l, acc, p).0);
282 }
283 acc = nacc;
284 }
285 c >>= 1;
286 }
287 None
288 }crates/competitive/src/data_structure/splay_tree/sequence.rs (line 87)
82 fn recalc(node: NodeRef<marker::DataMut<'_>, Self>) -> NodeRef<marker::DataMut<'_>, Self> {
83 let mut agg = T::single_agg(&node.data().key);
84 let mut size = 1;
85 if let Some(left) = node.left() {
86 let data = left.data();
87 agg = T::agg_operate(&data.agg, &agg);
88 // agg = <T::AggMonoid as Magma>::operate(&data.agg, &agg);
89 size += data.size;
90 }
91 if let Some(right) = node.right() {
92 let data = right.data();
93 agg = T::agg_operate(&agg, &data.agg);
94 size += data.size;
95 }
96 let data = node.data_mut();
97 data.agg = agg;
98 data.size = size;
99 node
100 }
101}
102impl<T> SplaySpec for LazyAggSplay<T>
103where
104 T: MonoidAction,
105{
106 type T = LazyAggElement<T>;
107 fn has_bottom_up() -> bool {
108 true
109 }
110 fn top_down(node: NodeRef<marker::DataMut<'_>, Self>) {
111 Self::propagate(node);
112 }
113 fn bottom_up(node: NodeRef<marker::DataMut<'_>, Self>) {
114 Self::recalc(node);
115 }
116}
117
118struct SeekBySize<T> {
119 index: usize,
120 _marker: PhantomData<fn() -> T>,
121}
122impl<T> SeekBySize<T> {
123 fn new(index: usize) -> Self {
124 Self {
125 index,
126 _marker: PhantomData,
127 }
128 }
129}
130impl<T> SplaySeeker for SeekBySize<T>
131where
132 T: MonoidAction,
133{
134 type S = LazyAggSplay<T>;
135 fn splay_seek(&mut self, node: NodeRef<marker::Immut<'_>, Self::S>) -> Ordering {
136 let lsize = node.left().map(|l| l.data().size).unwrap_or_default();
137 let ord = self.index.cmp(&lsize);
138 if matches!(ord, Ordering::Greater) {
139 self.index -= lsize + 1;
140 }
141 ord
142 }
143}
144
145struct SeekByAccCond<F, T>
146where
147 T: MonoidAction,
148{
149 acc: T::Agg,
150 f: F,
151 _marker: PhantomData<fn() -> T>,
152}
153impl<F, T> SeekByAccCond<F, T>
154where
155 T: MonoidAction,
156{
157 fn new(f: F) -> Self {
158 Self {
159 acc: T::agg_unit(),
160 f,
161 _marker: PhantomData,
162 }
163 }
164}
165impl<F, T> SplaySeeker for SeekByAccCond<F, T>
166where
167 F: FnMut(&T::Agg) -> bool,
168 T: MonoidAction,
169{
170 type S = LazyAggSplay<T>;
171 fn splay_seek(&mut self, node: NodeRef<marker::Immut<'_>, Self::S>) -> Ordering {
172 if let Some(lagg) = node.left().map(|l| &l.data().agg) {
173 let nacc = T::agg_operate(&self.acc, lagg);
174 if (self.f)(&nacc) {
175 return Ordering::Less;
176 }
177 self.acc = nacc;
178 };
179 self.acc = T::agg_operate(&self.acc, &T::single_agg(&node.data().key));
180 if (self.f)(&self.acc) {
181 Ordering::Equal
182 } else {
183 Ordering::Greater
184 }
185 }
186}
187
188struct SeekByRaccCond<F, T>
189where
190 T: MonoidAction,
191{
192 acc: T::Agg,
193 f: F,
194 _marker: PhantomData<fn() -> T>,
195}
196impl<F, T> SeekByRaccCond<F, T>
197where
198 T: MonoidAction,
199{
200 fn new(f: F) -> Self {
201 Self {
202 acc: T::agg_unit(),
203 f,
204 _marker: PhantomData,
205 }
206 }
207}
208impl<F, T> SplaySeeker for SeekByRaccCond<F, T>
209where
210 F: FnMut(&T::Agg) -> bool,
211 T: MonoidAction,
212{
213 type S = LazyAggSplay<T>;
214 fn splay_seek(&mut self, node: NodeRef<marker::Immut<'_>, Self::S>) -> Ordering {
215 if let Some(lagg) = node.right().map(|r| &r.data().agg) {
216 let nacc = T::agg_operate(lagg, &self.acc);
217 if (self.f)(&nacc) {
218 return Ordering::Greater;
219 }
220 self.acc = nacc;
221 };
222 self.acc = T::agg_operate(&T::single_agg(&node.data().key), &self.acc);
223 if (self.f)(&self.acc) {
224 Ordering::Equal
225 } else {
226 Ordering::Less
227 }
228 }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 76)
73 fn update_at(&mut self, k: usize, x: &M::Act) {
74 let nx = M::act_agg(&self.seg[k].0, x);
75 if k < self.n {
76 self.seg[k].1 = M::act_operate(&self.seg[k].1, x);
77 }
78 if let Some(nx) = nx {
79 self.seg[k].0 = nx;
80 } else if k < self.n {
81 self.propagate_at(k);
82 self.recalc_at(k);
83 } else {
84 panic!("act failed on leaf");
85 }
86 }More examples
crates/competitive/src/data_structure/lazy_segment_tree_map.rs (line 66)
61 fn update_at(&mut self, k: usize, x: &M::Act) {
62 let n = self.n;
63 let a = self.get_mut(k);
64 let nx = M::act_agg(&a.0, x);
65 if k < n {
66 a.1 = M::act_operate(&a.1, x);
67 }
68 if let Some(nx) = nx {
69 a.0 = nx;
70 } else if k < n {
71 self.propagate_at(k);
72 self.recalc_at(k);
73 } else {
74 panic!("act failed on leaf");
75 }
76 }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)
Dyn Compatibility§
This trait is not dyn compatible.
In older versions of Rust, dyn compatibility was called "object safety", so this trait is not object safe.