LazySegmentTree

competitive::data_structure

Struct LazySegmentTree 

Source 
pub struct LazySegmentTree<M>
where
    M: LazyMapMonoid,
{
    n: usize,
    seg: Vec<(M::Agg, M::Act)>,
}

Fields§

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

Implementations§

Source§

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

Source

pub fn new(n: usize) -> Self

Examples found in repository?
crates/aizu_online_judge/src/dsl/dsl_2_d.rs (line 10)
6pub fn dsl_2_d(reader: impl Read, mut writer: impl Write) {
7    let s = read_all_unchecked(reader);
8    let mut scanner = Scanner::new(&s);
9    scan!(scanner, n, q);
10    let mut seg = LazySegmentTree::<RangeMinRangeUpdate<_>>::new(n);
11    for _ in 0..q {
12        match scanner.scan::<usize>() {
13            0 => {
14                scan!(scanner, s, t, x: i32);
15                seg.update(s..t + 1, Some(x));
16            }
17            1 => {
18                scan!(scanner, i);
19                writeln!(writer, "{}", seg.fold(i..i + 1)).ok();
20            }
21            _ => unreachable!("unknown query"),
22        }
23    }
24}
More examples
Hide additional examples
crates/aizu_online_judge/src/dsl/dsl_2_f.rs (line 10)
6pub fn dsl_2_f(reader: impl Read, mut writer: impl Write) {
7    let s = read_all_unchecked(reader);
8    let mut scanner = Scanner::new(&s);
9    scan!(scanner, n, q);
10    let mut seg = LazySegmentTree::<RangeMinRangeUpdate<_>>::new(n);
11    for _ in 0..q {
12        match scanner.scan::<usize>() {
13            0 => {
14                scan!(scanner, s, t, x: i32);
15                seg.update(s..t + 1, Some(x));
16            }
17            1 => {
18                scan!(scanner, s, t);
19                writeln!(writer, "{}", seg.fold(s..t + 1)).ok();
20            }
21            _ => unreachable!("unknown query"),
22        }
23    }
24}
Source

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

