LazySegmentTreeMap

competitive::data_structure

Struct LazySegmentTreeMap 

Source 
pub struct LazySegmentTreeMap<M>
where
    M: LazyMapMonoid<Act: PartialEq>,
{
    n: usize,
    seg: HashMap<usize, (M::Agg, M::Act)>,
}

Fields§

§n: usize§seg: HashMap<usize, (M::Agg, M::Act)>

Implementations§

Source§

impl<M> LazySegmentTreeMap<M>
where M: LazyMapMonoid<Act: PartialEq>,

Source

pub fn new(n: usize) -> Self

Source

fn get_mut(&mut self, k: usize) -> &mut (M::Agg, M::Act)

Examples found in repository?
crates/competitive/src/data_structure/lazy_segment_tree_map.rs (line 58)
56    fn update_at(&mut self, k: usize, x: &M::Act) {
57        let n = self.n;
58        let a = self.get_mut(k);
59        let nx = M::act_agg(&a.0, x);
60        if k < n {
61            a.1 = M::act_operate(&a.1, x);
62        }
63        if let Some(nx) = nx {
64            a.0 = nx;
65        } else if k < n {
66            self.propagate_at(k);
67            self.recalc_at(k);
68        } else {
69            panic!("act failed on leaf");
70        }
71    }
72    #[inline]
73    fn recalc_at(&mut self, k: usize) {
74        let x = match (self.seg.get(&(2 * k)), self.seg.get(&(2 * k + 1))) {
75            (None, None) => M::agg_unit(),
76            (None, Some((y, _))) => y.clone(),
77            (Some((x, _)), None) => x.clone(),
78            (Some((x, _)), Some((y, _))) => M::agg_operate(x, y),
79        };
80        self.get_mut(k).0 = x;
81    }
82    #[inline]
83    fn propagate_at(&mut self, k: usize) {
84        debug_assert!(k < self.n);
85        let x = match self.seg.get_mut(&k) {
86            Some((_, x)) => replace(x, M::act_unit()),
87            None => M::act_unit(),
88        };
89        self.update_at(2 * k, &x);
90        self.update_at(2 * k + 1, &x);
91    }
92    #[inline]
93    fn propagate(&mut self, k: usize, right: bool, nofilt: bool) {
94        let right = right as usize;
95        for i in (1..(k + 1 - right).next_power_of_two().trailing_zeros()).rev() {
96            if nofilt || (k >> i) << i != k {
97                self.propagate_at((k - right) >> i);
98            }
99        }
100    }
101    #[inline]
102    fn recalc(&mut self, k: usize, right: bool, nofilt: bool) {
103        let right = right as usize;
104        for i in 1..(k + 1 - right).next_power_of_two().trailing_zeros() {
105            if nofilt || (k >> i) << i != k {
106                self.recalc_at((k - right) >> i);
107            }
108        }
109    }
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    }
Source

fn update_at(&mut self, k: usize, x: &M::Act)

Examples found in repository?
crates/competitive/src/data_structure/lazy_segment_tree_map.rs (line 89)
83    fn propagate_at(&mut self, k: usize) {
84        debug_assert!(k < self.n);
85        let x = match self.seg.get_mut(&k) {
86            Some((_, x)) => replace(x, M::act_unit()),
87            None => M::act_unit(),
88        };
89        self.update_at(2 * k, &x);
90        self.update_at(2 * k + 1, &x);
91    }
92    #[inline]
93    fn propagate(&mut self, k: usize, right: bool, nofilt: bool) {
94        let right = right as usize;
95        for i in (1..(k + 1 - right).next_power_of_two().trailing_zeros()).rev() {
96            if nofilt || (k >> i) << i != k {
97                self.propagate_at((k - right) >> i);
98            }
99        }
100    }
101    #[inline]
102    fn recalc(&mut self, k: usize, right: bool, nofilt: bool) {
103        let right = right as usize;
104        for i in 1..(k + 1 - right).next_power_of_two().trailing_zeros() {
105            if nofilt || (k >> i) << i != k {
106                self.recalc_at((k - right) >> i);
107            }
108        }
109    }
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    }
Source

fn recalc_at(&mut self, k: usize)

