fn main() { let mut io = IO::new(); input!{ from io, q: usize, query:[(i32, i64, i64); q] } let mut xs = Vec::with_capacity(2 * q); for &(t, a, b) in &query { xs.push(a); if t == 1 { xs.push(b); } } let (dict, _) = compress(&xs, 1); let mut bit = FenwickTree::new(dict.len() + 5); let mut ans = 0; for &(t, a, b) in &query { if t == 0 { let u = *dict.get(&a).unwrap(); bit.add(u, b); } else { let u = *dict.get(&a).unwrap(); let v = *dict.get(&b).unwrap(); ans += bit.sum(u..=v); } } io.println(ans); } use std::collections::HashMap; use std::hash::Hash; pub fn compress(l: &[T], start: usize)-> (HashMap, Vec) { let mut f = l.to_owned(); f.sort(); f.dedup(); let dict: HashMap = f.iter().cloned().zip(start..f.len()+start).collect(); let res: Vec = l.iter().map(|x| *dict.get(x).unwrap()).collect(); (dict, res) } // ------------ FenwickTree with generics start ------------ #[derive(Clone, Debug)] pub struct FenwickTree(Vec); impl FenwickTree { #[inline] fn lsb(x: usize) -> usize { x & x.wrapping_neg() } pub fn new(n: usize) -> Self { Self(vec![T::zero(); n+1]) } pub fn prefix_sum(&self, i: usize) -> T { std::iter::successors(Some(i), |&i| Some(i - Self::lsb(i))) .take_while(|&i| i != 0) .map(|i| self.0[i].clone()) .fold(T::zero(), |sum, x| sum + x) } pub fn add(&mut self, i: usize, x: T) { let n = self.0.len(); std::iter::successors(Some(i + 1), |&i| Some(i + Self::lsb(i))) .take_while(|&i| i < n) .for_each(|i| self.0[i] = self.0[i].clone() + x.clone()); } /// pred(j, sum(..j)) && !pred(j+1, sum(..j+1)) pub fn partition(&self, pred: impl Fn(usize, &T) -> bool) -> (usize, T) { assert!(pred(0, &self.0[0]), "need to be pred(0, 0)"); let mut j = 0; let mut current = self.0[0].clone(); let n = self.0.len(); for d in std::iter::successors(Some(n.next_power_of_two() >> 1), |&d| { Some(d >> 1)}) .take_while(|&d| d != 0) { if j + d < n { let next = current.clone() + self.0[j + d].clone(); if pred(j + d, &next) { current = next; j += d; } } } (j, current) } } impl From> for FenwickTree { fn from(src: Vec) -> Self { let mut table = std::iter::once(T::zero()) .chain(src.into_iter()) .collect::>(); let n = table.len(); (1..n) .map(|i| (i, i + Self::lsb(i))) .filter(|&(_, j)| j < n) .for_each(|(i, j)| { table[j] = table[j].clone() + table[i].clone(); }); Self(table) } } impl FenwickTree { pub fn sum>(&self, rng: R) -> T { let Range { start, end } = bounds_within(rng, self.0.len() - 1); self.prefix_sum(end) + -self.prefix_sum(start) } } // ------------ FenwickTree with generics end ------------ use std::ops::Bound::{Excluded, Included, Unbounded}; use std::ops::{Range, RangeBounds}; /// 区間を配列サイズに収まるように丸める。 /// /// 与えられた区間 `r` と `0..len` の共通部分を、有界な半開区間として返す。 /// /// # Examples /// ``` /// use bibliotheca::utils::bounds::bounds_within; /// /// assert_eq!(bounds_within(.., 7), 0..7); /// assert_eq!(bounds_within(..=4, 7), 0..5); /// ``` pub fn bounds_within>(r: R, len: usize) -> Range { let e_ex = match r.end_bound() { Included(&e) => e + 1, Excluded(&e) => e, Unbounded => len, } .min(len); let s_in = match r.start_bound() { Included(&s) => s, Excluded(&s) => s + 1, Unbounded => 0, } .min(e_ex); s_in..e_ex } // ------------ algebraic traits start ------------ use std::marker::Sized; use std::ops::*; /// 元 pub trait Element: Sized + Clone + PartialEq {} impl Element for T {} /// 結合性 pub trait Associative: Magma {} /// マグマ pub trait Magma: Element + Add {} impl> Magma for T {} /// 半群 pub trait SemiGroup: Magma + Associative {} impl SemiGroup for T {} /// モノイド pub trait Monoid: SemiGroup + Zero {} impl Monoid for T {} pub trait ComMonoid: Monoid + AddAssign {} impl ComMonoid for T {} /// 群 pub trait Group: Monoid + Neg {} impl> Group for T {} pub trait ComGroup: Group + ComMonoid {} impl ComGroup for T {} /// 半環 pub trait SemiRing: ComMonoid + Mul + One {} impl + One> SemiRing for T {} /// 環 pub trait Ring: ComGroup + SemiRing {} impl Ring for T {} pub trait ComRing: Ring + MulAssign {} impl ComRing for T {} /// 体 pub trait Field: ComRing + Div + DivAssign {} impl + DivAssign> Field for T {} /// 加法単元 pub trait Zero: Element { fn zero() -> Self; fn is_zero(&self) -> bool { *self == Self::zero() } } /// 乗法単元 pub trait One: Element { fn one() -> Self; fn is_one(&self) -> bool { *self == Self::one() } } macro_rules! impl_integer { ($($T:ty,)*) => { $( impl Associative for $T {} impl Zero for $T { fn zero() -> Self { 0 } fn is_zero(&self) -> bool { *self == 0 } } impl<'a> Zero for &'a $T { fn zero() -> Self { &0 } fn is_zero(&self) -> bool { *self == &0 } } impl One for $T { fn one() -> Self { 1 } fn is_one(&self) -> bool { *self == 1 } } impl<'a> One for &'a $T { fn one() -> Self { &1 } fn is_one(&self) -> bool { *self == &1 } } )* }; } impl_integer! { i8, i16, i32, i64, i128, isize, u8, u16, u32, u64, u128, usize, } // ------------ algebraic traits end ------------ // ------------ io module start ------------ use std::io::{stdout, BufWriter, Read, StdoutLock, Write}; pub struct IO { iter: std::str::SplitAsciiWhitespace<'static>, buf: BufWriter>, } impl IO { pub fn new() -> Self { let mut input = String::new(); std::io::stdin().read_to_string(&mut input).unwrap(); let input = Box::leak(input.into_boxed_str()); let out = Box::new(stdout()); IO { iter: input.split_ascii_whitespace(), buf: BufWriter::new(Box::leak(out).lock()), } } fn scan_str(&mut self) -> &'static str { self.iter.next().unwrap() } pub fn scan(&mut self) -> ::Output { ::scan(self) } pub fn scan_vec(&mut self, n: usize) -> Vec<::Output> { (0..n).map(|_| self.scan::()).collect() } pub fn print(&mut self, x: T) { ::print(self, x); } pub fn println(&mut self, x: T) { self.print(x); self.print("\n"); } pub fn iterln>(&mut self, mut iter: I, delim: &str) { if let Some(v) = iter.next() { self.print(v); for v in iter { self.print(delim); self.print(v); } } self.print("\n"); } pub fn flush(&mut self) { self.buf.flush().unwrap(); } } impl Default for IO { fn default() -> Self { Self::new() } } pub trait Scan { type Output; fn scan(io: &mut IO) -> Self::Output; } macro_rules! impl_scan { ($($t:tt),*) => { $( impl Scan for $t { type Output = Self; fn scan(s: &mut IO) -> Self::Output { s.scan_str().parse().unwrap() } } )* }; } impl_scan!(i16, i32, i64, isize, u16, u32, u64, usize, String); pub enum Bytes {} impl Scan for Bytes { type Output = &'static [u8]; fn scan(s: &mut IO) -> Self::Output { s.scan_str().as_bytes() } } pub enum Chars {} impl Scan for Chars { type Output = Vec; fn scan(s: &mut IO) -> Self::Output { s.scan_str().chars().collect() } } pub enum Usize1 {} impl Scan for Usize1 { type Output = usize; fn scan(s: &mut IO) -> Self::Output { s.scan::().wrapping_sub(1) } } impl Scan for (T, U) { type Output = (T::Output, U::Output); fn scan(s: &mut IO) -> Self::Output { (T::scan(s), U::scan(s)) } } impl Scan for (T, U, V) { type Output = (T::Output, U::Output, V::Output); fn scan(s: &mut IO) -> Self::Output { (T::scan(s), U::scan(s), V::scan(s)) } } impl Scan for (T, U, V, W) { type Output = (T::Output, U::Output, V::Output, W::Output); fn scan(s: &mut IO) -> Self::Output { (T::scan(s), U::scan(s), V::scan(s), W::scan(s)) } } pub trait Print { fn print(w: &mut IO, x: Self); } macro_rules! impl_print_int { ($($t:ty),*) => { $( impl Print for $t { fn print(w: &mut IO, x: Self) { w.buf.write_all(x.to_string().as_bytes()).unwrap(); } } )* }; } impl_print_int!(i16, i32, i64, isize, u16, u32, u64, usize); impl Print for u8 { fn print(w: &mut IO, x: Self) { w.buf.write_all(&[x]).unwrap(); } } impl Print for &[u8] { fn print(w: &mut IO, x: Self) { w.buf.write_all(x).unwrap(); } } impl Print for &str { fn print(w: &mut IO, x: Self) { w.print(x.as_bytes()); } } impl Print for String { fn print(w: &mut IO, x: Self) { w.print(x.as_bytes()); } } impl Print for (T, U) { fn print(w: &mut IO, (x, y): Self) { w.print(x); w.print(" "); w.print(y); } } impl Print for (T, U, V) { fn print(w: &mut IO, (x, y, z): Self) { w.print(x); w.print(" "); w.print(y); w.print(" "); w.print(z); } } mod neboccoio_macro { #[macro_export] macro_rules! input { (@start $io:tt @read @rest) => {}; (@start $io:tt @read @rest, $($rest: tt)*) => { input!(@start $io @read @rest $($rest)*) }; (@start $io:tt @read @rest mut $($rest:tt)*) => { input!(@start $io @read @mut [mut] @rest $($rest)*) }; (@start $io:tt @read @rest $($rest:tt)*) => { input!(@start $io @read @mut [] @rest $($rest)*) }; (@start $io:tt @read @mut [$($mut:tt)?] @rest $var:tt: [$kind:tt; $len:expr] $($rest:tt)*) => { let $($mut)* $var = $io.scan_vec::<$kind>($len); input!(@start $io @read @rest $($rest)*) }; (@start $io:tt @read @mut [$($mut:tt)?] @rest $var:tt: $kind:tt $($rest:tt)*) => { let $($mut)* $var = $io.scan::<$kind>(); input!(@start $io @read @rest $($rest)*) }; (from $io:tt $($rest:tt)*) => { input!(@start $io @read @rest $($rest)*) }; } } // ------------ io module end ------------