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