use std::collections::BTreeMap; 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 } } pub struct SegmentTreeSparseStatic where M: Monoid, { size: usize, points: Vec, cordinate: BTreeMap, data: Vec, } impl SegmentTreeSparseStatic where M: Monoid, M::S: Clone, { pub fn new() -> Self { SegmentTreeSparseStatic:: { size: 0, points: vec![], cordinate: BTreeMap::new(), data: vec![], } } pub fn point_add(&mut self, idx: usize) { self.points.push(idx); } pub fn build(&mut self) { let mut o = self.points.iter().cloned().collect::>(); o.sort(); o.dedup(); self.cordinate = (0..o.len()).map(|i| (o[i], i)).collect(); self.size = self.cordinate.len().next_power_of_two(); self.data.resize(2 * self.size - 1, M::id()); } pub fn get(&self, mut idx: usize) -> M::S { idx = *self.cordinate.get(&idx).unwrap() + self.size - 1; self.data[idx].clone() } pub fn update(&mut self, mut idx: usize, x: M::S) { idx = *self.cordinate.get(&idx).unwrap() + self.size - 1; self.data[idx] = x; while idx > 0 { idx = (idx - 1) / 2; self.data[idx] = M::op(&self.data[2 * idx + 1], &self.data[2 * idx + 2]); } } pub fn fold(&self, mut l: usize, mut r: usize) -> M::S { if l >= r { return M::id(); } l = *self .cordinate .range(&l..) .next() .map(|x| x.1) .unwrap_or(&self.size) + self.size - 1; r = *self .cordinate .range(&r..) .next() .map(|x| x.1) .unwrap_or(&self.size) + 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[l]); } if r % 2 == 0 { sum_r = M::op(&self.data[r - 1], &sum_r); } l = l / 2; r = (r - 1) / 2; } M::op(&sum_l, &sum_r) } } fn main() { let n; { let mut s = String::new(); std::io::stdin().read_line(&mut s).unwrap(); let mut ws = s.split_whitespace(); n = ws.next().unwrap().parse::().unwrap(); } let query; { let mut res: Vec<_> = vec![]; for _ in 0..n { let mut s = String::new(); std::io::stdin().read_line(&mut s).unwrap(); let mut ws = s.split_whitespace(); res.push(( ws.next().unwrap().parse::().unwrap(), ws.next().unwrap().parse::().unwrap(), ws.next().unwrap().parse::().unwrap(), )); } query = res; } let mut seg = SegmentTreeSparseStatic::::new(); for i in 0..n { let (q, x, _) = query[i]; if q == 0 { seg.point_add(x); } } seg.build(); let mut ans = 0; for i in 0..n { let (q, x, y) = query[i]; if q == 0 { let a = seg.get(x); seg.update(x, a + y); } else { ans += seg.fold(x, y + 1); } } println!("{}", ans); }