pub trait Magma: Sized + Clone { fn op(&self, rhs: &Self) -> Self; } pub trait Associative: Magma {} pub trait Unital: Magma { fn identity() -> Self; } pub trait Monoid: Magma + Associative + Unital {} impl Monoid for T {} pub enum Node { Section(Box>), Leaf(Leaf), None, } pub struct Section { left: Node, right: Node, val: T, } pub struct Leaf { i: usize, val: T, } impl Leaf { fn new(i: usize, x: T) -> Self { Leaf { i: i, val: x } } fn fold(&self) -> T { self.val.clone() } } impl Section { fn new() -> Self { Section { left: Node::None, right: Node::None, val: T::identity(), } } fn fold(&self) -> T { self.val.clone() } fn update(&mut self, i: usize, x: T, l: usize, r: usize) { let m = (l + r) >> 1; if i < m { let left = self.left.take(); self.left = left.update(i, x, l, m); } else { let right = self.right.take(); self.right = right.update(i, x, m, r); } self.val = self.left.fold().op(&self.right.fold()); } } impl Node { fn take(&mut self) -> Node { std::mem::replace(self, Node::None) } fn fold(&self) -> T { match self { &Node::Section(ref sec) => sec.as_ref().fold(), &Node::Leaf(ref leaf) => leaf.fold(), &Node::None => T::identity(), } } fn update(self, i: usize, x: T, l: usize, r: usize) -> Self { match self { Node::Section(mut sec) => { sec.as_mut().update(i, x, l, r); Node::Section(sec) } Node::Leaf(leaf) => { if leaf.i == i { Node::Leaf(Leaf::new(i, x)) } else { let mut new_section = Section::new(); let m = (l + r) >> 1; if leaf.i < m { new_section.left = Node::Leaf(leaf); } else { new_section.right = Node::Leaf(leaf); } new_section.update(i, x, l, r); Node::Section(Box::new(new_section)) } } Node::None => { Node::Leaf(Leaf::new(i, x)) } } } fn range_fold(&self, a: usize, b: usize, l: usize, r: usize) -> T { match self { &Node::Section(ref sec) => { if b <= l || r <= a { T::identity() } else if a <= l && r <= b { sec.fold() } else { let m = (l + r) >> 1; sec.left.range_fold(a, b, l, m).op(&sec.right.range_fold(a, b, m, r)) } } &Node::Leaf(ref leaf) => { if a <= leaf.i && leaf.i < b { leaf.fold() } else { T::identity() } } &Node::None => T::identity(), } } } pub struct DynamicSegmentTree { root: Node, n: usize, } impl DynamicSegmentTree { pub fn new(sz: usize) -> Self { let mut n = 1; while n < sz { n = n << 1; } DynamicSegmentTree { root: Node::None, n: n, } } pub fn update(&mut self, i: usize, x: T) { let r = self.root.take(); self.root = r.update(i, x, 0, self.n); } pub fn fold(&self, l: usize, r: usize) -> T { self.root.range_fold(l, r, 0, self.n) } } #[derive(Clone)] struct A(usize); impl Magma for A { fn op(&self, a: &Self) -> Self { A(self.0 + a.0) } } impl Associative for A {} impl Unital for A { fn identity() -> Self { A(0) } } use std::io::Read; fn main() { let mut buf = String::new(); std::io::stdin().read_to_string(&mut buf).unwrap(); let mut iter = buf.split_whitespace(); let q: usize = iter.next().unwrap().parse().unwrap(); let mut dyseg = DynamicSegmentTree::::new(1_000_000_100); let mut ans = A(0); for _ in 0..q { let query: usize = iter.next().unwrap().parse().unwrap(); let a: usize = iter.next().unwrap().parse().unwrap(); let b: usize = iter.next().unwrap().parse().unwrap(); if query == 0 { let val = dyseg.fold(a, a + 1).op(&A(b)); dyseg.update(a, val); } else if query == 1 { ans = ans.op(&dyseg.fold(a, b + 1)); } } println!("{}", ans.0); }