Struct LazySegmentTree

Source

pub struct LazySegmentTree<M>where
    M: LazyMapMonoid,{
    len: usize,
    n: usize,
    seg: Vec<M::Agg>,
    lazy: Vec<M::Act>,
}

Fields§

§len: usize§n: usize§seg: Vec<M::Agg>§lazy: Vec<M::Act>

Implementations§

Source §

impl<M> LazySegmentTree<M>
where M: LazyMapMonoid,

Source

pub fn new(len: usize) -> Self

Examples found in repository ?

crates/aizu_online_judge/src/dsl/dsl_2_d.rs (line 15)

12pub fn dsl_2_d(reader: impl Read, writer: impl Write) {
13    prepare_io!(reader, writer);
14    sc!(n, q);
15    let mut seg = LazySegmentTree::<RangeMinRangeUpdate<_>>::new(n);
16    for _ in 0..q {
17        sc!(query: Query);
18        match query {
19            Query::Update { s, t, x } => {
20                seg.update(s..t + 1, Some(x));
21            }
22            Query::Get { i } => {
23                pp!(seg.fold(i..i + 1));
24            }
25        }
26    }
27}

More examples

Hide additional examples

crates/aizu_online_judge/src/dsl/dsl_2_f.rs (line 15)

12pub fn dsl_2_f(reader: impl Read, writer: impl Write) {
13    prepare_io!(reader, writer);
14    sc!(n, q);
15    let mut seg = LazySegmentTree::<RangeMinRangeUpdate<_>>::new(n);
16    for _ in 0..q {
17        sc!(query: Query);
18        match query {
19            Query::Update { s, t, x } => {
20                seg.update(s..t + 1, Some(x));
21            }
22            Query::Fold { s, t } => {
23                pp!(seg.fold(s..t + 1));
24            }
25        }
26    }
27}

Source

pub fn from_vec(v: Vec<M::Agg>) -> Self

Examples found in repository ?

crates/library_checker/src/data_structure/range_affine_range_sum_large_array.rs (lines 31-36)

18pub fn range_affine_range_sum_large_array(reader: impl Read, writer: impl Write) {
19    prepare_io!(reader, writer);
20    sc!(n: u32, q, queries: [Query; q]);
21    let mut values: Vec<_> = [0, n]
22        .into_iter()
23        .chain(queries.iter().flat_map(|&query| {
24            let (Query::Update { l, r, .. } | Query::Fold { l, r }) = query;
25            [l, r]
26        }))
27        .collect();
28    values.radix_sort_by_key(|&x| x);
29    values.dedup();
30    let search = StaticSearch::from_sorted(&values);
31    let mut seg = LazySegmentTree::<RangeSumRangeLinear<M>>::from_vec(
32        values
33            .windows(2)
34            .map(|w| (M::zero(), M::from(w[1] - w[0])))
35            .collect(),
36    );
37    let endpoints: Vec<_> = queries
38        .iter()
39        .flat_map(|&query| {
40            let (Query::Update { l, r, .. } | Query::Fold { l, r }) = query;
41            [l, r]
42        })
43        .collect();
44    let mut positions = vec![0; endpoints.len()];
45    search.lower_bound_batch(&endpoints, &mut positions);
46    for (query, &[l, r]) in queries.into_iter().zip(positions.as_chunks::<2>().0) {
47        match query {
48            Query::Update { bc, .. } => {
49                seg.update(l..r, bc);
50            }
51            Query::Fold { .. } => {
52                pp!(seg.fold(l..r).0);
53            }
54        }
55    }
56}

More examples

Hide additional examples

crates/library_checker/src/data_structure/area_of_union_of_rectangles.rs (lines 29-31)

9pub fn area_of_union_of_rectangles(reader: impl Read, writer: impl Write) {
10    prepare_io!(buffered; reader, writer);
11    sc!(n, rectangles: [(u32, u32, u32, u32); n]);
12    let endpoints: Vec<_> = rectangles.iter().flat_map(|&(_, d, _, u)| [d, u]).collect();
13    let mut ys = endpoints.clone();
14    ys.radix_sort_by_key(|&y| y);
15    ys.dedup();
16    let search = StaticSearch::from_sorted(&ys);
17    let mut positions = vec![0; endpoints.len()];
18    search.lower_bound_batch(&endpoints, &mut positions);
19    let mut events: Vec<_> = rectangles
20        .into_iter()
21        .zip(positions.as_chunks().0)
22        .flat_map(|((l, _, r, _), &[d, u])| {
23            let d = d as u32;
24            let u = u as u32;
25            [(l, d, u, 1), (r, d, u, -1)]
26        })
27        .collect();
28    events.radix_sort_by_key(|&(x, ..)| x);
29    let mut seg = LazySegmentTree::<RangeMinCountRangeAdd<i32>>::from_vec(
30        ys.windows(2).map(|w| (0, (w[1] - w[0]) as usize)).collect(),
31    );
32    let height = (ys[ys.len() - 1] - ys[0]) as usize;
33    let mut prev_x = 0;
34    let mut area = 0u64;
35    for (x, d, u, delta) in events {
36        let (minimum, count) = seg.fold_all();
37        let covered = height - if minimum == 0 { count } else { 0 };
38        area += (x - prev_x) as u64 * covered as u64;
39        seg.update(d as usize..u as usize, delta);
40        prev_x = x;
41    }
42    pp!(area);
43}

Source

pub fn from_keys(keys: impl ExactSizeIterator<Item = M::Key>) -> Self

Examples found in repository ?

