use std::collections::HashMap; #[macro_export] macro_rules! read_line { ($($xs: tt)*) => { let mut buf = String::new(); std::io::stdin().read_line(&mut buf).unwrap(); let mut iter = buf.split_whitespace(); expand!(iter, $($xs)*); }; } #[macro_export] macro_rules! expand { ($iter: expr,) => {}; ($iter: expr, mut $var: ident : $type: tt, $($xs: tt)*) => { let mut $var = value!($iter, $type); expand!($iter, $($xs)*); }; ($iter: expr, $var: ident : $type: tt, $($xs: tt)*) => { let $var = value!($iter, $type); expand!($iter, $($xs)*); }; } #[macro_export] macro_rules! value { ($iter:expr, ($($type: tt),*)) => { ($(value!($iter, $type)),*) }; ($iter: expr, [$type: tt; $len: expr]) => { (0..$len).map(|_| value!($iter, $type)).collect::>() }; ($iter: expr, Chars) => { value!($iter, String).unwrap().chars().collect::>() }; ($iter: expr, $type: ty) => { if let Some(v) = $iter.next() { v.parse::<$type>().ok() } else { None } }; } pub trait Monoid { type S; fn op(a: &Self::S, b: &Self::S) -> Self::S; fn id() -> Self::S; } pub struct AddMonoid; impl Monoid for AddMonoid { type S = usize; fn op(a: &Self::S, b: &Self::S) -> Self::S { *a + *b } fn id() -> Self::S { 0 } } /// Let $\\{a_{i}\\}_{i=1}^{N}$ be a sequence of type Monoid::S. pub struct SegmentTreeDynamic where M: Monoid, { size: usize, data: HashMap, } impl SegmentTreeDynamic where M: Monoid, M::S: Clone, { /// Creates a segment tree with $\\{a_{i}\\}_{i=1}^{N}$ inside. /// n: lenght of $\\{a_{i}\\}_{i=1}^{N}$ (i.e. N) pub fn new(n: usize) -> Self { let size = n.next_power_of_two(); SegmentTreeDynamic:: { size, data: HashMap::new(), } } /// Updates $a_{idx}$ to x. pub fn update(&mut self, mut idx: usize, x: M::S) { idx += self.size - 1; self.data.insert(idx, x); while idx > 0 { idx = (idx - 1) / 2; *self.data.entry(idx).or_insert(M::id()) = M::op( &self.data.get(&(2 * idx + 1)).unwrap_or(&M::id()), &self.data.get(&(2 * idx + 2)).unwrap_or(&M::id()), ); } } /// Returns $a_{idx}$. pub fn get(&self, idx: usize) -> M::S { self.fold(idx, idx + 1) } /// Returns the result (fold op $\left[a_{l}, ... ,a_{r}\right)).$ /// (i.e. Return $a_{l} (op) a_{l + 1} (op) \cdots (op) a_{r-1})$ /// Notice that this is a half-opened section. pub fn fold(&self, mut l: usize, mut r: usize) -> M::S { l += self.size - 1; r += self.size - 1; let mut sum_l = M::id(); let mut sum_r = M::id(); while l < r { if l % 2 == 0 { sum_l = M::op(&sum_l, &self.data.get(&(l)).unwrap_or(&M::id())); } if r % 2 == 0 { sum_r = M::op(&self.data.get(&(r - 1)).unwrap_or(&M::id()), &sum_r); } l = l / 2; r = (r - 1) / 2; } M::op(&sum_l, &sum_r) } } fn main() { read_line!(n: usize,); let n = n.unwrap(); let mut seg = SegmentTreeDynamic::::new(1000100010); let mut ans = 0; for _ in 0..n { read_line!(t: usize, x: usize, y: usize,); let t = t.unwrap(); let x = x.unwrap(); let y = y.unwrap(); if t == 0 { let temp = seg.get(x); seg.update(x, temp + y); } else { let l = x; let r = y; ans += seg.fold(l, r + 1); } } println!("{}", ans); }