data-structure/lazy-segment-tree/src/wrapper.rs

• View this file on GitHub
• Last update: 2025-05-29 20:17:30+09:00
• Link: https://betrue12.hateblo.jp/entry/2020/09/23/005940

Depends on

• Lazy Segment Tree (data-structure/lazy-segment-tree/src/lib.rs)

Required by

• Lazy Segment Tree (data-structure/lazy-segment-tree/src/lib.rs)

Verified with

• verification/aizu-online-judge/dsl_2_f/src/main.rs
• verification/aizu-online-judge/dsl_2_g/src/main.rs
• verification/aizu-online-judge/dsl_2_h/src/main.rs
• verification/aizu-online-judge/dsl_2_i/src/main.rs
• verification/aizu-online-judge/grl_5_e/src/main.rs
• verification/library-checker/range_affine_range_sum/src/main.rs

Code

//! https://betrue12.hateblo.jp/entry/2020/09/23/005940

use crate::LazySegmentTree;

pub struct RangeAddRangeMinimumQuery;

impl RangeAddRangeMinimumQuery {
    pub fn new(n: usize) -> LazySegmentTree<i64, i64> {
        LazySegmentTree::new(n, |a, b| std::cmp::min(a, b), i64::MAX, |f, x| f + x, |f, g| f + g, 0)
    }
}

pub struct RangeAddRangeMaximumQuery;

impl RangeAddRangeMaximumQuery {
    pub fn new(n: usize) -> LazySegmentTree<i64, i64> {
        LazySegmentTree::new(n, |a, b| std::cmp::max(a, b), i64::MIN, |f, x| f + x, |f, g| f + g, 0)
    }
}

pub struct RangeAddRangeSumQuery;

impl RangeAddRangeSumQuery {
    pub fn new(n: usize) -> LazySegmentTree<(i64, i64), i64> {
        LazySegmentTree::new(n, |a, b| (a.0 + b.0, a.1 + b.1), (0, 0), |f, x| (x.0 + f * x.1, x.1), |f, x| f + x, 0)
    }
}

pub struct RangeUpdateRangeMinimumQuery;

impl RangeUpdateRangeMinimumQuery {
    pub fn new(n: usize) -> LazySegmentTree<i64, i64> {
        LazySegmentTree::new(
            n,
            |a, b| std::cmp::min(a, b),
            i64::MAX,
            |f, x| if f == i64::MAX { x } else { f },
            |f, g| if f == i64::MAX { g } else { f },
            i64::MAX,
        )
    }
}

pub struct RangeUpdateRangeMaximumQuery;

impl RangeUpdateRangeMaximumQuery {
    pub fn new(n: usize) -> LazySegmentTree<i64, i64> {
        LazySegmentTree::new(
            n,
            |a, b| std::cmp::max(a, b),
            i64::MIN,
            |f, x| if f == i64::MAX { x } else { f },
            |f, g| if f == i64::MAX { g } else { f },
            i64::MAX,
        )
    }
}

pub struct RangeUpdateRangeSumQuery;

impl RangeUpdateRangeSumQuery {
    pub fn new(n: usize) -> LazySegmentTree<(i64, i64), i64> {
        LazySegmentTree::new(
            n,
            |a, b| (a.0 + b.0, a.1 + b.1),
            (0, 0),
            |f, x| if f != i64::MAX { (f * x.1, x.1) } else { x },
            |f, g| if f == i64::MAX { g } else { f },
            i64::MAX,
        )
    }
}

pub struct RangeAffineRangeSumQuery;

impl RangeAffineRangeSumQuery {
    pub fn new(n: usize) -> LazySegmentTree<(i64, i64), (i64, i64)> {
        LazySegmentTree::new(
            n,
            |a, b| (a.0 + b.0, a.1 + b.1),
            (0, 0),
            |a, b| (a.0 * b.0 + a.1 * b.1, b.1),
            |a, b| (a.0 * b.0, a.0 * b.1 + a.1),
            (1, 0),
        )
    }
}

Traceback (most recent call last):
  File "/opt/hostedtoolcache/Python/3.11.12/x64/lib/python3.11/site-packages/onlinejudge_verify/documentation/build.py", line 71, in _render_source_code_stat
    bundled_code = language.bundle(stat.path, basedir=basedir, options={'include_paths': [basedir]}).decode()
                   ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/opt/hostedtoolcache/Python/3.11.12/x64/lib/python3.11/site-packages/onlinejudge_verify/languages/rust.py", line 288, in bundle
    raise NotImplementedError
NotImplementedError

Back to top page