// verification-helper: PROBLEM https://yukicoder.me/problems/no/789 pub use __cargo_equip::prelude::*; use dynamic_segment_tree::DynamicSegmentTree; use monoid::add::Additive; use proconio::{fastout, input}; type DynamicSegTree = DynamicSegmentTree, 0, 1_000_000_002>; #[fastout] fn main() { input! { q: usize }; let mut seg = DynamicSegTree::new(); let mut ans = 0_i64; for _ in 0..q { input! { t: usize }; match t { 0 => { input! { x: i64, y: i64 }; seg.set(x, seg.get(x) + y); } 1 => { input! { l: i64, r: i64 } ans += seg.prod(l..=r); } _ => unreachable!(), } } println!("{}", ans); } // The following code was expanded by `cargo-equip`. /// # Bundled libraries /// /// - `path+file:///home/siro53/repos/comprolib_rs/crates/ds/segment_tree/dynamic_segment_tree#0.1.0` published in **missing** licensed under **missing** as `crate::__cargo_equip::crates::dynamic_segment_tree` /// - `path+file:///home/siro53/repos/comprolib_rs/crates/traits/monoid#0.1.0` published in **missing** licensed under **missing** as `crate::__cargo_equip::crates::monoid` /// - `path+file:///home/siro53/repos/comprolib_rs/crates/traits/numeric#0.1.0` published in **missing** licensed under **missing** as `crate::__cargo_equip::crates::__numeric_0_1_0` #[cfg_attr(any(), rustfmt::skip)] #[allow(unused)] mod __cargo_equip { pub(crate) mod crates { pub mod dynamic_segment_tree {use crate::__cargo_equip::preludes::dynamic_segment_tree::*;use std::ops::{Bound,RangeBounds};use monoid::Monoid;pub struct Nodewhere M:Monoid,{value:M::ValueType,children_node:[Option>>;2],}implNodewhere M:Monoid,{pub fn new(value:M::ValueType)->Self{Self{value,children_node:[None,None],}}}pub struct DynamicSegmentTreewhere M:Monoid,{root:Option>>,}implDefault for DynamicSegmentTreewhere M:Monoid,{fn default()->Self{Self{root:None}}}implDynamicSegmentTreewhere M:Monoid,{pub fn new()->Self{Self::default()}pub fn set(&mut self,pos:i64,value:M::ValueType){assert!(MIN_INDEX<=pos);assert!(posM::ValueType{assert!(MIN_INDEX<=pos);assert!(pos>(&self,range:R)->M::ValueType{let l=match range.start_bound(){Bound::Included(l)=>*l,Bound::Excluded(l)=>l+1,Bound::Unbounded=>MIN_INDEX,};let r=match range.end_bound(){Bound::Included(r)=>r+1,Bound::Excluded(r)=>*r,Bound::Unbounded=>MAX_INDEX,};assert!(MIN_INDEX<=l);assert!(l<=r);assert!(r<=MAX_INDEX);Self::_prod(&self.root,MIN_INDEX,MAX_INDEX,l,r)}fn _set(node:&mut Option>>,l:i64,r:i64,pos:i64,value:M::ValueType){if node.is_none(){*node=Some(Box::new(Node::::new(M::unit())));}let ptr=node.as_mut().unwrap();if r-l==1{ptr.value=value;return;}let mid=(l+r)/2;if pos>>,l:i64,r:i64,pos:i64)->M::ValueType{if node.is_none(){return M::unit();}let ptr=node.as_ref().unwrap();if r-l==1{return ptr.value.clone();}let mid=(l+r)/2;if pos>>,l:i64,r:i64,ql:i64,qr:i64)->M::ValueType{if node.is_none()||(qr<=l||r<=ql){return M::unit();}let ptr=node.as_ref().unwrap();if ql<=l&&r<=qr{return ptr.value.clone();}let mid=(l+r)/2;M::op(&Self::_prod(&ptr.children_node[0],l,mid,ql,qr),&Self::_prod(&ptr.children_node[1],mid,r,ql,qr),)}}} pub mod monoid {use crate::__cargo_equip::preludes::monoid::*;pub trait Monoid{type ValueType:Clone;fn op(left_value:&Self::ValueType,right_value:&Self::ValueType)->Self::ValueType;fn unit()->Self::ValueType;}pub mod add{use crate::__cargo_equip::preludes::monoid::*;use std::{marker::PhantomData,ops::Add};use crate::__cargo_equip::crates::monoid::Monoid;use numeric::zero::Zero;pub struct Additive(PhantomDataT>);implMonoid for Additivewhere T:Add+Copy+Zero,{type ValueType=T;fn op(left_value:&Self::ValueType,right_value:&Self::ValueType)->Self::ValueType{*left_value+*right_value}fn unit()->Self::ValueType{T::zero()}}}pub mod affine{use crate::__cargo_equip::preludes::monoid::*;use std::{marker::PhantomData,ops::{Add,Mul},};use crate::__cargo_equip::crates::monoid::Monoid;use numeric::{one::One,zero::Zero};#[derive(Clone)]pub struct Affine(pub T,pub T);implAffinewhere T:Clone+Add+Mul,{pub fn eval(self,x:T)->T{self.0*x+self.1}}pub struct AffineOperator(PhantomDataT>);implMonoid for AffineOperatorwhere T:Copy+Add+Mul+Zero+One,{type ValueType=Affine;fn op(left_value:&Self::ValueType,right_value:&Self::ValueType)->Self::ValueType{if REV{return Affine(right_value.0*left_value.0,right_value.0*left_value.1+right_value.1,);}Affine(left_value.0*right_value.0,left_value.0*right_value.1+left_value.1,)}fn unit()->Self::ValueType{Affine(T::one(),T::zero())}}}pub mod bitwise_and{use crate::__cargo_equip::preludes::monoid::*;use std::{marker::PhantomData,ops::{BitAnd,Not},};use crate::__cargo_equip::crates::monoid::Monoid;use numeric::zero::Zero;pub struct BitwiseAnd(PhantomDataT>);implMonoid for BitwiseAndwhere T:Copy+BitAnd+Not+Zero,{type ValueType=T;fn op(left_value:&Self::ValueType,right_value:&Self::ValueType)->Self::ValueType{*left_value&*right_value}fn unit()->Self::ValueType{!T::zero()}}}pub mod bitwise_or{use crate::__cargo_equip::preludes::monoid::*;use std::{marker::PhantomData,ops::BitOr};use crate::__cargo_equip::crates::monoid::Monoid;use numeric::zero::Zero;pub struct BitwiseOr(PhantomDataT>);implMonoid for BitwiseOrwhere T:Copy+BitOr+Zero,{type ValueType=T;fn op(left_value:&Self::ValueType,right_value:&Self::ValueType)->Self::ValueType{*left_value|*right_value}fn unit()->Self::ValueType{T::zero()}}}pub mod bitwise_xor{use crate::__cargo_equip::preludes::monoid::*;use std::{marker::PhantomData,ops::BitXor};use crate::__cargo_equip::crates::monoid::Monoid;use numeric::zero::Zero;pub struct BitwiseXor(PhantomDataT>);implMonoid for BitwiseXorwhere T:Copy+BitXor+Zero,{type ValueType=T;fn op(left_value:&Self::ValueType,right_value:&Self::ValueType)->Self::ValueType{*left_value^*right_value}fn unit()->Self::ValueType{T::zero()}}}pub mod max{use crate::__cargo_equip::preludes::monoid::*;use std::marker::PhantomData;use crate::__cargo_equip::crates::monoid::Monoid;use numeric::bound::BoundedBelow;pub struct Max(PhantomDataT>);implMonoid for Maxwhere T:Copy+Ord+BoundedBelow,{type ValueType=T;fn op(left_value:&Self::ValueType,right_value:&Self::ValueType)->Self::ValueType{std::cmp::max(*left_value,*right_value)}fn unit()->Self::ValueType{T::min_value()}}}pub mod max_with_index{use crate::__cargo_equip::preludes::monoid::*;use std::marker::PhantomData;use crate::__cargo_equip::crates::monoid::Monoid;use numeric::bound::BoundedBelow;#[derive(Clone,Copy)]#[allow(unused)]pub struct MaxWithIndex{max_value:T,max_index:usize,}pub struct MaxWithIndexOperator(PhantomDataT>);implMonoid for MaxWithIndexOperatorwhere T:Copy+Ord+BoundedBelow,{type ValueType=MaxWithIndex;fn op(left_value:&Self::ValueType,right_value:&Self::ValueType)->Self::ValueType{if left_value.max_valueSelf::ValueType{MaxWithIndex{max_value:T::min_value(),max_index:0,}}}}pub mod min{use crate::__cargo_equip::preludes::monoid::*;use std::marker::PhantomData;use crate::__cargo_equip::crates::monoid::Monoid;use numeric::bound::BoundedAbove;pub struct Min(PhantomDataT>);implMonoid for Minwhere T:Copy+Ord+BoundedAbove,{type ValueType=T;fn op(left_value:&Self::ValueType,right_value:&Self::ValueType)->Self::ValueType{std::cmp::min(*left_value,*right_value)}fn unit()->Self::ValueType{T::max_value()}}}pub mod min_with_index{use crate::__cargo_equip::preludes::monoid::*;use std::marker::PhantomData;use crate::__cargo_equip::crates::monoid::Monoid;use numeric::bound::BoundedAbove;#[derive(Clone,Copy)]#[allow(unused)]pub struct MinWithIndex{min_value:T,min_index:usize,}pub struct MinWithIndexOperator(PhantomDataT>);implMonoid for MinWithIndexOperatorwhere T:Copy+Ord+BoundedAbove,{type ValueType=MinWithIndex;fn op(left_value:&Self::ValueType,right_value:&Self::ValueType)->Self::ValueType{if left_value.min_value>right_value.min_value{*right_value}else{*left_value}}fn unit()->Self::ValueType{MinWithIndex{min_value:T::max_value(),min_index:0,}}}}pub mod mul{use crate::__cargo_equip::preludes::monoid::*;use std::{marker::PhantomData,ops::Mul};use crate::__cargo_equip::crates::monoid::Monoid;use numeric::one::One;pub struct Multiplicative(PhantomDataT>);implMonoid for Multiplicativewhere T:Mul+Copy+One,{type ValueType=T;fn op(left_value:&Self::ValueType,right_value:&Self::ValueType)->Self::ValueType{*left_value**right_value}fn unit()->Self::ValueType{T::one()}}}} pub mod __numeric_0_1_0 {pub mod bound{pub trait BoundedBelow{fn min_value()->Self;}pub trait BoundedAbove{fn max_value()->Self;}macro_rules!impl_bound_integer{($($ty:ty),*)=>{$(impl BoundedBelow for$ty{#[inline]fn min_value()->Self{Self::MIN}}impl BoundedAbove for$ty{#[inline]fn max_value()->Self{Self::MAX}})*};}impl_bound_integer!(i8,i16,i32,i64,i128,isize,u8,u16,u32,u64,u128,usize);}pub mod infinity{pub trait Infinity{fn infinity()->Self;}pub trait NegInfinity{fn negative_infinity()->Self;}macro_rules!impl_infinity{($($t:ty,$infinity_value:expr,)*)=>{$(impl Infinity for$t{fn infinity()->Self{$infinity_value}})*}}macro_rules!impl_negative_infinity{($($t:ty,$neg_infinity_value:expr,)*)=>{$(impl NegInfinity for$t{fn negative_infinity()->Self{$neg_infinity_value}})*}}impl_infinity!{i32,1_i32<<30,u32,1_u32<<30,f32,1e10,i64,1_i64<<60,isize,1_isize<<60,u64,1_u64<<60,usize,1_usize<<60,f64,1e20,i128,1_i128<<120,u128,1_u128<<120,}impl_negative_infinity!{i32,-1_i32<<30,u32,0,f32,-1e10,i64,-1_i64<<60,isize,-1_isize<<60,u64,0,usize,0,f64,1e20,i128,-1_i128<<120,u128,0,}}pub mod one{pub trait One{fn one()->Self;}macro_rules!impl_one_integer{($($ty:ty),*)=>{$(impl One for$ty{#[inline]fn one()->Self{1}})*};}macro_rules!impl_one_float{($($ty:ty),*)=>{$(impl One for$ty{#[inline]fn one()->Self{1.}})*};}impl_one_integer!(u8,u16,u32,u64,u128,usize,i8,i16,i32,i64,i128,isize);impl_one_float!(f32,f64);}pub mod zero{pub trait Zero{fn zero()->Self;}macro_rules!impl_zero_integer{($($ty:ty),*)=>{$(impl Zero for$ty{#[inline]fn zero()->Self{0}})*};}macro_rules!impl_zero_float{($($ty:ty),*)=>{$(impl Zero for$ty{#[inline]fn zero()->Self{0.}})*};}impl_zero_integer!(u8,u16,u32,u64,u128,usize,i8,i16,i32,i64,i128,isize);impl_zero_float!(f32,f64);}} } pub(crate) mod macros { pub mod dynamic_segment_tree {} pub mod monoid {} pub mod __numeric_0_1_0 {} } pub(crate) mod prelude {pub use crate::__cargo_equip::crates::*;} mod preludes { pub mod dynamic_segment_tree {pub(in crate::__cargo_equip)use crate::__cargo_equip::crates::monoid;} pub mod monoid {pub(in crate::__cargo_equip)use crate::__cargo_equip::crates::__numeric_0_1_0 as numeric;} pub mod __numeric_0_1_0 {} } }