競プロ典型 017

https://atcoder.jp/contests/typical90/tasks/typical90_q

ある線分に対し、Lが小さい線分でその線分が交わるものを数えます。その線分をとすると、となります。線分の集合(L, R)をLでソートします。そうして、BITを用意してに1を加えていきます。そして、その前にとなるRがいくつあるかを調べます。

// Crossing Segments
#![allow(non_snake_case)]

use std::collections::BTreeMap;


//////////////////// library ////////////////////

fn read<T: std::str::FromStr>() -> T {
    let mut line = String::new();
    std::io::stdin().read_line(&mut line).ok();
    line.trim().parse().ok().unwrap()
}

fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    read::<String>().split_whitespace()
            .map(|e| e.parse().ok().unwrap()).collect()
}


//////////////////// Binary Indexed Tree ////////////////////

struct BIT {
    v: Vec<i64>
}

impl BIT {
    fn ceil_two_pow(n: usize) -> usize {
        if n == 1 { 1 } else { BIT::ceil_two_pow((n+1)/2) * 2 }
    }
    
    fn new(m: usize) -> BIT {
        let n = BIT::ceil_two_pow(m);
        let v: Vec<i64> = vec![0; n+1];
        BIT { v }
    }
    
    // v_1 + ... + v_n
    fn sum(&self, n: usize) -> i64 {
        let mut s: i64 = 0;
        let mut m: i64 = n as i64;
        while m != 0 {
            s += self.v[m as usize];
            m -= m & (-m)
        }
        s
    }
    
    fn add(&mut self, n: usize, e: i64) {
        let mut m: i64 = n as i64;
        while (m as usize) < self.v.len() {
            self.v[m as usize] += e;
            m += m & (-m)
        }
    }
    
    fn to_vec(&self) -> Vec<i64> {
        let mut v: Vec<i64> = vec![];
        let mut prev_s = 0;
        for i in 1..self.v.len() {
            let s = self.sum(i);
            v.push(s - prev_s);
            prev_s = s
        }
        v
    }
}


//////////////////// process ////////////////////

type Point = (i32, i32);

fn read_point() -> Point {
    let v = read_vec();
    (v[0], v[1])
}

fn read_input() -> (usize, Vec<Point>) {
    let v = read_vec::<usize>();
    let (N, M) = (v[0], v[1]);
    let points: Vec<Point> = (0..M).map(|_| read_point()).collect();
    (N, points)
}

fn sort_by_x(points: &Vec<Point>) -> BTreeMap<i32, Vec<i32>> {
    let mut tree = BTreeMap::new();
    for &(x, y) in points.iter() {
        let e = tree.entry(x).or_insert(vec![]);
        (*e).push(y)
    }
    tree
}

fn count(tree: BTreeMap<i32, Vec<i32>>, N: usize) -> i64 {
    let mut counter: i64 = 0;
    let mut bit = BIT::new(N);
    for (&x, ys) in tree.iter() {
        for &y in ys.iter() {
            counter += bit.sum(y as usize - 1) - bit.sum(x as usize);
        }
        for &y in ys.iter() {
            bit.add(y as usize, 1);
        }
    }
    counter
}

fn F(N: usize, points: Vec<Point>) -> i64 {
    let tree_x = sort_by_x(&points);
    count(tree_x, N)
}

fn main() {
    let (N, points) = read_input();
    println!("{}", F(N, points))
}