crates/aizu_online_judge/src/dsl/dsl_2_e.rs (line 15)

12pub fn dsl_2_e(reader: impl Read, writer: impl Write) {
13    prepare_io!(reader, writer);
14    sc!(n, q);
15    let mut seg = LazySegmentTree::<RangeSumRangeAdd<_>>::from_keys(std::iter::repeat_n(0, n));
16    for _ in 0..q {
17        sc!(query: Query);
18        match query {
19            Query::Add { s, t, x } => {
20                seg.update(s - 1..t, x);
21            }
22            Query::Get { i } => {
23                pp!(seg.fold(i - 1..i).0);
24            }
25        }
26    }
27}

More examples

Hide additional examples

crates/aizu_online_judge/src/dsl/dsl_2_h.rs (line 15)

12pub fn dsl_2_h(reader: impl Read, writer: impl Write) {
13    prepare_io!(reader, writer);
14    sc!(n, q);
15    let mut seg = LazySegmentTree::<RangeMinRangeAdd<_>>::from_keys(std::iter::repeat_n(0, n));
16    for _ in 0..q {
17        sc!(query: Query);
18        match query {
19            Query::Add { s, t, x } => {
20                seg.update(s..t + 1, x);
21            }
22            Query::Min { s, t } => {
23                pp!(seg.fold(s..t + 1));
24            }
25        }
26    }
27}

crates/aizu_online_judge/src/dsl/dsl_2_g.rs (line 15)

12pub fn dsl_2_g(reader: impl Read, writer: impl Write) {
13    prepare_io!(reader, writer);
14    sc!(n, q);
15    let mut seg = LazySegmentTree::<RangeSumRangeAdd<_>>::from_keys(std::iter::repeat_n(0, n));
16    for _ in 0..q {
17        sc!(query: Query);
18        match query {
19            Query::Add { s, t, x } => {
20                seg.update(s - 1..t, x);
21            }
22            Query::Sum { s, t } => {
23                pp!(seg.fold(s - 1..t).0);
24            }
25        }
26    }
27}

crates/library_checker/src/data_structure/range_affine_range_sum.rs (line 18)

15pub fn range_affine_range_sum(reader: impl Read, writer: impl Write) {
16    prepare_io!(reader, writer);
17    sc!(n, q, a: [M; iter n]);
18    let mut seg = LazySegmentTree::<RangeSumRangeLinear<_>>::from_keys(a);
19    for _ in 0..q {
20        sc!(query: Query);
21        match query {
22            Query::Update { l, r, bc } => {
23                seg.update(l..r, bc);
24            }
25            Query::Fold { l, r } => {
26                pp!(seg.fold(l..r).0);
27            }
28        }
29    }
30}

crates/aizu_online_judge/src/dsl/dsl_2_i.rs (line 15)

12pub fn dsl_2_i(reader: impl Read, writer: impl Write) {
13    prepare_io!(reader, writer);
14    sc!(n, q);
15    let mut seg = LazySegmentTree::<RangeSumRangeUpdate<_>>::from_keys(std::iter::repeat_n(0, n));
16    for _ in 0..q {
17        sc!(query: Query);
18        match query {
19            Query::Update { s, t, x } => {
20                seg.update(s..t + 1, Some(x));
21            }
22            Query::Sum { s, t } => {
23                pp!(seg.fold(s..t + 1).0);
24            }
25        }
26    }
27}

crates/library_checker/src/data_structure/range_add_range_min.rs (line 15)

12pub fn range_add_range_min(reader: impl Read, writer: impl Write) {
13    prepare_io!(reader, writer);
14    sc!(n, q, a: [i64; iter n]);
15    let mut seg = LazySegmentTree::<RangeMinRangeAdd<i64>>::from_keys(a);
16    for _ in 0..q {
17        sc!(query: Query);
18        match query {
19            Query::Add { l, r, x } => {
20                seg.update(l..r, x);
21            }
22            Query::Min { l, r } => {
23                let ans = seg.fold(l..r);
24                pp!(ans);
25            }
26        }
27    }
28}

Additional examples can be found in:

Source

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

Examples found in repository ?

crates/competitive/src/data_structure/lazy_segment_tree.rs (line 111)

105    fn propagate_at(&mut self, k: usize) {
106        debug_assert!(k < self.n);
107        let x = replace(&mut self.lazy[k], M::act_unit());
108        if M::is_act_unit(&x) {
109            return;
110        }
111        self.update_at(2 * k, &x);
112        self.update_at(2 * k + 1, &x);
113    }
114    #[inline]
115    fn propagate(&mut self, k: usize) {
116        for i in (1..=self.n.trailing_zeros()).rev() {
117            self.propagate_at(k >> i);
118        }
119    }
120    #[inline]
121    fn recalc(&mut self, mut k: usize) {
122        while k > 1 {
123            k >>= 1;
124            self.recalc_at(k);
125        }
126    }
127    pub fn update<R>(&mut self, range: R, x: M::Act)
128    where
129        R: RangeBounds<usize>,
130    {
131        let range = range.to_range_bounded(0, self.len).expect("invalid range");
132        if range.is_empty() || M::is_act_unit(&x) {
133            return;
134        }
135        let mut a = range.start + self.n;
136        let mut b = range.end + self.n;
137        for i in (1..=self.n.trailing_zeros()).rev() {
138            if (a >> i) << i != a {
139                self.propagate_at(a >> i);
140            }
141            if (b >> i) << i != b {
142                self.propagate_at((b - 1) >> i);
143            }
144        }
145        while a < b {
146            if a & 1 != 0 {
147                self.update_at(a, &x);
148                a += 1;
149            }
150            if b & 1 != 0 {
151                b -= 1;
152                self.update_at(b, &x);
153            }
154            a /= 2;
155            b /= 2;
156        }
157        let a = range.start + self.n;
158        let b = range.end + self.n;
159        for i in 1..=self.n.trailing_zeros() {
160            if (a >> i) << i != a {
161                self.recalc_at(a >> i);
162            }
163            if (b >> i) << i != b {
164                self.recalc_at((b - 1) >> i);
165            }
166        }
167    }

