// 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::::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>;}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{left_child:Option>>,right_child:Option>>,index:usize,value:M::Target,product:M::Target,}implNode{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 =Option>>;fn set_node(node:&mut NodePtr,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 indexnode.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:&NodePtr,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(node:&NodePtr,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{range_size:usize,root_node:NodePtr,}implDynamicSegTree{pub fn new(range_size:usize)->Self{Self{range_size,root_node:None,}}pub fn set(&mut self,index:usize,value:M::Target){assert!(indexM::Target{assert!(indexM::Target{self.root_node.as_ref().map_or(M::id_element(),|node|node.product.clone())}pub fn prod>(&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;} } }