fn getline() -> String { let mut ret = String::new(); std::io::stdin().read_line(&mut ret).unwrap(); ret } struct BIT2D { n: i32, m: i32, dat: std::collections::HashMap<(i32, i32), i64>, } impl BIT2D { pub fn new(n: i32, m: i32) -> Self { BIT2D { n: n, m: m, dat: std::collections::HashMap::with_capacity((n + m) as usize), } } pub fn add(&mut self, x: i32, y: i32, val: i64) { let mut x = x; while x <= self.n { let mut y = y; while y <= self.m { *self.dat.entry((x, y)).or_insert(0) += val; y += y & -y; } x += x & -x; } } pub fn sum(&self, mut xl: i32, mut xr: i32, y: i32) -> i64 { let mut sum = 0; let get = |x: i32| -> i64 { let mut y = y; let mut sum = 0; while y > 0 { sum += self.dat.get(&(x, y)).unwrap_or(&0); y -= y & -y; } sum }; while xr != xl { if xr > xl { sum += get(xr); xr -= xr & -xr; } else { sum -= get(xl); xl -= xl & -xl; } } sum } } // https://yukicoder.me/problems/no/3313 (3) // 区間の交差 + クエリー問題 // -> WA。i < j という条件を見落としていた。これがあると動的セグメント木が必要になるはず。 // Tags: dynamic-segment-trees, dynamic-2d-segment-trees fn main() { let n = getline().trim().parse::().unwrap(); let mut lr = vec![]; let mut ls = vec![]; let mut rs = vec![]; for _ in 0..n { let ints = getline().trim().split_whitespace() .map(|x| x.parse::().unwrap()) .collect::>(); lr.push((ints[0], ints[1])); ls.push(ints[0]); rs.push(ints[1]); } ls.sort(); ls.dedup(); rs.sort(); rs.dedup(); const W: i32 = 1 << 19; let mut bit = BIT2D::new(W, W); let mut ans = 0i64; for i in 0..n { if i % 1000 == 0 { eprintln!("trial {i} out of {n}"); } let (l, r) = lr[i]; let l = ls.binary_search(&l).unwrap() as i32; let r = rs.binary_search(&r).unwrap() as i32; ans += bit.sum(0, l + 1, W) - bit.sum(0, l + 1, r + 1); bit.add(l + 1, r + 1, 1); } println!("{ans}"); }