Source

fn recalc_at(&mut self, k: usize)

Examples found in repository ?

crates/competitive/src/data_structure/lazy_segment_tree.rs (line 95)

83    fn update_at(&mut self, k: usize, x: &M::Act) {
84        if M::is_act_unit(x) {
85            return;
86        }
87        let nx = M::act_agg(&self.seg[k], x);
88        if k < self.n {
89            self.lazy[k] = M::act_operate(&self.lazy[k], x);
90        }
91        if let Some(nx) = nx {
92            self.seg[k] = nx;
93        } else if k < self.n {
94            self.propagate_at(k);
95            self.recalc_at(k);
96        } else {
97            panic!("act failed on leaf");
98        }
99    }
100    #[inline]
101    fn recalc_at(&mut self, k: usize) {
102        self.seg[k] = M::agg_operate(&self.seg[2 * k], &self.seg[2 * k + 1]);
103    }
104    #[inline]
105    fn propagate_at(&mut self, k: usize) {
106        debug_assert!(k < self.n);
107        let x = replace(&mut self.lazy[k], M::act_unit());
108        if M::is_act_unit(&x) {
109            return;
110        }
111        self.update_at(2 * k, &x);
112        self.update_at(2 * k + 1, &x);
113    }
114    #[inline]
115    fn propagate(&mut self, k: usize) {
116        for i in (1..=self.n.trailing_zeros()).rev() {
117            self.propagate_at(k >> i);
118        }
119    }
120    #[inline]
121    fn recalc(&mut self, mut k: usize) {
122        while k > 1 {
123            k >>= 1;
124            self.recalc_at(k);
125        }
126    }
127    pub fn update<R>(&mut self, range: R, x: M::Act)
128    where
129        R: RangeBounds<usize>,
130    {
131        let range = range.to_range_bounded(0, self.len).expect("invalid range");
132        if range.is_empty() || M::is_act_unit(&x) {
133            return;
134        }
135        let mut a = range.start + self.n;
136        let mut b = range.end + self.n;
137        for i in (1..=self.n.trailing_zeros()).rev() {
138            if (a >> i) << i != a {
139                self.propagate_at(a >> i);
140            }
141            if (b >> i) << i != b {
142                self.propagate_at((b - 1) >> i);
143            }
144        }
145        while a < b {
146            if a & 1 != 0 {
147                self.update_at(a, &x);
148                a += 1;
149            }
150            if b & 1 != 0 {
151                b -= 1;
152                self.update_at(b, &x);
153            }
154            a /= 2;
155            b /= 2;
156        }
157        let a = range.start + self.n;
158        let b = range.end + self.n;
159        for i in 1..=self.n.trailing_zeros() {
160            if (a >> i) << i != a {
161                self.recalc_at(a >> i);
162            }
163            if (b >> i) << i != b {
164                self.recalc_at((b - 1) >> i);
165            }
166        }
167    }

Source

fn propagate_at(&mut self, k: usize)

Examples found in repository ?

crates/competitive/src/data_structure/lazy_segment_tree.rs (line 94)