Examples found in repository?
crates/aizu_online_judge/src/dsl/dsl_2_h.rs (line 10)
6pub fn dsl_2_h(reader: impl Read, mut writer: impl Write) {
7    let s = read_all_unchecked(reader);
8    let mut scanner = Scanner::new(&s);
9    scan!(scanner, n, q);
10    let mut seg = LazySegmentTree::<RangeMinRangeAdd<_>>::from_vec(vec![0; n]);
11    for _ in 0..q {
12        match scanner.scan::<usize>() {
13            0 => {
14                scan!(scanner, s, t, x: i64);
15                seg.update(s..t + 1, x);
16            }
17            1 => {
18                scan!(scanner, s, t);
19                writeln!(writer, "{}", seg.fold(s..t + 1)).ok();
20            }
21            _ => unreachable!("unknown query"),
22        }
23    }
24}
More examples
Hide additional examples
crates/aizu_online_judge/src/dsl/dsl_2_e.rs (line 10)
6pub fn dsl_2_e(reader: impl Read, mut writer: impl Write) {
7    let s = read_all_unchecked(reader);
8    let mut scanner = Scanner::new(&s);
9    scan!(scanner, n, q);
10    let mut seg = LazySegmentTree::<RangeSumRangeAdd<_>>::from_vec(vec![(0, 1); n]);
11    for _ in 0..q {
12        match scanner.scan::<usize>() {
13            0 => {
14                scan!(scanner, s, t, x: u64);
15                seg.update(s - 1..t, x);
16            }
17            1 => {
18                scan!(scanner, i);
19                writeln!(writer, "{}", seg.fold(i - 1..i).0).ok();
20            }
21            _ => unreachable!("unknown query"),
22        }
23    }
24}
crates/aizu_online_judge/src/dsl/dsl_2_g.rs (line 10)
6pub fn dsl_2_g(reader: impl Read, mut writer: impl Write) {
7    let s = read_all_unchecked(reader);
8    let mut scanner = Scanner::new(&s);
9    scan!(scanner, n, q);
10    let mut seg = LazySegmentTree::<RangeSumRangeAdd<_>>::from_vec(vec![(0, 1); n]);
11    for _ in 0..q {
12        match scanner.scan::<usize>() {
13            0 => {
14                scan!(scanner, s, t, x: u64);
15                seg.update(s - 1..t, x);
16            }
17            1 => {
18                scan!(scanner, s, t);
19                writeln!(writer, "{}", seg.fold(s - 1..t).0).ok();
20            }
21            _ => unreachable!("unknown query"),
22        }
23    }
24}
crates/aizu_online_judge/src/dsl/dsl_2_i.rs (line 10)
6pub fn dsl_2_i(reader: impl Read, mut writer: impl Write) {
7    let s = read_all_unchecked(reader);
8    let mut scanner = Scanner::new(&s);
9    scan!(scanner, n, q);
10    let mut seg = LazySegmentTree::<RangeSumRangeUpdate<_>>::from_vec(vec![(0, 1); n]);
11    for _ in 0..q {
12        match scanner.scan::<usize>() {
13            0 => {
14                scan!(scanner, s, t, x: i64);
15                seg.update(s..t + 1, Some(x));
16            }
17            1 => {
18                scan!(scanner, s, t);
19                writeln!(writer, "{}", seg.fold(s..t + 1).0).ok();
20            }
21            _ => unreachable!("unknown query"),
22        }
23    }
24}
crates/library_checker/src/data_structure/range_affine_range_sum.rs (lines 14-16)
10pub fn range_affine_range_sum(reader: impl Read, mut writer: impl Write) {
11    let s = read_all_unchecked(reader);
12    let mut scanner = Scanner::new(&s);
13    scan!(scanner, n, q, a: [MInt998244353]);
14    let mut seg = LazySegmentTree::<RangeSumRangeLinear<_>>::from_vec(
15        a.take(n).map(|x| (x, MInt998244353::one())).collect::<_>(),
16    );
17    for _ in 0..q {
18        match scanner.scan::<usize>() {
19            0 => {
20                scan!(scanner, l, r, bc: (MInt998244353, MInt998244353));
21                seg.update(l..r, bc);
22            }
23            1 => {
24                scan!(scanner, l, r);
25                writeln!(writer, "{}", seg.fold(l..r).0).ok();
26            }
27            _ => unreachable!("unknown query"),
28        }
29    }
30}
crates/aizu_online_judge/src/grl/grl_5_e.rs (line 24)
12pub fn grl_5_e(reader: impl Read, mut writer: impl Write) {
13    let s = read_all_unchecked(reader);
14    let mut scanner = Scanner::new(&s);
15    scan!(scanner, n, c: [SizedCollect<usize>]);
16    let edges = c
17        .take(n)
18        .enumerate()
19        .flat_map(|(u, it)| it.into_iter().map(move |v| (u, v)))
20        .collect();
21    let mut graph = UndirectedSparseGraph::from_edges(n, edges);
22    let hld = HeavyLightDecomposition::new(0, &mut graph);
23    type M = (AdditiveOperation<u64>, AdditiveOperation<u64>);
24    let mut seg = LazySegmentTree::<RangeSumRangeAdd<_>>::from_vec(vec![(0u64, 1u64); n]);
25
26    scan!(scanner, q);
27    for _ in 0..q {
28        match scanner.scan::<usize>() {
29            0 => {
30                scan!(scanner, v, w: u64);
31                hld.update(0, v, true, |l, r| seg.update(l..r, w));
32            }
33            1 => {
34                scan!(scanner, u);
35                let ans = hld.query::<M, _>(0, u, true, |l, r| seg.fold(l..r)).0;
36                writeln!(writer, "{}", ans).ok();
37            }
38            _ => unreachable!("unknown query"),
39        }
40    }
41}
Additional examples can be found in:
Source

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

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 93)
90    fn propagate_at(&mut self, k: usize) {
91        debug_assert!(k < self.n);
92        let x = replace(&mut self.seg[k].1, M::act_unit());
93        self.update_at(2 * k, &x);
94        self.update_at(2 * k + 1, &x);
95    }
96    #[inline]
97    fn propagate(&mut self, k: usize, right: bool, nofilt: bool) {
98        let right = right as usize;
99        for i in (1..(k + 1 - right).next_power_of_two().trailing_zeros()).rev() {
100            if nofilt || (k >> i) << i != k {
101                self.propagate_at((k - right) >> i);
102            }
103        }
104    }
105    #[inline]
106    fn recalc(&mut self, k: usize, right: bool, nofilt: bool) {
107        let right = right as usize;
108        for i in 1..(k + 1 - right).next_power_of_two().trailing_zeros() {
109            if nofilt || (k >> i) << i != k {
110                self.recalc_at((k - right) >> i);
111            }
112        }
113    }
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    }
Source

