#1035523 (Rust) No.789 範囲の合計

提出ソース
結果

問題	No.789 範囲の合計
ユーザー	ArcAki
提出日時	2025-01-16 07:14:22
言語	Rust (1.83.0 + proconio)
結果	AC
実行時間	101 ms / 1,000 ms
コード長	12,943 bytes
コンパイル時間	11,906 ms
コンパイル使用メモリ	401,864 KB
実行使用メモリ	45,056 KB
最終ジャッジ日時	2025-01-16 07:14:46
合計ジャッジ時間	14,939 ms
ジャッジサーバーID （参考情報）	judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン	結果
other	AC * 15
権限があれば一括ダウンロードができます
ソースコード

raw source code
#[allow(unused_imports)]
use std::{
    collections::{*},
    cmp::{Reverse, Ordering, Ord, PartialOrd, PartialEq},
    mem::{swap},
    time::Instant,
    fs::File,
    io::{self, stdin, read_to_string},
    hash::Hash,
};
#[allow(unused_imports)]
use crate::input::{Usize1, Chars};

pub fn bit_length(x: usize)->usize{
    64-x.saturating_sub(1).leading_zeros()as usize
}

pub trait SegTreeMonoid{
    type S: Copy;
    fn identity()->Self::S;
    fn op(a: &Self::S, b: &Self::S)->Self::S;
}

pub struct DynamicSegmenttree<M> where M: SegTreeMonoid{
    n: usize,
    data: Vec<(M::S, Option<usize>, Option<usize>)>,
}

impl<M> DynamicSegmenttree<M> where M: SegTreeMonoid{
    pub fn new(n: usize)->Self{
        let n = n.next_power_of_two();
        DynamicSegmenttree{
            n, data: vec![(M::identity(), None, None)]
        }
    }

    pub fn set(&mut self, p: usize, x: M::S){
        self.update_dfs(0, 0, self.n, p, x, false);
    }

    pub fn push(&mut self, p: usize, x: M::S){
        self.update_dfs(0, 0, self.n, p, x, true);
    }

    fn update_dfs(&mut self, p: usize, l: usize, r: usize, idx: usize, x: M::S, f: bool)->M::S{
        if l+1==r{
            let (pre, left, right) = self.data[p];
            if f{
                self.data[p] = (M::op(&pre, &x), left, right);
            } else {
                self.data[p] = (x, left, right);
            }
            return self.data[p].0;
        }
        let (_, mut left, mut right) = self.data[p];
        let m = (l+r)/2;
        let res = if idx < m{
            let res_l = if let Some(ln) = left{
                self.update_dfs(ln, l, m, idx, x, f)
            } else {
                let nex = self.data.len();
                left = Some(nex);
                self.data.push((M::identity(), None, None));
                self.update_dfs(nex, l, m, idx, x, f)
            };
            let res_r = if let Some(rn) = right{
                self.data[rn].0
            } else {
                M::identity()
            };
            M::op(&res_l, &res_r)
        } else {
            let res_l = if let Some(ln) = left{
                self.data[ln].0
            } else {
                M::identity()
            };
            let res_r = if let Some(rn) = right{
                self.update_dfs(rn, m, r, idx, x, f)
            } else {
                let nex = self.data.len();
                right = Some(nex);
                self.data.push((M::identity(), None, None));
                self.update_dfs(nex, m, r, idx, x, f)
            };
            M::op(&res_l, &res_r)
        };
        self.data[p] = (res, left, right);
        res
    }

    pub fn prod(&self, l: usize, r: usize)->M::S{
        self.prod_dfs(0, 0, self.n, l, r)
    }

    fn prod_dfs(&self, p: usize, l: usize, r: usize, x: usize, y: usize)->M::S{
        if r <= x||y <= l{return M::identity();}
        let (z, left, right) =self.data[p];
        if x <= l && r <= y{
            return z;
        }
        let m = (l+r)/2;
        let res_l = if let Some(ln) = left{
            self.prod_dfs(ln, l, m, x, y)
        } else {
            M::identity()
        };
        let res_r = if let Some(rn) = right{
            self.prod_dfs(rn, m, r, x, y)
        } else {
            M::identity()
        };
        M::op(&res_l, &res_r)
    }

    pub fn max_right<F>(&self, l: usize, f: F)->usize where F: Fn(&M::S)->bool{
        assert!(f(&M::identity()));
        if l==self.n{return self.n}
        let mut ac = M::identity();
        self.max_right_dfs(0, 0, self.n, l, &mut ac, &f)
    }