83    fn update_at(&mut self, k: usize, x: &M::Act) {
84        if M::is_act_unit(x) {
85            return;
86        }
87        let nx = M::act_agg(&self.seg[k], x);
88        if k < self.n {
89            self.lazy[k] = M::act_operate(&self.lazy[k], x);
90        }
91        if let Some(nx) = nx {
92            self.seg[k] = nx;
93        } else if k < self.n {
94            self.propagate_at(k);
95            self.recalc_at(k);
96        } else {
97            panic!("act failed on leaf");
98        }
99    }
100    #[inline]
101    fn recalc_at(&mut self, k: usize) {
102        self.seg[k] = M::agg_operate(&self.seg[2 * k], &self.seg[2 * k + 1]);
103    }
104    #[inline]
105    fn propagate_at(&mut self, k: usize) {
106        debug_assert!(k < self.n);
107        let x = replace(&mut self.lazy[k], M::act_unit());
108        if M::is_act_unit(&x) {
109            return;
110        }
111        self.update_at(2 * k, &x);
112        self.update_at(2 * k + 1, &x);
113    }
114    #[inline]
115    fn propagate(&mut self, k: usize) {
116        for i in (1..=self.n.trailing_zeros()).rev() {
117            self.propagate_at(k >> i);
118        }
119    }
120    #[inline]
121    fn recalc(&mut self, mut k: usize) {
122        while k > 1 {
123            k >>= 1;
124            self.recalc_at(k);
125        }
126    }
127    pub fn update<R>(&mut self, range: R, x: M::Act)
128    where
129        R: RangeBounds<usize>,
130    {
131        let range = range.to_range_bounded(0, self.len).expect("invalid range");
132        if range.is_empty() || M::is_act_unit(&x) {
133            return;
134        }
135        let mut a = range.start + self.n;
136        let mut b = range.end + self.n;
137        for i in (1..=self.n.trailing_zeros()).rev() {
138            if (a >> i) << i != a {
139                self.propagate_at(a >> i);
140            }
141            if (b >> i) << i != b {
142                self.propagate_at((b - 1) >> i);
143            }
144        }
145        while a < b {
146            if a & 1 != 0 {
147                self.update_at(a, &x);
148                a += 1;
149            }
150            if b & 1 != 0 {
151                b -= 1;
152                self.update_at(b, &x);
153            }
154            a /= 2;
155            b /= 2;
156        }
157        let a = range.start + self.n;
158        let b = range.end + self.n;
159        for i in 1..=self.n.trailing_zeros() {
160            if (a >> i) << i != a {
161                self.recalc_at(a >> i);
162            }
163            if (b >> i) << i != b {
164                self.recalc_at((b - 1) >> i);
165            }
166        }
167    }
168    pub fn fold<R>(&mut self, range: R) -> M::Agg
169    where
170        R: RangeBounds<usize>,
171    {
172        let range = range.to_range_bounded(0, self.len).expect("invalid range");
173        if range.is_empty() {
174            return M::agg_unit();
175        }
176        if let Some(result) = (|| {
177            let mut left_index = range.start + self.n - 1;
178            let mut right_index = range.end + self.n;
179            let mut left = M::agg_unit();
180            let mut right = M::agg_unit();
181            let mut has_left = false;
182            let mut has_right = false;
183            for _ in 0..(left_index ^ right_index).ilog2() {
184                if left_index & 1 == 0 {
185                    left = M::agg_operate(&left, &self.seg[left_index ^ 1]);
186                    has_left = true;
187                }
188                if right_index & 1 != 0 {
189                    right = M::agg_operate(&self.seg[right_index ^ 1], &right);
190                    has_right = true;
191                }
192                left_index >>= 1;
193                right_index >>= 1;
194                if has_left {
195                    left = M::act_agg(&left, &self.lazy[left_index])?;
196                }
197                if has_right && right_index < self.n {
198                    right = M::act_agg(&right, &self.lazy[right_index])?;
199                }
200            }
201            let mut result = M::agg_operate(&left, &right);
202            while left_index > 1 {
203                left_index >>= 1;
204                result = M::act_agg(&result, &self.lazy[left_index])?;
205            }
206            Some(result)
207        })() {
208            return result;
209        }
210        let mut l = range.start + self.n;
211        let mut r = range.end + self.n;
212        self.propagate(l);
213        self.propagate(r - 1);
214        let mut vl = M::agg_unit();
215        let mut vr = M::agg_unit();
216        while l < r {
217            if l & 1 != 0 {
218                vl = M::agg_operate(&vl, &self.seg[l]);
219                l += 1;
220            }
221            if r & 1 != 0 {
222                r -= 1;
223                vr = M::agg_operate(&self.seg[r], &vr);
224            }
225            l /= 2;
226            r /= 2;
227        }
228        M::agg_operate(&vl, &vr)
229    }
230    pub fn set(&mut self, k: usize, x: M::Agg) {
231        assert!(k < self.len);
232        let k = k + self.n;
233        self.propagate(k);
234        self.seg[k] = x;
235        self.recalc(k);
236    }
237    pub fn get(&mut self, k: usize) -> M::Agg {
238        self.fold(k..k + 1)
239    }
240    pub fn fold_all(&self) -> M::Agg {
241        self.seg[1].clone()
242    }
243    pub fn partition_point_acc<P>(&mut self, left: usize, mut pred: P) -> usize
244    where
245        P: FnMut(&M::Agg) -> bool,
246    {
247        let mut acc = M::agg_unit();
248        if left == self.len {
249            return self.len;
250        }
251        let mut k = left + self.n;
252        self.propagate(k);
253        loop {
254            while k & 1 == 0 {
255                k >>= 1;
256            }
257            let nacc = M::agg_operate(&acc, &self.seg[k]);
258            if !pred(&nacc) {
259                while k < self.n {
260                    self.propagate_at(k);
261                    k <<= 1;
262                    let nacc = M::agg_operate(&acc, &self.seg[k]);
263                    if pred(&nacc) {
264                        acc = nacc;
265                        k += 1;
266                    }
267                }
268                return k - self.n;
269            }
270            acc = nacc;
271            k += 1;
272            if k.is_power_of_two() {
273                return self.len;
274            }
275        }
276    }
277    pub fn rpartition_point_acc<P>(&mut self, right: usize, mut pred: P) -> usize
278    where
279        P: FnMut(&M::Agg) -> bool,
280    {
281        let mut acc = M::agg_unit();
282        if right == 0 {
283            return 0;
284        }
285        let mut k = right + self.n;
286        self.propagate(k - 1);
287        loop {
288            k -= 1;
289            while k > 1 && k & 1 != 0 {
290                k >>= 1;
291            }
292            let nacc = M::agg_operate(&self.seg[k], &acc);
293            if !pred(&nacc) {
294                while k < self.n {
295                    self.propagate_at(k);
296                    k = 2 * k + 1;
297                    let nacc = M::agg_operate(&self.seg[k], &acc);
298                    if pred(&nacc) {
299                        acc = nacc;
300                        k -= 1;
301                    }
302                }
303                return k + 1 - self.n;
304            }
305            acc = nacc;
306            if k.is_power_of_two() {
307                return 0;
308            }
309        }
310    }

Source

fn propagate(&mut self, k: usize)

Examples found in repository ?

crates/competitive/src/data_structure/lazy_segment_tree.rs (line 212)

