fn getline() -> String { let mut ret = String::new(); std::io::stdin().read_line(&mut ret).unwrap(); ret } // (+, 0) struct Dyn2DSegTree { n: i64, root: Node, e: i64, } struct Node { val: i64, l: Option>, r: Option>, } impl Dyn2DSegTree { fn new(n: i64) -> Self { assert_eq!(n & -n, n); Dyn2DSegTree { n: n, root: Node::new(0), e: 0, } } // O(log^2 n) fn query(&self, x: std::ops::Range, y: std::ops::Range) -> i64 { self.query_sub(Some(&self.root), x.start, x.end, 0, self.n, y.start, y.end, 0, self.n) } fn query_sub(&self, node: Option<&Node>, lx: i64, rx: i64, ax: i64, bx: i64, ly: i64, ry: i64, ay: i64, by: i64) -> i64 { let node = if let Some(node) = node { node } else { return self.e; }; if rx <= ax || bx <= lx || ry <= ay || by <= ly { return self.e; } if lx <= ax && bx <= rx && ly <= ay && by <= ry { return node.val; } if bx - ax >= by - ay { // bisect on x assert!(bx - ax >= 2); let mid = (bx + ax) / 2; let p = self.query_sub(node.l.as_deref(), lx, rx, ax, mid, ly, ry, ay, by); let q = self.query_sub(node.r.as_deref(), lx, rx, mid, bx, ly, ry, ay, by); return p + q; // op } // bisect on y assert!(by - ay >= 2); let mid = (by + ay) / 2; let p = self.query_sub(node.l.as_deref(), lx, rx, ax, bx, ly, ry, ay, mid); let q = self.query_sub(node.r.as_deref(), lx, rx, ax, bx, ly, ry, mid, by); p + q // op } fn update(&mut self, x: i64, y: i64, val: i64) { let n = self.n; Self::update_sub(&mut self.root, x, y, val, self.e, 0, n, 0, n); } fn update_sub(node: &mut Node, x: i64, y: i64, val: i64, e: i64, ax: i64, bx: i64, ay: i64, by: i64) { if x < ax || bx <= x || y < ay || by <= y { unreachable!(); } if (ax, bx) == (x, x + 1) && (ay, by) == (y, y + 1) { node.val = val; return; } if bx - ax >= by - ay { // bisect on x assert!(bx - ax >= 2); let mid = (bx + ax) / 2; if x >= mid { if node.r.is_none() { node.r = Some(Box::new(Node::new(e))); } Self::update_sub(node.r.as_mut().unwrap(), x, y, val, e, mid, bx, ay, by); } else { if node.l.is_none() { node.l = Some(Box::new(Node::new(e))); } Self::update_sub(node.l.as_mut().unwrap(), x, y, val, e, ax, mid, ay, by); } } else { // bisect on y assert!(by - ay >= 2); let mid = (by + ay) / 2; if y >= mid { if node.r.is_none() { node.r = Some(Box::new(Node::new(e))); } Self::update_sub(node.r.as_mut().unwrap(), x, y, val, e, ax, bx, mid, by); } else { if node.l.is_none() { node.l = Some(Box::new(Node::new(e))); } Self::update_sub(node.l.as_mut().unwrap(), x, y, val, e, ax, bx, ay, mid); } } let p = node.l.as_ref().map(|v| v.val).unwrap_or(e); let q = node.r.as_ref().map(|v| v.val).unwrap_or(e); node.val = p + q; // op } } impl Node { fn new(e: i64) -> Self { Node { val: e, l: None, r: None, } } } // 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: usize = 1 << 19; let mut st = Dyn2DSegTree::new(W as i64); let mut ans = 0i64; for i in 0..n { let (l, r) = lr[i]; let l = ls.binary_search(&l).unwrap() as i64; let r = rs.binary_search(&r).unwrap() as i64; ans += st.query(0..l, r..W as i64); st.update(l, r, 1); } println!("{ans}"); }