use proconio::input; struct SegmentTree { size: usize, a: Vec>, } impl SegmentTree { fn new(n: usize) -> Self { let mut size = 1usize; while size < n { size <<= 1; } Self { size, a: vec![Vec::new(); 2 * size], } } fn set(&mut self, x: usize, j: usize) { let mut idx = self.size + x; self.a[idx].push(j); while idx > 1 { idx >>= 1; let left = idx << 1; let right = left | 1; // --- 借用衝突回避のため clone --- let left_vec = self.a[left].clone(); let right_vec = self.a[right].clone(); let dst = &mut self.a[idx]; Self::merge(dst, &left_vec, &right_vec); } } fn merge(dst: &mut Vec, left: &Vec, right: &Vec) { dst.clear(); dst.reserve(left.len() + right.len()); let mut i = 0usize; let mut j = 0usize; while i < left.len() || j < right.len() { if i < left.len() && j < right.len() { if left[i] <= right[j] { dst.push(left[i]); i += 1; } else { dst.push(right[j]); j += 1; } } else if i < left.len() { dst.push(left[i]); i += 1; } else { dst.push(right[j]); j += 1; } } } // Python の _calc と等価 fn calc(array: &Vec, x: usize) -> usize { if array.is_empty() { return 0; } if x <= array[0] { return array.len(); } // lower_bound let mut lo = 0usize; let mut hi = array.len(); while lo < hi { let mid = (lo + hi) / 2; if array[mid] < x { lo = mid + 1; } else { hi = mid; } } array.len() - lo } fn get_sum(&self, l: usize, r: usize, x: usize) -> usize { let mut L = self.size + l; let mut R = self.size + r; let mut res = 0usize; while L < R { if (R & 1) == 1 { R -= 1; res += Self::calc(&self.a[R], x); } if (L & 1) == 1 { res += Self::calc(&self.a[L], x); L += 1; } L >>= 1; R >>= 1; } res } } fn main() { input! { n: usize, lr_in: [(usize, usize); n], } let mut max_r = 0usize; let mut lr: Vec<(usize, usize, usize)> = Vec::with_capacity(n); for (i, (l, r)) in lr_in.into_iter().enumerate() { max_r = max_r.max(r); lr.push((l, r, i)); } // l の降順(Python の reverse=True) lr.sort_by(|a, b| b.0.cmp(&a.0)); let mut seg = SegmentTree::new(max_r + 1); let mut ans: i64 = 0; for (l, r, idx) in lr { ans += seg.get_sum(l, r, idx) as i64; seg.set(r, idx); } println!("{}", ans); }