168    pub fn fold<R>(&mut self, range: R) -> M::Agg
169    where
170        R: RangeBounds<usize>,
171    {
172        let range = range.to_range_bounded(0, self.len).expect("invalid range");
173        if range.is_empty() {
174            return M::agg_unit();
175        }
176        if let Some(result) = (|| {
177            let mut left_index = range.start + self.n - 1;
178            let mut right_index = range.end + self.n;
179            let mut left = M::agg_unit();
180            let mut right = M::agg_unit();
181            let mut has_left = false;
182            let mut has_right = false;
183            for _ in 0..(left_index ^ right_index).ilog2() {
184                if left_index & 1 == 0 {
185                    left = M::agg_operate(&left, &self.seg[left_index ^ 1]);
186                    has_left = true;
187                }
188                if right_index & 1 != 0 {
189                    right = M::agg_operate(&self.seg[right_index ^ 1], &right);
190                    has_right = true;
191                }
192                left_index >>= 1;
193                right_index >>= 1;
194                if has_left {
195                    left = M::act_agg(&left, &self.lazy[left_index])?;
196                }
197                if has_right && right_index < self.n {
198                    right = M::act_agg(&right, &self.lazy[right_index])?;
199                }
200            }
201            let mut result = M::agg_operate(&left, &right);
202            while left_index > 1 {
203                left_index >>= 1;
204                result = M::act_agg(&result, &self.lazy[left_index])?;
205            }
206            Some(result)
207        })() {
208            return result;
209        }
210        let mut l = range.start + self.n;
211        let mut r = range.end + self.n;
212        self.propagate(l);
213        self.propagate(r - 1);
214        let mut vl = M::agg_unit();
215        let mut vr = M::agg_unit();
216        while l < r {
217            if l & 1 != 0 {
218                vl = M::agg_operate(&vl, &self.seg[l]);
219                l += 1;
220            }
221            if r & 1 != 0 {
222                r -= 1;
223                vr = M::agg_operate(&self.seg[r], &vr);
224            }
225            l /= 2;
226            r /= 2;
227        }
228        M::agg_operate(&vl, &vr)
229    }
230    pub fn set(&mut self, k: usize, x: M::Agg) {
231        assert!(k < self.len);
232        let k = k + self.n;
233        self.propagate(k);
234        self.seg[k] = x;
235        self.recalc(k);
236    }
237    pub fn get(&mut self, k: usize) -> M::Agg {
238        self.fold(k..k + 1)
239    }
240    pub fn fold_all(&self) -> M::Agg {
241        self.seg[1].clone()
242    }
243    pub fn partition_point_acc<P>(&mut self, left: usize, mut pred: P) -> usize
244    where
245        P: FnMut(&M::Agg) -> bool,
246    {
247        let mut acc = M::agg_unit();
248        if left == self.len {
249            return self.len;
250        }
251        let mut k = left + self.n;
252        self.propagate(k);
253        loop {
254            while k & 1 == 0 {
255                k >>= 1;
256            }
257            let nacc = M::agg_operate(&acc, &self.seg[k]);
258            if !pred(&nacc) {
259                while k < self.n {
260                    self.propagate_at(k);
261                    k <<= 1;
262                    let nacc = M::agg_operate(&acc, &self.seg[k]);
263                    if pred(&nacc) {
264                        acc = nacc;
265                        k += 1;
266                    }
267                }
268                return k - self.n;
269            }
270            acc = nacc;
271            k += 1;
272            if k.is_power_of_two() {
273                return self.len;
274            }
275        }
276    }
277    pub fn rpartition_point_acc<P>(&mut self, right: usize, mut pred: P) -> usize
278    where
279        P: FnMut(&M::Agg) -> bool,
280    {
281        let mut acc = M::agg_unit();
282        if right == 0 {
283            return 0;
284        }
285        let mut k = right + self.n;
286        self.propagate(k - 1);
287        loop {
288            k -= 1;
289            while k > 1 && k & 1 != 0 {
290                k >>= 1;
291            }
292            let nacc = M::agg_operate(&self.seg[k], &acc);
293            if !pred(&nacc) {
294                while k < self.n {
295                    self.propagate_at(k);
296                    k = 2 * k + 1;
297                    let nacc = M::agg_operate(&self.seg[k], &acc);
298                    if pred(&nacc) {
299                        acc = nacc;
300                        k -= 1;
301                    }
302                }
303                return k + 1 - self.n;
304            }
305            acc = nacc;
306            if k.is_power_of_two() {
307                return 0;
308            }
309        }
310    }

Source

fn recalc(&mut self, k: usize)

Examples found in repository ?

crates/competitive/src/data_structure/lazy_segment_tree.rs (line 235)

230    pub fn set(&mut self, k: usize, x: M::Agg) {
231        assert!(k < self.len);
232        let k = k + self.n;
233        self.propagate(k);
234        self.seg[k] = x;
235        self.recalc(k);
236    }

Source

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

Examples found in repository ?

crates/aizu_online_judge/src/dsl/dsl_2_d.rs (line 20)

12pub fn dsl_2_d(reader: impl Read, writer: impl Write) {
13    prepare_io!(reader, writer);
14    sc!(n, q);
15    let mut seg = LazySegmentTree::<RangeMinRangeUpdate<_>>::new(n);
16    for _ in 0..q {
17        sc!(query: Query);
18        match query {
19            Query::Update { s, t, x } => {
20                seg.update(s..t + 1, Some(x));
21            }
22            Query::Get { i } => {
23                pp!(seg.fold(i..i + 1));
24            }
25        }
26    }
27}

More examples