    fn max_right_dfs<F>(&self, p: usize, l: usize, r: usize, x: usize, ac: &mut M::S, f: &F)->usize where F: Fn(&M::S)->bool{
        if r <= x{
            return x
        }
        if l >= x{
            let res = M::op(ac, &self.data[p].0);
            if f(&res){
                *ac = res;
                return r;
            } else if r-l==1{
                return l;
            }
        }
        let m = (l+r)/2;
        let (_, left, right) = self.data[p];
        let ret = if let Some(ln) = left{
            self.max_right_dfs(ln, l, m, x, ac, f)
        } else {
            x
        };
        if ret < m{
            return ret;
        } else if let Some(rn) = right{
            self.max_right_dfs(rn, m, r, x, ac, f)
        } else {
            r
        }
    }

    pub fn min_left<F>(&self, r: usize, f: F)->usize where F: Fn(&M::S)->bool{
        assert!(f(&M::identity()));
        if r==0{return 0;}
        let mut ac = M::identity();
        self.min_left_dfs(0, 0, self.n, r, &mut ac, &f)
    }

    fn min_left_dfs<F>(&self, p: usize, l: usize, r: usize, x: usize, ac: &mut M::S, f: &F)->usize where F: Fn(&M::S)->bool{
        if x <= l{
            return l;
        } else if r <= x{
            let res = M::op(&self.data[p].0, ac);
            if f(&res){
                *ac = res;
                return l;
            } else if l+1==r{
                return r;
            }
        }
        let m = (l+r)/2;
        let (_, left, right) = self.data[p];
        let ret = if let Some(rn) = right{
            self.min_left_dfs(rn, m, r, x, ac, f)
        } else {
            m
        };
        if ret > m{
            ret
        } else if let Some(ln) = left{
            self.min_left_dfs(ln, l, m, x, ac, f)
        } else {
            l
        }
    }

    pub fn all_prod(&self)->M::S{
        self.data[0].0
    }
}

struct M;
impl SegTreeMonoid for M{
    type S = usize;

    fn identity() -> Self::S {
        0
    }

    fn op(&a: &Self::S, &b: &Self::S) -> Self::S {
        a+b
    }
}

// qryxipさんのコードをお借りしています！！ありがとうございます！！

fn main() {
    let __fastout_stdout = ::std::io::stdout();
    let __fastout_stdout = &mut ::std::io::BufWriter::new(__fastout_stdout.lock());
    #[allow(unused_macros)]
    macro_rules ! print
    {($ ($ tt : tt) *) =>{{
        use std :: io :: Write as _ ; :: std :: write !
        (__fastout_stdout, $ ($ tt) *) . unwrap () ;}};}
    #[allow(unused_macros)]
    macro_rules ! println
    {($ ($ tt : tt) *) =>{{
        use std :: io :: Write as _ ; :: std :: writeln !
        (__fastout_stdout, $ ($ tt) *) . unwrap ();}} ;}

    let __fastout_res = {
        // 本体コードはここから

        input!{
        n: usize,
        query: [(usize, usize, usize); n],
    }
        let mut segtree = DynamicSegmenttree::<M>::new(1000000001);
        let mut ans = 0;
        for &(p, x, y) in &query{
            if p==0{
                segtree.push(x, y);
            } else {
                let res = segtree.prod(x, y+1);
                ans += res;
            }
        }
        std::println!("{}", ans);

        // 本体コードここまで
    };

    <::std::io::BufWriter<_> as ::std::io::Write>::flush(__fastout_stdout).unwrap();
    __fastout_res
}

#[allow(unused)]
pub mod input {
    pub use crate::{input, input_inner, read, readable};
    use std::{
        cell::RefCell,
        fmt::Debug,
        io::{self, BufRead, Read},
        rc::Rc,
        str::{FromStr, SplitWhitespace},
    };

    #[macro_export]
    macro_rules! input {
        (from $scanner:ident; $($tt:tt)*) => {
            $crate::input::input_inner!(@scanner($scanner), @tts($($tt)*))
        };
        ($($tt:tt)*) => {
            let __scanner = $crate::input::DEFAULT_SCANNER.with(|__scanner| __scanner.clone());
            let mut __scanner_ref = __scanner.borrow_mut();
            if let $crate::input::Scanner::Uninited = *__scanner_ref {
                *__scanner_ref = $crate::input::Scanner::stdin_auto().unwrap();
            }
            $crate::input::input_inner!(@scanner(__scanner_ref), @tts($($tt)*));
            ::std::mem::drop(__scanner_ref);
            ::std::mem::drop(__scanner);
        };
    }