fn recalc_at(&mut self, k: usize)

Examples found in repository?
crates/competitive/src/data_structure/lazy_segment_tree.rs (line 80)
71    fn update_at(&mut self, k: usize, x: &M::Act) {
72        let nx = M::act_agg(&self.seg[k].0, x);
73        if k < self.n {
74            self.seg[k].1 = M::act_operate(&self.seg[k].1, x);
75        }
76        if let Some(nx) = nx {
77            self.seg[k].0 = nx;
78        } else if k < self.n {
79            self.propagate_at(k);
80            self.recalc_at(k);
81        } else {
82            panic!("act failed on leaf");
83        }
84    }
85    #[inline]
86    fn recalc_at(&mut self, k: usize) {
87        self.seg[k].0 = M::agg_operate(&self.seg[2 * k].0, &self.seg[2 * k + 1].0);
88    }
89    #[inline]
90    fn propagate_at(&mut self, k: usize) {
91        debug_assert!(k < self.n);
92        let x = replace(&mut self.seg[k].1, M::act_unit());
93        self.update_at(2 * k, &x);
94        self.update_at(2 * k + 1, &x);
95    }
96    #[inline]
97    fn propagate(&mut self, k: usize, right: bool, nofilt: bool) {
98        let right = right as usize;
99        for i in (1..(k + 1 - right).next_power_of_two().trailing_zeros()).rev() {
100            if nofilt || (k >> i) << i != k {
101                self.propagate_at((k - right) >> i);
102            }
103        }
104    }
105    #[inline]
106    fn recalc(&mut self, k: usize, right: bool, nofilt: bool) {
107        let right = right as usize;
108        for i in 1..(k + 1 - right).next_power_of_two().trailing_zeros() {
109            if nofilt || (k >> i) << i != k {
110                self.recalc_at((k - right) >> i);
111            }
112        }
113    }
Source

fn propagate_at(&mut self, k: usize)

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

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

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

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

