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

• View this file on GitHub
• Last update: 2025-06-07 00:31:50+09:00
• Link: https://atcoder.jp/contests/abc223/editorial/2774

Depends on

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

Required by

• Segment Tree (data-structure/segment-tree/src/lib.rs)
• Rolling Hash + Segment Tree (string/rolling-hash-segment-tree/src/lib.rs)
• tree/euler-tour/src/lib.rs

Verified with

• verification/aizu-online-judge/dsl_2_a/src/main.rs
• verification/aizu-online-judge/dsl_2_b/src/main.rs
• verification/library-checker/vertex_set_path_composite/src/main.rs

Code

use crate::SegmentTree;

pub struct RangeMinimumQuery;

impl RangeMinimumQuery {
    pub fn new(n: usize) -> SegmentTree<i64> {
        SegmentTree::new(n, |a, b| std::cmp::min(a, b), i64::MAX)
    }
}

pub struct RangeMaximumQuery;

impl RangeMaximumQuery {
    pub fn new(n: usize) -> SegmentTree<i64> {
        SegmentTree::new(n, |a, b| std::cmp::max(a, b), i64::MIN)
    }
}

pub struct RangeSumQuery;

impl RangeSumQuery {
    pub fn new(n: usize) -> SegmentTree<i64> {
        SegmentTree::new(n, |a, b| a + b, 0)
    }
}

pub struct ParenthesisCheckQuery;

impl ParenthesisCheckQuery {
    pub fn new(n: usize) -> SegmentTree<(i64, i64)> {
        SegmentTree::new(n, |a, b| (a.0 + std::cmp::max(b.0 - a.1, 0), std::cmp::max(a.1 - b.0, 0) + b.1), (0, 0))
    }

    pub fn new_build(n: usize, s: &Vec<char>) -> SegmentTree<(i64, i64)> {
        let mut st = SegmentTree::new(n, |a, b| (a.0 + std::cmp::max(b.0 - a.1, 0), std::cmp::max(a.1 - b.0, 0) + b.1), (0, 0));
        for i in 0..s.len() {
            st.set(
                i,
                match s[i] {
                    '(' => (0, 1),
                    ')' => (1, 0),
                    _ => unreachable!(),
                },
            );
        }
        st
    }
}

/*
// reference: https://atcoder.jp/contests/abc223/editorial/2774
pub struct ParenthesisCheckQuery;

impl ParenthesisCheckQuery {
    pub fn new(n: usize) -> SegmentTree<(i64, i64)> {
        SegmentTree::new(n, |a, b| (std::cmp::min(a.0, a.1 + b.0), a.1 + b.1), (0, 0))
    }

    pub fn new_build(n: usize, s: &Vec<char>) -> SegmentTree<(i64, i64)> {
        let mut st = SegmentTree::new(n, |a, b| (a.0 + std::cmp::max(b.0 - a.1, 0), std::cmp::max(a.1 - b.0, 0) + b.1), (0, 0));
        for i in 0..s.len() {
            st.set(
                i,
                match s[i] {
                    '(' => (0, 0),
                    ')' => (-1, -1),
                    _ => unreachable!(),
                },
            );
        }
        st
    }
}
*/

pub struct RangeCompositeQuery;

impl RangeCompositeQuery {
    pub fn new(n: usize) -> SegmentTree<(i64, i64)> {
        SegmentTree::new(n, |a, b| (a.0 * b.0, a.1 * b.0 + b.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