Hide additional examples

crates/aizu_online_judge/src/dsl/dsl_2_f.rs (line 20)

12pub fn dsl_2_f(reader: impl Read, writer: impl Write) {
13    prepare_io!(reader, writer);
14    sc!(n, q);
15    let mut seg = LazySegmentTree::<RangeMinRangeUpdate<_>>::new(n);
16    for _ in 0..q {
17        sc!(query: Query);
18        match query {
19            Query::Update { s, t, x } => {
20                seg.update(s..t + 1, Some(x));
21            }
22            Query::Fold { s, t } => {
23                pp!(seg.fold(s..t + 1));
24            }
25        }
26    }
27}

crates/aizu_online_judge/src/dsl/dsl_2_e.rs (line 20)

12pub fn dsl_2_e(reader: impl Read, writer: impl Write) {
13    prepare_io!(reader, writer);
14    sc!(n, q);
15    let mut seg = LazySegmentTree::<RangeSumRangeAdd<_>>::from_keys(std::iter::repeat_n(0, n));
16    for _ in 0..q {
17        sc!(query: Query);
18        match query {
19            Query::Add { s, t, x } => {
20                seg.update(s - 1..t, x);
21            }
22            Query::Get { i } => {
23                pp!(seg.fold(i - 1..i).0);
24            }
25        }
26    }
27}

crates/aizu_online_judge/src/dsl/dsl_2_h.rs (line 20)

12pub fn dsl_2_h(reader: impl Read, writer: impl Write) {
13    prepare_io!(reader, writer);
14    sc!(n, q);
15    let mut seg = LazySegmentTree::<RangeMinRangeAdd<_>>::from_keys(std::iter::repeat_n(0, n));
16    for _ in 0..q {
17        sc!(query: Query);
18        match query {
19            Query::Add { s, t, x } => {
20                seg.update(s..t + 1, x);
21            }
22            Query::Min { s, t } => {
23                pp!(seg.fold(s..t + 1));
24            }
25        }
26    }
27}

crates/aizu_online_judge/src/dsl/dsl_2_g.rs (line 20)

12pub fn dsl_2_g(reader: impl Read, writer: impl Write) {
13    prepare_io!(reader, writer);
14    sc!(n, q);
15    let mut seg = LazySegmentTree::<RangeSumRangeAdd<_>>::from_keys(std::iter::repeat_n(0, n));
16    for _ in 0..q {
17        sc!(query: Query);
18        match query {
19            Query::Add { s, t, x } => {
20                seg.update(s - 1..t, x);
21            }
22            Query::Sum { s, t } => {
23                pp!(seg.fold(s - 1..t).0);
24            }
25        }
26    }
27}

crates/library_checker/src/data_structure/range_affine_range_sum.rs (line 23)

15pub fn range_affine_range_sum(reader: impl Read, writer: impl Write) {
16    prepare_io!(reader, writer);
17    sc!(n, q, a: [M; iter n]);
18    let mut seg = LazySegmentTree::<RangeSumRangeLinear<_>>::from_keys(a);
19    for _ in 0..q {
20        sc!(query: Query);
21        match query {
22            Query::Update { l, r, bc } => {
23                seg.update(l..r, bc);
24            }
25            Query::Fold { l, r } => {
26                pp!(seg.fold(l..r).0);
27            }
28        }
29    }
30}

Additional examples can be found in:

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.rs (line 238)

237    pub fn get(&mut self, k: usize) -> M::Agg {
238        self.fold(k..k + 1)
239    }

More examples

Hide additional examples

crates/aizu_online_judge/src/dsl/dsl_2_d.rs (line 23)

12pub fn dsl_2_d(reader: impl Read, writer: impl Write) {
13    prepare_io!(reader, writer);
14    sc!(n, q);
15    let mut seg = LazySegmentTree::<RangeMinRangeUpdate<_>>::new(n);
16    for _ in 0..q {
17        sc!(query: Query);
18        match query {
19            Query::Update { s, t, x } => {
20                seg.update(s..t + 1, Some(x));
21            }
22            Query::Get { i } => {
23                pp!(seg.fold(i..i + 1));
24            }
25        }
26    }
27}

crates/aizu_online_judge/src/dsl/dsl_2_f.rs (line 23)

12pub fn dsl_2_f(reader: impl Read, writer: impl Write) {
13    prepare_io!(reader, writer);
14    sc!(n, q);
15    let mut seg = LazySegmentTree::<RangeMinRangeUpdate<_>>::new(n);
16    for _ in 0..q {
17        sc!(query: Query);
18        match query {
19            Query::Update { s, t, x } => {
20                seg.update(s..t + 1, Some(x));
21            }
22            Query::Fold { s, t } => {
23                pp!(seg.fold(s..t + 1));
24            }
25        }
26    }
27}

crates/aizu_online_judge/src/dsl/dsl_2_e.rs (line 23)

12pub fn dsl_2_e(reader: impl Read, writer: impl Write) {
13    prepare_io!(reader, writer);
14    sc!(n, q);
15    let mut seg = LazySegmentTree::<RangeSumRangeAdd<_>>::from_keys(std::iter::repeat_n(0, n));
16    for _ in 0..q {
17        sc!(query: Query);
18        match query {
19            Query::Add { s, t, x } => {
20                seg.update(s - 1..t, x);
21            }
22            Query::Get { i } => {
23                pp!(seg.fold(i - 1..i).0);
24            }
25        }
26    }
27}

crates/aizu_online_judge/src/dsl/dsl_2_h.rs (line 23)