Examples found in repository?
crates/competitive/src/data_structure/lazy_segment_tree_map.rs (line 67)
56    fn update_at(&mut self, k: usize, x: &M::Act) {
57        let n = self.n;
58        let a = self.get_mut(k);
59        let nx = M::act_agg(&a.0, x);
60        if k < n {
61            a.1 = M::act_operate(&a.1, x);
62        }
63        if let Some(nx) = nx {
64            a.0 = nx;
65        } else if k < n {
66            self.propagate_at(k);
67            self.recalc_at(k);
68        } else {
69            panic!("act failed on leaf");
70        }
71    }
72    #[inline]
73    fn recalc_at(&mut self, k: usize) {
74        let x = match (self.seg.get(&(2 * k)), self.seg.get(&(2 * k + 1))) {
75            (None, None) => M::agg_unit(),
76            (None, Some((y, _))) => y.clone(),
77            (Some((x, _)), None) => x.clone(),
78            (Some((x, _)), Some((y, _))) => M::agg_operate(x, y),
79        };
80        self.get_mut(k).0 = x;
81    }
82    #[inline]
83    fn propagate_at(&mut self, k: usize) {
84        debug_assert!(k < self.n);
85        let x = match self.seg.get_mut(&k) {
86            Some((_, x)) => replace(x, M::act_unit()),
87            None => M::act_unit(),
88        };
89        self.update_at(2 * k, &x);
90        self.update_at(2 * k + 1, &x);
91    }
92    #[inline]
93    fn propagate(&mut self, k: usize, right: bool, nofilt: bool) {
94        let right = right as usize;
95        for i in (1..(k + 1 - right).next_power_of_two().trailing_zeros()).rev() {
96            if nofilt || (k >> i) << i != k {
97                self.propagate_at((k - right) >> i);
98            }
99        }
100    }
101    #[inline]
102    fn recalc(&mut self, k: usize, right: bool, nofilt: bool) {
103        let right = right as usize;
104        for i in 1..(k + 1 - right).next_power_of_two().trailing_zeros() {
105            if nofilt || (k >> i) << i != k {
106                self.recalc_at((k - right) >> i);
107            }
108        }
109    }
Source

fn propagate_at(&mut self, k: usize)

Examples found in repository?
crates/competitive/src/data_structure/lazy_segment_tree_map.rs (line 66)
56    fn update_at(&mut self, k: usize, x: &M::Act) {
57        let n = self.n;
58        let a = self.get_mut(k);
59        let nx = M::act_agg(&a.0, x);
60        if k < n {
61            a.1 = M::act_operate(&a.1, x);
62        }
63        if let Some(nx) = nx {
64            a.0 = nx;
65        } else if k < n {
66            self.propagate_at(k);
67            self.recalc_at(k);
68        } else {
69            panic!("act failed on leaf");
70        }
71    }
72    #[inline]
73    fn recalc_at(&mut self, k: usize) {
74        let x = match (self.seg.get(&(2 * k)), self.seg.get(&(2 * k + 1))) {
75            (None, None) => M::agg_unit(),
76            (None, Some((y, _))) => y.clone(),
77            (Some((x, _)), None) => x.clone(),
78            (Some((x, _)), Some((y, _))) => M::agg_operate(x, y),
79        };
80        self.get_mut(k).0 = x;
81    }
82    #[inline]
83    fn propagate_at(&mut self, k: usize) {
84        debug_assert!(k < self.n);
85        let x = match self.seg.get_mut(&k) {
86            Some((_, x)) => replace(x, M::act_unit()),
87            None => M::act_unit(),
88        };
89        self.update_at(2 * k, &x);
90        self.update_at(2 * k + 1, &x);
91    }
92    #[inline]
93    fn propagate(&mut self, k: usize, right: bool, nofilt: bool) {
94        let right = right as usize;
95        for i in (1..(k + 1 - right).next_power_of_two().trailing_zeros()).rev() {
96            if nofilt || (k >> i) << i != k {
97                self.propagate_at((k - right) >> i);
98            }
99        }
100    }
101    #[inline]
102    fn recalc(&mut self, k: usize, right: bool, nofilt: bool) {
103        let right = right as usize;
104        for i in 1..(k + 1 - right).next_power_of_two().trailing_zeros() {
105            if nofilt || (k >> i) << i != k {
106                self.recalc_at((k - right) >> i);
107            }
108        }
109    }
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    }
Source

fn propagate(&mut self, k: usize, right: bool, nofilt: bool)

Examples found in repository?
crates/competitive/src/data_structure/lazy_segment_tree_map.rs (line 117)
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    }
Source