Examples found in repository?
crates/competitive/src/data_structure/lazy_segment_tree.rs (line 135)
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    }
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 15)
6pub fn dsl_2_d(reader: impl Read, mut writer: impl Write) {
7    let s = read_all_unchecked(reader);
8    let mut scanner = Scanner::new(&s);
9    scan!(scanner, n, q);
10    let mut seg = LazySegmentTree::<RangeMinRangeUpdate<_>>::new(n);
11    for _ in 0..q {
12        match scanner.scan::<usize>() {
13            0 => {
14                scan!(scanner, s, t, x: i32);
15                seg.update(s..t + 1, Some(x));
16            }
17            1 => {
18                scan!(scanner, i);
19                writeln!(writer, "{}", seg.fold(i..i + 1)).ok();
20            }
21            _ => unreachable!("unknown query"),
22        }
23    }
24}
More examples
Hide additional examples
crates/aizu_online_judge/src/dsl/dsl_2_f.rs (line 15)
6pub fn dsl_2_f(reader: impl Read, mut writer: impl Write) {
7    let s = read_all_unchecked(reader);
8    let mut scanner = Scanner::new(&s);
9    scan!(scanner, n, q);
10    let mut seg = LazySegmentTree::<RangeMinRangeUpdate<_>>::new(n);
11    for _ in 0..q {
12        match scanner.scan::<usize>() {
13            0 => {
14                scan!(scanner, s, t, x: i32);
15                seg.update(s..t + 1, Some(x));
16            }
17            1 => {
18                scan!(scanner, s, t);
19                writeln!(writer, "{}", seg.fold(s..t + 1)).ok();
20            }
21            _ => unreachable!("unknown query"),
22        }
23    }
24}
crates/aizu_online_judge/src/dsl/dsl_2_h.rs (line 15)
6pub fn dsl_2_h(reader: impl Read, mut writer: impl Write) {
7    let s = read_all_unchecked(reader);
8    let mut scanner = Scanner::new(&s);
9    scan!(scanner, n, q);
10    let mut seg = LazySegmentTree::<RangeMinRangeAdd<_>>::from_vec(vec![0; n]);
11    for _ in 0..q {
12        match scanner.scan::<usize>() {
13            0 => {
14                scan!(scanner, s, t, x: i64);
15                seg.update(s..t + 1, x);
16            }
17            1 => {
18                scan!(scanner, s, t);
19                writeln!(writer, "{}", seg.fold(s..t + 1)).ok();
20            }
21            _ => unreachable!("unknown query"),
22        }
23    }
24}
crates/aizu_online_judge/src/dsl/dsl_2_e.rs (line 15)
6pub fn dsl_2_e(reader: impl Read, mut writer: impl Write) {
7    let s = read_all_unchecked(reader);
8    let mut scanner = Scanner::new(&s);
9    scan!(scanner, n, q);
10    let mut seg = LazySegmentTree::<RangeSumRangeAdd<_>>::from_vec(vec![(0, 1); n]);
11    for _ in 0..q {
12        match scanner.scan::<usize>() {
13            0 => {
14                scan!(scanner, s, t, x: u64);
15                seg.update(s - 1..t, x);
16            }
17            1 => {
18                scan!(scanner, i);
19                writeln!(writer, "{}", seg.fold(i - 1..i).0).ok();
20            }
21            _ => unreachable!("unknown query"),
22        }
23    }
24}
crates/aizu_online_judge/src/dsl/dsl_2_g.rs (line 15)
6pub fn dsl_2_g(reader: impl Read, mut writer: impl Write) {
7    let s = read_all_unchecked(reader);
8    let mut scanner = Scanner::new(&s);
9    scan!(scanner, n, q);
10    let mut seg = LazySegmentTree::<RangeSumRangeAdd<_>>::from_vec(vec![(0, 1); n]);
11    for _ in 0..q {
12        match scanner.scan::<usize>() {
13            0 => {
14                scan!(scanner, s, t, x: u64);
15                seg.update(s - 1..t, x);
16            }
17            1 => {
18                scan!(scanner, s, t);
19                writeln!(writer, "{}", seg.fold(s - 1..t).0).ok();
20            }
21            _ => unreachable!("unknown query"),
22        }
23    }
24}
crates/aizu_online_judge/src/dsl/dsl_2_i.rs (line 15)
6pub fn dsl_2_i(reader: impl Read, mut writer: impl Write) {
7    let s = read_all_unchecked(reader);
8    let mut scanner = Scanner::new(&s);
9    scan!(scanner, n, q);
10    let mut seg = LazySegmentTree::<RangeSumRangeUpdate<_>>::from_vec(vec![(0, 1); n]);
11    for _ in 0..q {
12        match scanner.scan::<usize>() {
13            0 => {
14                scan!(scanner, s, t, x: i64);
15                seg.update(s..t + 1, Some(x));
16            }
17            1 => {
18                scan!(scanner, s, t);
19                writeln!(writer, "{}", seg.fold(s..t + 1).0).ok();
20            }
21            _ => unreachable!("unknown query"),
22        }
23    }
24}
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 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    }
More examples
Hide additional examples
crates/aizu_online_judge/src/dsl/dsl_2_d.rs (line 19)
6pub fn dsl_2_d(reader: impl Read, mut writer: impl Write) {
7    let s = read_all_unchecked(reader);
8    let mut scanner = Scanner::new(&s);
9    scan!(scanner, n, q);
10    let mut seg = LazySegmentTree::<RangeMinRangeUpdate<_>>::new(n);
11    for _ in 0..q {
12        match scanner.scan::<usize>() {
13            0 => {
14                scan!(scanner, s, t, x: i32);
15                seg.update(s..t + 1, Some(x));
16            }
17            1 => {
18                scan!(scanner, i);
19                writeln!(writer, "{}", seg.fold(i..i + 1)).ok();
20            }
21            _ => unreachable!("unknown query"),
22        }
23    }
24}
crates/aizu_online_judge/src/dsl/dsl_2_f.rs (line 19)
6pub fn dsl_2_f(reader: impl Read, mut writer: impl Write) {
7    let s = read_all_unchecked(reader);
8    let mut scanner = Scanner::new(&s);
9    scan!(scanner, n, q);
10    let mut seg = LazySegmentTree::<RangeMinRangeUpdate<_>>::new(n);
11    for _ in 0..q {
12        match scanner.scan::<usize>() {
13            0 => {
14                scan!(scanner, s, t, x: i32);
15                seg.update(s..t + 1, Some(x));
16            }
17            1 => {
18                scan!(scanner, s, t);
19                writeln!(writer, "{}", seg.fold(s..t + 1)).ok();
20            }
21            _ => unreachable!("unknown query"),
22        }
23    }
24}
crates/aizu_online_judge/src/dsl/dsl_2_h.rs (line 19)
6pub fn dsl_2_h(reader: impl Read, mut writer: impl Write) {
7    let s = read_all_unchecked(reader);
8    let mut scanner = Scanner::new(&s);
9    scan!(scanner, n, q);
10    let mut seg = LazySegmentTree::<RangeMinRangeAdd<_>>::from_vec(vec![0; n]);
11    for _ in 0..q {
12        match scanner.scan::<usize>() {
13            0 => {
14                scan!(scanner, s, t, x: i64);
15                seg.update(s..t + 1, x);
16            }
17            1 => {
18                scan!(scanner, s, t);
19                writeln!(writer, "{}", seg.fold(s..t + 1)).ok();
20            }
21            _ => unreachable!("unknown query"),
22        }
23    }
24}
crates/aizu_online_judge/src/dsl/dsl_2_e.rs (line 19)
6pub fn dsl_2_e(reader: impl Read, mut writer: impl Write) {
7    let s = read_all_unchecked(reader);
8    let mut scanner = Scanner::new(&s);
9    scan!(scanner, n, q);
10    let mut seg = LazySegmentTree::<RangeSumRangeAdd<_>>::from_vec(vec![(0, 1); n]);
11    for _ in 0..q {
12        match scanner.scan::<usize>() {
13            0 => {
14                scan!(scanner, s, t, x: u64);
15                seg.update(s - 1..t, x);
16            }
17            1 => {
18                scan!(scanner, i);
19                writeln!(writer, "{}", seg.fold(i - 1..i).0).ok();
20            }
21            _ => unreachable!("unknown query"),
22        }
23    }
24}
crates/aizu_online_judge/src/dsl/dsl_2_g.rs (line 19)
6pub fn dsl_2_g(reader: impl Read, mut writer: impl Write) {
7    let s = read_all_unchecked(reader);
8    let mut scanner = Scanner::new(&s);
9    scan!(scanner, n, q);
10    let mut seg = LazySegmentTree::<RangeSumRangeAdd<_>>::from_vec(vec![(0, 1); n]);
11    for _ in 0..q {
12        match scanner.scan::<usize>() {
13            0 => {
14                scan!(scanner, s, t, x: u64);
15                seg.update(s - 1..t, x);
16            }
17            1 => {
18                scan!(scanner, s, t);
19                writeln!(writer, "{}", seg.fold(s - 1..t).0).ok();
20            }
21            _ => unreachable!("unknown query"),
22        }
23    }
24}
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(&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.rs (line 222)
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    }
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.rs (line 266)
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    }
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 LazySegmentTree<M>
where M: LazyMapMonoid,

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

§

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

§

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

§

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

§

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

§

impl<M> UnwindSafe for LazySegmentTree<M>
where <M as LazyMapMonoid>::Agg: UnwindSafe, <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<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.