pub trait RangeBoundsExt<T> {
Show 18 methods
// Required methods
fn start_bound_included_checked(&self) -> Option<T>;
fn start_bound_excluded_checked(&self) -> Option<T>;
fn end_bound_included_checked(&self) -> Option<T>;
fn end_bound_excluded_checked(&self) -> Option<T>;
fn start_bound_included(&self) -> T;
fn start_bound_excluded(&self) -> T;
fn end_bound_included(&self) -> T;
fn end_bound_excluded(&self) -> T;
fn start_bound_included_bounded(&self, lb: T) -> Option<T>
where T: Ord;
fn start_bound_excluded_bounded(&self, lb: T) -> Option<T>
where T: Ord;
fn end_bound_included_bounded(&self, ub: T) -> Option<T>
where T: Ord;
fn end_bound_excluded_bounded(&self, ub: T) -> Option<T>
where T: Ord;
// Provided methods
fn to_range_checked(&self) -> Option<Range<T>> { ... }
fn to_range(&self) -> Range<T> { ... }
fn to_range_bounded(&self, min: T, max: T) -> Option<Range<T>>
where T: Ord { ... }
fn to_range_inclusive_checked(&self) -> Option<RangeInclusive<T>> { ... }
fn to_range_inclusive(&self) -> RangeInclusive<T> { ... }
fn to_range_inclusive_bounded(
&self,
min: T,
max: T,
) -> Option<RangeInclusive<T>>
where T: Ord { ... }
}Required Methods§
fn start_bound_included_checked(&self) -> Option<T>
fn start_bound_excluded_checked(&self) -> Option<T>
fn end_bound_included_checked(&self) -> Option<T>
fn end_bound_excluded_checked(&self) -> Option<T>
fn start_bound_included(&self) -> T
fn start_bound_excluded(&self) -> T
fn end_bound_included(&self) -> T
fn end_bound_excluded(&self) -> T
fn start_bound_included_bounded(&self, lb: T) -> Option<T>where
T: Ord,
fn start_bound_excluded_bounded(&self, lb: T) -> Option<T>where
T: Ord,
fn end_bound_included_bounded(&self, ub: T) -> Option<T>where
T: Ord,
fn end_bound_excluded_bounded(&self, ub: T) -> Option<T>where
T: Ord,
Provided Methods§
fn to_range_checked(&self) -> Option<Range<T>>
Sourcefn to_range(&self) -> Range<T>
fn to_range(&self) -> Range<T>
Examples found in repository?
crates/competitive/src/data_structure/segment_tree_map.rs (line 93)
89 pub fn fold<R>(&self, range: R) -> M::T
90 where
91 R: RangeBounds<usize>,
92 {
93 let range = range.to_range();
94 debug_assert!(range.end <= self.n);
95 let mut l = range.start + self.n;
96 let mut r = range.end + self.n;
97 let mut vl = M::unit();
98 let mut vr = M::unit();
99 while l < r {
100 if l & 1 != 0 {
101 vl = M::operate(&vl, self.get_ref(l));
102 l += 1;
103 }
104 if r & 1 != 0 {
105 r -= 1;
106 vr = M::operate(self.get_ref(r), &vr);
107 }
108 l /= 2;
109 r /= 2;
110 }
111 M::operate(&vl, &vr)
112 }
113 fn bisect_perfect<F>(&self, mut pos: usize, mut acc: M::T, f: F) -> (usize, M::T)
114 where
115 F: Fn(&M::T) -> bool,
116 {
117 while pos < self.n {
118 pos <<= 1;
119 let nacc = M::operate(&acc, self.get_ref(pos));
120 if !f(&nacc) {
121 acc = nacc;
122 pos += 1;
123 }
124 }
125 (pos - self.n, acc)
126 }
127 fn rbisect_perfect<F>(&self, mut pos: usize, mut acc: M::T, f: F) -> (usize, M::T)
128 where
129 F: Fn(&M::T) -> bool,
130 {
131 while pos < self.n {
132 pos = pos * 2 + 1;
133 let nacc = M::operate(self.get_ref(pos), &acc);
134 if !f(&nacc) {
135 acc = nacc;
136 pos -= 1;
137 }
138 }
139 (pos - self.n, acc)
140 }
141 /// Returns the first index that satisfies a accumlative predicate.
142 pub fn position_acc<R, F>(&self, range: R, f: F) -> Option<usize>
143 where
144 R: RangeBounds<usize>,
145 F: Fn(&M::T) -> bool,
146 {
147 let range = range.to_range();
148 debug_assert!(range.end <= self.n);
149 let mut l = range.start + self.n;
150 let r = range.end + self.n;
151 let mut k = 0usize;
152 let mut acc = M::unit();
153 while l < r >> k {
154 if l & 1 != 0 {
155 let nacc = M::operate(&acc, self.get_ref(l));
156 if f(&nacc) {
157 return Some(self.bisect_perfect(l, acc, f).0);
158 }
159 acc = nacc;
160 l += 1;
161 }
162 l >>= 1;
163 k += 1;
164 }
165 for k in (0..k).rev() {
166 let r = r >> k;
167 if r & 1 != 0 {
168 let nacc = M::operate(&acc, self.get_ref(r - 1));
169 if f(&nacc) {
170 return Some(self.bisect_perfect(r - 1, acc, f).0);
171 }
172 acc = nacc;
173 }
174 }
175 None
176 }
177 /// Returns the last index that satisfies a accumlative predicate.
178 pub fn rposition_acc<R, F>(&self, range: R, f: F) -> Option<usize>
179 where
180 R: RangeBounds<usize>,
181 F: Fn(&M::T) -> bool,
182 {
183 let range = range.to_range();
184 debug_assert!(range.end <= self.n);
185 let mut l = range.start + self.n;
186 let mut r = range.end + self.n;
187 let mut c = 0usize;
188 let mut k = 0usize;
189 let mut acc = M::unit();
190 while l >> k < r {
191 c <<= 1;
192 if l & (1 << k) != 0 {
193 l += 1 << k;
194 c += 1;
195 }
196 if r & 1 != 0 {
197 r -= 1;
198 let nacc = M::operate(self.get_ref(r), &acc);
199 if f(&nacc) {
200 return Some(self.rbisect_perfect(r, acc, f).0);
201 }
202 acc = nacc;
203 }
204 r >>= 1;
205 k += 1;
206 }
207 for k in (0..k).rev() {
208 if c & 1 != 0 {
209 l -= 1 << k;
210 let l = l >> k;
211 let nacc = M::operate(self.get_ref(l), &acc);
212 if f(&nacc) {
213 return Some(self.rbisect_perfect(l, acc, f).0);
214 }
215 acc = nacc;
216 }
217 c >>= 1;
218 }
219 None
220 }Sourcefn to_range_bounded(&self, min: T, max: T) -> Option<Range<T>>where
T: Ord,
fn to_range_bounded(&self, min: T, max: T) -> Option<Range<T>>where
T: Ord,
Examples found in repository?
crates/competitive/src/data_structure/accumulate.rs (line 76)
71 pub fn fold<R>(&self, range: R) -> M::T
72 where
73 R: RangeBounds<usize>,
74 {
75 let n = self.data.len() - 1;
76 let range = range.to_range_bounded(0, n).expect("invalid range");
77 let (l, r) = (range.start, range.end);
78 assert!(l <= r, "bad range [{}, {})", l, r);
79 M::operate(&M::inverse(unsafe { self.data.get_unchecked(l) }), unsafe {
80 self.data.get_unchecked(r)
81 })
82 }
83}
84
85/// 2-dimensional accumlated data
86pub struct Accumulate2d<M>
87where
88 M: AbelianMonoid,
89{
90 h: usize,
91 w: usize,
92 data: Vec<M::T>,
93}
94
95impl<M> Debug for Accumulate2d<M>
96where
97 M: AbelianMonoid,
98 M::T: Debug,
99{
100 fn fmt(&self, f: &mut Formatter<'_>) -> fmt::Result {
101 f.debug_struct("Accumulate2d")
102 .field("h", &self.h)
103 .field("w", &self.w)
104 .field("data", &self.data)
105 .finish()
106 }
107}
108
109impl<M> Accumulate2d<M>
110where
111 M: AbelianMonoid,
112{
113 pub fn new(arr2d: &[Vec<M::T>]) -> Self {
114 let h = arr2d.len();
115 assert!(h > 0);
116 let w = arr2d[0].len();
117 assert!(w > 0);
118 let w1 = w + 1;
119 let mut data = Vec::with_capacity((h + 1) * w1);
120 data.resize_with(w1, M::unit);
121 for (i, arr) in arr2d.iter().enumerate() {
122 assert_eq!(w, arr.len(), "expected 2d array");
123 let mut acc = M::unit();
124 for (j, x) in arr.iter().enumerate() {
125 let y = M::operate(&acc, x);
126 data.push(M::operate(&acc, unsafe { data.get_unchecked(w1 * i + j) }));
127 acc = y;
128 }
129 data.push(M::operate(&acc, unsafe { data.get_unchecked(w1 * i + w) }));
130 }
131 Self { h, w, data }
132 }
133 pub fn from_fn<F>(h: usize, w: usize, mut f: F) -> Self
134 where
135 F: FnMut(usize, usize) -> M::T,
136 {
137 let w1 = w + 1;
138 let mut data = Vec::with_capacity((h + 1) * w1);
139 data.resize_with(w1, M::unit);
140 for i in 0..h {
141 let mut acc = M::unit();
142 for j in 0..w {
143 let y = M::operate(&acc, &f(i, j));
144 data.push(M::operate(&acc, unsafe { data.get_unchecked(w1 * i + j) }));
145 acc = y;
146 }
147 data.push(M::operate(&acc, unsafe { data.get_unchecked(w1 * i + w) }));
148 }
149 Self { h, w, data }
150 }
151 /// Return fold of \[0, x\) × \[0, y\)
152 pub fn accumulate(&self, x: usize, y: usize) -> M::T {
153 let h1 = self.h + 1;
154 let w1 = self.w + 1;
155 assert!(
156 x < h1,
157 "index out of range: the first len is {} but the index is {}",
158 h1,
159 x
160 );
161 assert!(
162 y < w1,
163 "index out of range: the second len is {} but the index is {}",
164 w1,
165 y
166 );
167 unsafe { self.data.get_unchecked(w1 * x + y) }.clone()
168 }
169}
170
171impl<M> Accumulate2d<M>
172where
173 M: AbelianGroup,
174{
175 /// Return fold of range
176 pub fn fold<R0, R1>(&self, range0: R0, range1: R1) -> M::T
177 where
178 R0: RangeBounds<usize>,
179 R1: RangeBounds<usize>,
180 {
181 let range0 = range0.to_range_bounded(0, self.h).expect("invalid range");
182 let range1 = range1.to_range_bounded(0, self.w).expect("invalid range");
183 let (xl, xr) = (range0.start, range0.end);
184 let (yl, yr) = (range1.start, range1.end);
185 assert!(xl <= xr, "bad range [{}, {})", xl, xr);
186 assert!(yl <= yr, "bad range [{}, {})", yl, yr);
187 let w1 = self.w + 1;
188 unsafe {
189 M::rinv_operate(
190 &M::operate(
191 self.data.get_unchecked(w1 * xl + yl),
192 self.data.get_unchecked(w1 * xr + yr),
193 ),
194 &M::operate(
195 self.data.get_unchecked(w1 * xl + yr),
196 self.data.get_unchecked(w1 * xr + yl),
197 ),
198 )
199 }
200 }
201}
202
203pub struct AccumulateKd<const K: usize, M>
204where
205 M: AbelianMonoid,
206{
207 dim: [usize; K],
208 offset: [usize; K],
209 data: Vec<M::T>,
210}
211
212impl<const K: usize, M> Debug for AccumulateKd<K, M>
213where
214 M: AbelianMonoid,
215 M::T: Debug,
216{
217 fn fmt(&self, f: &mut Formatter<'_>) -> fmt::Result {
218 f.debug_struct("AccumulateKd")
219 .field("dim", &self.dim)
220 .field("offset", &self.offset)
221 .field("data", &self.data)
222 .finish()
223 }
224}
225
226impl<const K: usize, M> AccumulateKd<K, M>
227where
228 M: AbelianMonoid,
229{
230 pub fn from_fn(dim: [usize; K], mut f: impl FnMut([usize; K]) -> M::T) -> Self {
231 fn fill<const K: usize, T>(
232 dim: &[usize; K],
233 offset: &[usize; K],
234 data: &mut [T],
235 f: &mut impl FnMut([usize; K]) -> T,
236 mut index: [usize; K],
237 pos: usize,
238 ) {
239 if pos < K {
240 for i in 0..dim[pos] {
241 index[pos] = i;
242 fill(dim, offset, data, f, index, pos + 1);
243 }
244 } else {
245 let i: usize = index.iter().zip(offset).map(|(x, y)| (x + 1) * y).sum();
246 data[i] = f(index);
247 }
248 }
249
250 let mut offset = [1; K];
251 for d in (1..K).rev() {
252 offset[d - 1] = offset[d] * (dim[d] + 1);
253 }
254 let size = offset[0] * (dim[0] + 1);
255 let mut data = vec![M::unit(); size];
256 fill(&dim, &offset, &mut data, &mut f, [0; K], 0);
257 for d in 0..K {
258 for i in 1..size {
259 if i / offset[d] % (dim[d] + 1) != 0 {
260 data[i] = M::operate(&data[i], &data[i - offset[d]]);
261 }
262 }
263 }
264 Self { dim, offset, data }
265 }
266 pub fn accumulate(&self, x: [usize; K]) -> M::T {
267 for (d, x) in x.into_iter().enumerate() {
268 assert!(
269 x <= self.dim[d],
270 "index out of range: the len is {} but the index is {}",
271 self.dim[d] + 1,
272 x
273 );
274 }
275 let p: usize = x.iter().zip(&self.offset).map(|(x, y)| x * y).sum();
276 unsafe { self.data.get_unchecked(p) }.clone()
277 }
278}
279
280impl<const K: usize, M> AccumulateKd<K, M>
281where
282 M: AbelianGroup,
283{
284 pub fn fold<R>(&self, ranges: [R; K]) -> M::T
285 where
286 R: RangeBounds<usize>,
287 {
288 let ranges: [_; K] = std::array::from_fn(|i| {
289 let range = ranges[i]
290 .to_range_bounded(0, self.dim[i])
291 .expect("invalid range");
292 let (l, r) = (range.start, range.end);
293 assert!(l <= r, "bad range [{}, {})", l, r);
294 [l, r]
295 });
296 let mut acc = M::unit();
297 for bit in 0..1 << K {
298 let p: usize = ranges
299 .iter()
300 .zip(&self.offset)
301 .enumerate()
302 .map(|(d, (range, offset))| range[(bit >> d) & 1 ^ 1] * offset)
303 .sum();
304 if bit.count_ones() & 1 == 0 {
305 acc = M::operate(&acc, unsafe { self.data.get_unchecked(p) });
306 } else {
307 acc = M::rinv_operate(&acc, unsafe { self.data.get_unchecked(p) });
308 }
309 }
310 acc
311 }More examples
crates/competitive/src/data_structure/segment_tree.rs (line 90)
86 pub fn fold<R>(&self, range: R) -> M::T
87 where
88 R: RangeBounds<usize>,
89 {
90 let range = range.to_range_bounded(0, self.n).expect("invalid range");
91 let mut l = range.start + self.n;
92 let mut r = range.end + self.n;
93 let mut vl = M::unit();
94 let mut vr = M::unit();
95 while l < r {
96 if l & 1 != 0 {
97 vl = M::operate(&vl, &self.seg[l]);
98 l += 1;
99 }
100 if r & 1 != 0 {
101 r -= 1;
102 vr = M::operate(&self.seg[r], &vr);
103 }
104 l /= 2;
105 r /= 2;
106 }
107 M::operate(&vl, &vr)
108 }
109 fn bisect_perfect<F>(&self, mut pos: usize, mut acc: M::T, f: F) -> (usize, M::T)
110 where
111 F: Fn(&M::T) -> bool,
112 {
113 while pos < self.n {
114 pos <<= 1;
115 let nacc = M::operate(&acc, &self.seg[pos]);
116 if !f(&nacc) {
117 acc = nacc;
118 pos += 1;
119 }
120 }
121 (pos - self.n, acc)
122 }
123 fn rbisect_perfect<F>(&self, mut pos: usize, mut acc: M::T, f: F) -> (usize, M::T)
124 where
125 F: Fn(&M::T) -> bool,
126 {
127 while pos < self.n {
128 pos = pos * 2 + 1;
129 let nacc = M::operate(&self.seg[pos], &acc);
130 if !f(&nacc) {
131 acc = nacc;
132 pos -= 1;
133 }
134 }
135 (pos - self.n, acc)
136 }
137 /// Returns the first index that satisfies a accumlative predicate.
138 pub fn position_acc<R, F>(&self, range: R, f: F) -> Option<usize>
139 where
140 R: RangeBounds<usize>,
141 F: Fn(&M::T) -> bool,
142 {
143 let range = range.to_range_bounded(0, self.n).expect("invalid range");
144 let mut l = range.start + self.n;
145 let r = range.end + self.n;
146 let mut k = 0usize;
147 let mut acc = M::unit();
148 while l < r >> k {
149 if l & 1 != 0 {
150 let nacc = M::operate(&acc, &self.seg[l]);
151 if f(&nacc) {
152 return Some(self.bisect_perfect(l, acc, f).0);
153 }
154 acc = nacc;
155 l += 1;
156 }
157 l >>= 1;
158 k += 1;
159 }
160 for k in (0..k).rev() {
161 let r = r >> k;
162 if r & 1 != 0 {
163 let nacc = M::operate(&acc, &self.seg[r - 1]);
164 if f(&nacc) {
165 return Some(self.bisect_perfect(r - 1, acc, f).0);
166 }
167 acc = nacc;
168 }
169 }
170 None
171 }
172 /// Returns the last index that satisfies a accumlative predicate.
173 pub fn rposition_acc<R, F>(&self, range: R, f: F) -> Option<usize>
174 where
175 R: RangeBounds<usize>,
176 F: Fn(&M::T) -> bool,
177 {
178 let range = range.to_range_bounded(0, self.n).expect("invalid range");
179 let mut l = range.start + self.n;
180 let mut r = range.end + self.n;
181 let mut c = 0usize;
182 let mut k = 0usize;
183 let mut acc = M::unit();
184 while l >> k < r {
185 c <<= 1;
186 if l & (1 << k) != 0 {
187 l += 1 << k;
188 c += 1;
189 }
190 if r & 1 != 0 {
191 r -= 1;
192 let nacc = M::operate(&self.seg[r], &acc);
193 if f(&nacc) {
194 return Some(self.rbisect_perfect(r, acc, f).0);
195 }
196 acc = nacc;
197 }
198 r >>= 1;
199 k += 1;
200 }
201 for k in (0..k).rev() {
202 if c & 1 != 0 {
203 l -= 1 << k;
204 let l = l >> k;
205 let nacc = M::operate(&self.seg[l], &acc);
206 if f(&nacc) {
207 return Some(self.rbisect_perfect(l, acc, f).0);
208 }
209 acc = nacc;
210 }
211 c >>= 1;
212 }
213 None
214 }crates/competitive/src/algorithm/sqrt_decomposition.rs (line 56)
52 pub fn update<R>(&mut self, range: R, x: <S::M as Magma>::T)
53 where
54 R: RangeBounds<usize>,
55 {
56 let range = range.to_range_bounded(0, self.n).expect("invalid range");
57 for (i, (cells, bucket)) in self.buckets.iter_mut().enumerate() {
58 let s = i * self.bucket_size;
59 let t = s + cells.len();
60 if t <= range.start || range.end <= s {
61 } else if range.start <= s && t <= range.end {
62 S::update_bucket(bucket, &x);
63 } else {
64 for cell in &mut cells[range.start.max(s) - s..range.end.min(t) - s] {
65 S::update_cell(bucket, cell, &x);
66 }
67 }
68 }
69 }
70 pub fn get(&self, i: usize) -> <S::M as Magma>::T {
71 let (cells, bucket) = &self.buckets[i / self.bucket_size];
72 let j = i % self.bucket_size;
73 S::fold_cell(bucket, &cells[j])
74 }
75 pub fn fold<R>(&self, range: R) -> <S::M as Magma>::T
76 where
77 R: RangeBounds<usize>,
78 {
79 let range = range.to_range_bounded(0, self.n).expect("invalid range");
80 let mut res = S::M::unit();
81 for (i, (cells, bucket)) in self.buckets.iter().enumerate() {
82 let s = i * self.bucket_size;
83 let t = s + cells.len();
84 if t <= range.start || range.end <= s {
85 } else if range.start <= s && t <= range.end {
86 <S::M as Magma>::operate_assign(&mut res, &S::fold_bucket(bucket));
87 } else {
88 for cell in &cells[range.start.max(s) - s..range.end.min(t) - s] {
89 <S::M as Magma>::operate_assign(&mut res, &S::fold_cell(bucket, cell));
90 }
91 }
92 }
93 res
94 }crates/competitive/src/data_structure/lazy_segment_tree.rs (line 120)
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/lazy_segment_tree_map.rs (line 119)
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 }