12pub fn dsl_2_h(reader: impl Read, writer: impl Write) {
13    prepare_io!(reader, writer);
14    sc!(n, q);
15    let mut seg = LazySegmentTree::<RangeMinRangeAdd<_>>::from_keys(std::iter::repeat_n(0, n));
16    for _ in 0..q {
17        sc!(query: Query);
18        match query {
19            Query::Add { s, t, x } => {
20                seg.update(s..t + 1, x);
21            }
22            Query::Min { s, t } => {
23                pp!(seg.fold(s..t + 1));
24            }
25        }
26    }
27}

crates/aizu_online_judge/src/dsl/dsl_2_g.rs (line 23)

12pub fn dsl_2_g(reader: impl Read, writer: impl Write) {
13    prepare_io!(reader, writer);
14    sc!(n, q);
15    let mut seg = LazySegmentTree::<RangeSumRangeAdd<_>>::from_keys(std::iter::repeat_n(0, n));
16    for _ in 0..q {
17        sc!(query: Query);
18        match query {
19            Query::Add { s, t, x } => {
20                seg.update(s - 1..t, x);
21            }
22            Query::Sum { s, t } => {
23                pp!(seg.fold(s - 1..t).0);
24            }
25        }
26    }
27}

Additional examples can be found in:

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(&self) -> M::Agg

Examples found in repository ?

crates/library_checker/src/data_structure/area_of_union_of_rectangles.rs (line 36)

9pub fn area_of_union_of_rectangles(reader: impl Read, writer: impl Write) {
10    prepare_io!(buffered; reader, writer);
11    sc!(n, rectangles: [(u32, u32, u32, u32); n]);
12    let endpoints: Vec<_> = rectangles.iter().flat_map(|&(_, d, _, u)| [d, u]).collect();
13    let mut ys = endpoints.clone();
14    ys.radix_sort_by_key(|&y| y);
15    ys.dedup();
16    let search = StaticSearch::from_sorted(&ys);
17    let mut positions = vec![0; endpoints.len()];
18    search.lower_bound_batch(&endpoints, &mut positions);
19    let mut events: Vec<_> = rectangles
20        .into_iter()
21        .zip(positions.as_chunks().0)
22        .flat_map(|((l, _, r, _), &[d, u])| {
23            let d = d as u32;
24            let u = u as u32;
25            [(l, d, u, 1), (r, d, u, -1)]
26        })
27        .collect();
28    events.radix_sort_by_key(|&(x, ..)| x);
29    let mut seg = LazySegmentTree::<RangeMinCountRangeAdd<i32>>::from_vec(
30        ys.windows(2).map(|w| (0, (w[1] - w[0]) as usize)).collect(),
31    );
32    let height = (ys[ys.len() - 1] - ys[0]) as usize;
33    let mut prev_x = 0;
34    let mut area = 0u64;
35    for (x, d, u, delta) in events {
36        let (minimum, count) = seg.fold_all();
37        let covered = height - if minimum == 0 { count } else { 0 };
38        area += (x - prev_x) as u64 * covered as u64;
39        seg.update(d as usize..u as usize, delta);
40        prev_x = x;
41    }
42    pp!(area);
43}

Source

pub fn partition_point_acc(&mut self, left: usize, pred: P) -> usize
where P: FnMut(&M::Agg) -> bool,

Source

pub fn rpartition_point_acc(&mut self, right: usize, pred: P) -> usize
where P: FnMut(&M::Agg) -> bool,

Trait Implementations§

Source §

impl<M> Clone for LazySegmentTree<M>
where M: LazyMapMonoid,

Source §

fn clone(&self) -> Self

Returns a duplicate of the value. Read more

1.0.0 (const: unstable) · Source§

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

Performs copy-assignment from source. Read more

Source §

impl<M> Debug for LazySegmentTree<M>
where M: LazyMapMonoid<Agg: Debug, Act: Debug>,

Source §

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

Formats the value using the given formatter. Read more

Auto Trait Implementations§

§

impl<M> Freeze for LazySegmentTree<M>
where Vec<<M as LazyMapMonoid>::Agg>: Freeze, Vec<<M as LazyMapMonoid>::Act>: Freeze,

§

impl<M> RefUnwindSafe for LazySegmentTree<M>
where Vec<<M as LazyMapMonoid>::Agg>: RefUnwindSafe, Vec<<M as LazyMapMonoid>::Act>: RefUnwindSafe,

§

impl<M> Send for LazySegmentTree<M>
where Vec<<M as LazyMapMonoid>::Agg>: Send, Vec<<M as LazyMapMonoid>::Act>: Send,

§

impl<M> Sync for LazySegmentTree<M>
where Vec<<M as LazyMapMonoid>::Agg>: Sync, Vec<<M as LazyMapMonoid>::Act>: Sync,

§

impl<M> Unpin for LazySegmentTree<M>
where Vec<<M as LazyMapMonoid>::Agg>: Unpin, Vec<<M as LazyMapMonoid>::Act>: Unpin,

§

impl<M> UnsafeUnpin for LazySegmentTree<M>
where Vec<<M as LazyMapMonoid>::Agg>: UnsafeUnpin, Vec<<M as LazyMapMonoid>::Act>: UnsafeUnpin,

§

impl<M> UnwindSafe for LazySegmentTree<M>
where Vec<<M as LazyMapMonoid>::Agg>: UnwindSafe, Vec<<M as LazyMapMonoid>::Act>: UnwindSafe,

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 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 §

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 for T
where U: Into<T>,

Source §

type Error = !