fn recalc(&mut self, k: usize, right: bool, nofilt: bool)

Examples found in repository?
crates/competitive/src/data_structure/lazy_segment_tree_map.rs (line 131)
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    }
Source

pub fn update<R>(&mut self, range: R, x: M::Act)
where R: RangeBounds<usize>,

Source

pub fn fold<R>(&mut self, range: R) -> M::Agg
where R: RangeBounds<usize>,

Examples found in repository?
crates/competitive/src/data_structure/lazy_segment_tree_map.rs (line 170)
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    }
Source

pub fn set(&mut self, k: usize, x: M::Agg)

Source

pub fn get(&mut self, k: usize) -> M::Agg

Source

pub fn fold_all(&mut self) -> M::Agg

Source

fn bisect_perfect<P>( &mut self, pos: usize, acc: M::Agg, p: P, ) -> (usize, M::Agg)
where P: Fn(&M::Agg) -> bool,

Examples found in repository?
crates/competitive/src/data_structure/lazy_segment_tree_map.rs (line 231)
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    }
Source

fn rbisect_perfect<P>( &mut self, pos: usize, acc: M::Agg, p: P, ) -> (usize, M::Agg)
where P: Fn(&M::Agg) -> bool,

Examples found in repository?
crates/competitive/src/data_structure/lazy_segment_tree_map.rs (line 281)
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    }
Source

pub fn position_acc<R, P>(&mut self, range: R, p: P) -> Option<usize>
where R: RangeBounds<usize>, P: Fn(&M::Agg) -> bool,

Returns the first index that satisfies a accumlative predicate.

Source

pub fn rposition_acc<R, P>(&mut self, range: R, p: P) -> Option<usize>
where R: RangeBounds<usize>, P: Fn(&M::Agg) -> bool,

Returns the last index that satisfies a accumlative predicate.

Trait Implementations§

Source§

impl<M> Clone for LazySegmentTreeMap<M>
where M: LazyMapMonoid<Act: PartialEq>,

Source§

fn clone(&self) -> Self

Returns a duplicate of the value. Read more
1.0.0 · Source§

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source. Read more
Source§

impl<M> Debug for LazySegmentTreeMap<M>
where M: LazyMapMonoid<Agg: Debug, Act: PartialEq + Debug>,

Source§

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter. Read more

Auto Trait Implementations§

Blanket Implementations§

Source§

impl<T> Any for T
where T: 'static + ?Sized,

Source§

fn type_id(&self) -> TypeId

Gets the TypeId of self. Read more
Source§

impl<T> Borrow<T> for T
where T: ?Sized,

Source§

fn borrow(&self) -> &T

Immutably borrows from an owned value. Read more
Source§

impl<T> BorrowMut<T> for T
where T: ?Sized,

Source§

fn borrow_mut(&mut self) -> &mut T

Mutably borrows from an owned value. Read more
Source§

impl<T> CloneToUninit for T
where T: Clone,

Source§

unsafe fn clone_to_uninit(&self, dest: *mut u8)

🔬This is a nightly-only experimental API. (clone_to_uninit)
Performs copy-assignment from self to dest. Read more
Source§

impl<T> From<T> for T

Source§

fn from(t: T) -> T

Returns the argument unchanged.

Source§

impl<T, U> Into<U> for T
where U: From<T>,

Source§

fn into(self) -> U

Calls U::from(self).

That is, this conversion is whatever the implementation of From<T> for U chooses to do.

Source§

impl<T> ToOwned for T
where T: Clone,

Source§

type Owned = T

The resulting type after obtaining ownership.
Source§

fn to_owned(&self) -> T

Creates owned data from borrowed data, usually by cloning. Read more
Source§

fn clone_into(&self, target: &mut T)

Uses borrowed data to replace owned data, usually by cloning. Read more
Source§

impl<T, U> TryFrom<U> for T
where U: Into<T>,

Source§

type Error = Infallible

The type returned in the event of a conversion error.
Source§

fn try_from(value: U) -> Result<T, <T as TryFrom<U>>::Error>

Performs the conversion.
Source§

impl<T, U> TryInto<U> for T
where U: TryFrom<T>,

Source§

type Error = <U as TryFrom<T>>::Error

The type returned in the event of a conversion error.
Source§

fn try_into(self) -> Result<U, <U as TryFrom<T>>::Error>

Performs the conversion.