    #[macro_export]
    macro_rules! input_inner {
        (@scanner($scanner:ident), @tts()) => {};
        (@scanner($scanner:ident), @tts(mut $single_tt_pat:tt : $readable:tt)) => {
            let mut $single_tt_pat = $crate::input::read!(from $scanner { $readable });
        };
        (@scanner($scanner:ident), @tts($single_tt_pat:tt : $readable:tt)) => {
            let $single_tt_pat = $crate::input::read!(from $scanner { $readable });
        };
        (@scanner($scanner:ident), @tts(mut $single_tt_pat:tt : $readable:tt, $($rest:tt)*)) => {
            $crate::input::input_inner!(@scanner($scanner), @tts(mut $single_tt_pat: $readable));
            $crate::input::input_inner!(@scanner($scanner), @tts($($rest)*));
        };
        (@scanner($scanner:ident), @tts($single_tt_pat:tt : $readable:tt, $($rest:tt)*)) => {
            $crate::input::input_inner!(@scanner($scanner), @tts($single_tt_pat: $readable));
            $crate::input::input_inner!(@scanner($scanner), @tts($($rest)*));
        };
    }

    #[macro_export]
    macro_rules! read {
        (from $scanner:ident { [$tt:tt] }) => {
            $crate::input::read!(from $scanner { [$tt; $crate::read!(from $scanner { usize })] })
        };
        (from $scanner:ident  { [$tt:tt; $n:expr] }) => {
            (0..$n).map(|_| $crate::input::read!(from $scanner { $tt })).collect::<Vec<_>>()
        };
        (from $scanner:ident { ($($tt:tt),+) }) => {
            ($($crate::read!(from $scanner { $tt })),*)
        };
        (from $scanner:ident { $ty:ty }) => {
            <$ty as $crate::input::Readable>::read_from_scanner(&mut $scanner)
        };
    }

    #[macro_export]
    macro_rules! readable {
        ($name:ident; |$scanner:ident| { $($body:tt)* }) => {
            $crate::input::readable!($name; |$scanner| -> () { $($body)* });
        };
        ($name:ident; |$scanner:ident| $expr:expr) => {
            $crate::input::readable!($name; |$scanner| -> () { $expr });
        };
        ($name:ident; |$scanner:ident| -> $output:ty { $($body:tt)* }) => {
            enum $name {}

            impl $crate::input::Readable for $name {
                type Output = $output;

                fn read_from_scanner(mut $scanner: &mut $crate::input::Scanner) -> $output {
                    $($body)*
                }
            }
        };
    }

    pub enum Scanner {
        Uninited,
        Once {
            words: SplitWhitespace<'static>,
        },
        Lines {
            rdr: Box<dyn BufRead>,
            words: SplitWhitespace<'static>,
        },
    }

    impl Scanner {
        pub fn stdin_auto() -> io::Result<Self> {
            if cfg!(debug_assertions) {
                Ok(Self::lines(Box::leak(Box::new(io::stdin())).lock()))
            } else {
                Self::once(io::stdin())
            }
        }

        pub fn once<R: Read>(mut rdr: R) -> io::Result<Self> {
            let mut buf = String::with_capacity(1024);
            rdr.read_to_string(&mut buf)?;
            let words = Box::leak(buf.into_boxed_str()).split_whitespace();
            Ok(Self::Once { words })
        }

        pub fn lines<R: BufRead + 'static>(rdr: R) -> Self {
            Self::Lines {
                rdr: Box::new(rdr),
                words: "".split_whitespace(),
            }
        }

        pub fn parse_next_unwrap<T: FromStr>(&mut self) -> T
        where
            T::Err: Debug,
        {
            match self {
                Self::Uninited => None,
                Self::Once { words } => words.next(),
                Self::Lines { rdr, words } => words.next().or_else(|| {
                    let mut line = "".to_owned();
                    rdr.read_line(&mut line).unwrap();
                    *words = Box::leak(line.into_boxed_str()).split_whitespace();
                    words.next()
                }),
            }
                .expect("reached EOF")
                .parse()
                .unwrap()
        }
    }

    thread_local! {
        pub static DEFAULT_SCANNER: Rc<RefCell<Scanner>> = Rc::new(RefCell::new(Scanner::Uninited));
    }

    pub trait Readable {
        type Output;

        fn read_from_scanner(scanner: &mut Scanner) -> Self::Output;
    }

    impl<T: FromStr> Readable for T
    where
        T::Err: Debug,
    {
        type Output = Self;

        fn read_from_scanner(scanner: &mut Scanner) -> Self {
            scanner.parse_next_unwrap()
        }
    }

    pub enum Usize1 {}
    pub enum Chars {}
    impl Readable for Usize1 {
        type Output = usize;

        fn read_from_scanner(scanner: &mut Scanner) -> Self::Output {
            let val: usize = scanner.parse_next_unwrap();
            if val == 0 {
                panic!("Usize1-0-parse-error");
            }
            val - 1
        }
    }

    impl Readable for Chars {
        type Output = Vec<char>;

        fn read_from_scanner(scanner: &mut Scanner) -> Self::Output {
            let val: String = scanner.parse_next_unwrap();
            val.chars().collect()
        }
    }
}
yukicoder

結果

ソースコード
