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

• 問題: No.789 範囲の合計
• ユーザー: CoCo_Japan_pan
• 提出日時: 2025-04-29 13:09:47
• 言語: Rust (1.83.0 + proconio)
• 結果: AC
• 実行時間: 56 ms / 1,000 ms
• コード長: 6,206 bytes
• コンパイル時間: 14,670 ms
• コンパイル使用メモリ: 376,564 KB
• 実行使用メモリ: 8,960 KB
• 最終ジャッジ日時: 2025-04-29 13:10:06
• 合計ジャッジ時間: 17,552 ms
• ジャッジサーバーID （参考情報）: judge2 / judge3

ファイルパターン	結果
other	AC * 15

ソースコード

// verification-helper: PROBLEM https://yukicoder.me/problems/no/789

pub use __cargo_equip::prelude::*;

use algebra::Monoid;
use dynamic_segtree::DynamicSegTree;
use proconio::{fastout, input};

struct SumMonoid;
impl Monoid for SumMonoid {
    type Target = usize;
    fn id_element() -> Self::Target {
        0
    }
    fn binary_operation(a: &Self::Target, b: &Self::Target) -> Self::Target {
        a + b
    }
}

#[fastout]
fn main() {
    input! {
        n: usize,
        t_x_y: [(u8, usize, usize); n],
    }
    let mut seg = DynamicSegTree::<SumMonoid>::new(1000_000_010);
    let mut ans = 0;
    for (t, x, y) in t_x_y {
        if t == 0 {
            let pre_val = seg.get(x);
            seg.set(x, pre_val + y);
        } else {
            ans += seg.prod(x..=y);
        }
    }
    println!("{}", ans);
}

// The following code was expanded by `cargo-equip`.

///  # Bundled libraries
/// 
///  - `algebra 0.1.0 (path+██████████████████████████████████████████████████████)`                                published in https://github.com/CoCo-Japan-pan/procon_lib_rs.git licensed under `CC0-1.0` as `crate::__cargo_equip::crates::algebra`
///  - `dynamic_segtree 0.1.0 (path+█████████████████████████████████████████████████████████████████████████████)` published in https://github.com/CoCo-Japan-pan/procon_lib_rs.git licensed under `CC0-1.0` as `crate::__cargo_equip::crates::dynamic_segtree`
#[cfg_attr(any(), rustfmt::skip)]
#[allow(unused)]
mod __cargo_equip {
    pub(crate) mod crates {
        pub mod algebra {use std::fmt::Debug;pub trait Commutative{}pub trait Action:Debug+Clone{type Target:Clone;fn id_action()->Self;fn composition(&mut self,rhs:&Self);fn apply(&self,target:&mut Self::Target);}pub trait Monoid{type Target:Debug+Clone+Eq;fn id_element()->Self::Target;fn binary_operation(a:&Self::Target,b:&Self::Target)->Self::Target;}pub trait ActionMonoid{type M:Monoid;type A:Action<Target=<Self::M as Monoid>::Target>;}pub trait IdempotentMonoid:Monoid{}pub trait Group:Monoid{fn inverse(a:&Self::Target)->Self::Target;}pub trait Semiring:Debug+Clone+Eq{type Target:Debug+Clone+Eq;fn zero()->Self::Target;fn one()->Self::Target;fn add_assign(a:&mut Self::Target,b:&Self::Target);fn mul(a:&Self::Target,b:&Self::Target)->Self::Target;}}
        pub mod dynamic_segtree {use crate::__cargo_equip::preludes::dynamic_segtree::*;use algebra::Monoid;use std::ops::RangeBounds;struct Node<M:Monoid>{left_child:Option<Box<Node<M>>>,right_child:Option<Box<Node<M>>>,index:usize,value:M::Target,product:M::Target,}impl<M:Monoid>Node<M>{fn new(index:usize,value:M::Target)->Self{Self{left_child:None,right_child:None,index,product:value.clone(),value,}}fn update(&mut self){let id_element=M::id_element();let left_value=self.left_child.as_ref().map_or(&id_element,|node|&node.product);let right_value=self.right_child.as_ref().map_or(&id_element,|node|&node.product);self.product=M::binary_operation(&M::binary_operation(left_value,&self.value),right_value);}}type NodePtr<M> =Option<Box<Node<M>>>;fn set_node<M:Monoid>(node:&mut NodePtr<M>,mut index:usize,mut value:M::Target,left:usize,right:usize,){if node.is_none(){*node=Some(Box::new(Node::new(index,value)));return;}let node=node.as_mut().unwrap();if node.index==index{node.value=value;node.update();return;}let half=(left+right)>>1;if index<half{if index>node.index{std::mem::swap(&mut node.value,&mut value);std::mem::swap(&mut node.index,&mut index);}set_node(&mut node.left_child,index,value,left,half);}else{if index<node.index{std::mem::swap(&mut node.value,&mut value);std::mem::swap(&mut node.index,&mut index);}set_node(&mut node.right_child,index,value,half,right);}node.update();}fn get_node<M:Monoid>(node:&NodePtr<M>,index:usize,left:usize,right:usize)->M::Target{if node.is_none(){return M::id_element();}let node=node.as_ref().unwrap();if node.index==index{return node.value.clone();}let half=(left+right)>>1;if index<half{get_node(&node.left_child,index,left,half)}else{get_node(&node.right_child,index,half,right)}}fn prod_node<M:Monoid>(node:&NodePtr<M>,prod_left:usize,prod_right:usize,left:usize,right:usize,)->M::Target{if node.is_none()||right<=prod_left||prod_right<=left{return M::id_element();}let node=node.as_ref().unwrap();if prod_left<=left&&right<=prod_right{return node.product.clone();}let half=(left+right)>>1;let mut res=M::id_element();res=M::binary_operation(&res,&prod_node(&node.left_child,prod_left,prod_right,left,half),);if prod_left<=node.index&&node.index<prod_right{res=M::binary_operation(&res,&node.value);}res=M::binary_operation(&res,&prod_node(&node.right_child,prod_left,prod_right,half,right),);res}pub struct DynamicSegTree<M:Monoid>{range_size:usize,root_node:NodePtr<M>,}impl<M:Monoid>DynamicSegTree<M>{pub fn new(range_size:usize)->Self{Self{range_size,root_node:None,}}pub fn set(&mut self,index:usize,value:M::Target){assert!(index<self.range_size);set_node(&mut self.root_node,index,value,0,self.range_size);}pub fn get(&self,index:usize)->M::Target{assert!(index<self.range_size);get_node(&self.root_node,index,0,self.range_size)}pub fn all_prod(&self)->M::Target{self.root_node.as_ref().map_or(M::id_element(),|node|node.product.clone())}pub fn prod<R:RangeBounds<usize>>(&self,range:R)->M::Target{use std::ops::Bound::*;let start=match range.start_bound(){Included(&l)=>l,Excluded(&l)=>l+1,Unbounded=>0,};let end=match range.end_bound(){Included(&r)=>r+1,Excluded(&r)=>r,Unbounded=>self.range_size,};assert!(start<=end&&end<=self.range_size);if start==0&&end==self.range_size{return self.all_prod();}prod_node(&self.root_node,start,end,0,self.range_size)}}}
    }

    pub(crate) mod macros {
        pub mod algebra {}
        pub mod dynamic_segtree {}
    }

    pub(crate) mod prelude {pub use crate::__cargo_equip::crates::*;}

    mod preludes {
        pub mod algebra {}
        pub mod dynamic_segtree {pub(in crate::__cargo_equip)use crate::__cargo_equip::crates::algebra;}
    }
}