The type returned in the event of a conversion error.

Source §

fn try_from(value: U) -> Result<T, !>

Performs the conversion.

Source §

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

Source §

type Error = >::Error

The type returned in the event of a conversion error.

Source §

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

Performs the conversion.

Struct LazySegmentTree Copy item path

Fields§

Implementations§

impl<M> LazySegmentTree<M>where M: LazyMapMonoid,

pub fn new(len: usize) -> Self

pub fn from_vec(v: Vec<M::Agg>) -> Self

pub fn from_keys(keys: impl ExactSizeIterator<Item = M::Key>) -> Self

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

fn recalc_at(&mut self, k: usize)

fn propagate_at(&mut self, k: usize)

fn propagate(&mut self, k: usize)

fn recalc(&mut self, k: usize)

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

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

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

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

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

pub fn partition_point_acc<P>(&mut self, left: usize, pred: P) -> usizewhere P: FnMut(&M::Agg) -> bool,

pub fn rpartition_point_acc<P>(&mut self, right: usize, pred: P) -> usizewhere P: FnMut(&M::Agg) -> bool,

Trait Implementations§

impl<M> Clone for LazySegmentTree<M>where M: LazyMapMonoid,

fn clone(&self) -> Self

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

impl<M> Debug for LazySegmentTree<M>where M: LazyMapMonoid<Agg: Debug, Act: Debug>,

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

Auto Trait Implementations§

impl<M> Freeze for LazySegmentTree<M>where Vec<<M as LazyMapMonoid>::Agg>: Freeze, Vec<<M as LazyMapMonoid>::Act>: Freeze,

impl<M> RefUnwindSafe for LazySegmentTree<M>where Vec<<M as LazyMapMonoid>::Agg>: RefUnwindSafe, Vec<<M as LazyMapMonoid>::Act>: RefUnwindSafe,

impl<M> Send for LazySegmentTree<M>where Vec<<M as LazyMapMonoid>::Agg>: Send, Vec<<M as LazyMapMonoid>::Act>: Send,

impl<M> Sync for LazySegmentTree<M>where Vec<<M as LazyMapMonoid>::Agg>: Sync, Vec<<M as LazyMapMonoid>::Act>: Sync,

impl<M> Unpin for LazySegmentTree<M>where Vec<<M as LazyMapMonoid>::Agg>: Unpin, Vec<<M as LazyMapMonoid>::Act>: Unpin,

impl<M> UnsafeUnpin for LazySegmentTree<M>where Vec<<M as LazyMapMonoid>::Agg>: UnsafeUnpin, Vec<<M as LazyMapMonoid>::Act>: UnsafeUnpin,

impl<M> UnwindSafe for LazySegmentTree<M>where Vec<<M as LazyMapMonoid>::Agg>: UnwindSafe, Vec<<M as LazyMapMonoid>::Act>: UnwindSafe,

Blanket Implementations§

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

fn type_id(&self) -> TypeId

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

fn borrow(&self) -> &T

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

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

impl<T> CloneToUninit for Twhere T: Clone,

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

impl<T> From<T> for T

fn from(t: T) -> T

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

fn into(self) -> U

impl<T> ToArrayVecScalar for T

fn to_array_vec_scalar(self) -> ArrayVecScalar<T>

impl<T> ToOwned for Twhere T: Clone,

type Owned = T

fn to_owned(&self) -> T

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

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

type Error = !

fn try_from(value: U) -> Result<T, !>

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

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

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

Struct LazySegmentTree

impl<M> LazySegmentTree<M>
where M: LazyMapMonoid,

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

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

pub fn partition_point_acc<P>(&mut self, left: usize, pred: P) -> usize
where P: FnMut(&M::Agg) -> bool,

pub fn rpartition_point_acc<P>(&mut self, right: usize, pred: P) -> usize
where P: FnMut(&M::Agg) -> bool,

impl<M> Clone for LazySegmentTree<M>
where M: LazyMapMonoid,

impl<M> Debug for LazySegmentTree<M>
where M: LazyMapMonoid<Agg: Debug, Act: Debug>,

impl<M> Freeze for LazySegmentTree<M>
where Vec<<M as LazyMapMonoid>::Agg>: Freeze, Vec<<M as LazyMapMonoid>::Act>: Freeze,

impl<M> RefUnwindSafe for LazySegmentTree<M>
where Vec<<M as LazyMapMonoid>::Agg>: RefUnwindSafe, Vec<<M as LazyMapMonoid>::Act>: RefUnwindSafe,

impl<M> Send for LazySegmentTree<M>
where Vec<<M as LazyMapMonoid>::Agg>: Send, Vec<<M as LazyMapMonoid>::Act>: Send,

impl<M> Sync for LazySegmentTree<M>
where Vec<<M as LazyMapMonoid>::Agg>: Sync, Vec<<M as LazyMapMonoid>::Act>: Sync,

impl<M> Unpin for LazySegmentTree<M>
where Vec<<M as LazyMapMonoid>::Agg>: Unpin, Vec<<M as LazyMapMonoid>::Act>: Unpin,

impl<M> UnsafeUnpin for LazySegmentTree<M>
where Vec<<M as LazyMapMonoid>::Agg>: UnsafeUnpin, Vec<<M as LazyMapMonoid>::Act>: UnsafeUnpin,

impl<M> UnwindSafe for LazySegmentTree<M>
where Vec<<M as LazyMapMonoid>::Agg>: UnwindSafe, Vec<<M as LazyMapMonoid>::Act>: UnwindSafe,

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

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

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

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

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

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

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

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