AtCoder Beginner Contest 405 F

https://atcoder.jp/contests/abc405/tasks/abc405_f

エッジの端点をxとyとすると、エッジを平面上の点と考えるます。そうすると、それと交差するエッジの端点(x1, y1)は、1 ≤ x1 < xかつx < y1 < y、または、x < x1 < yかつy < y1 ≤ N*2を満たせばよいです。すなわち指定した2つの矩形内の点を数えればよいです。
これを高速に求めるには2次元のSegment Treeを作ればよいです。すなわち、x方向にSegment Treeを作って、その要素をy方向のSegment Treeにします。しかし、これではメモリが食いすぎるので、yのVecにしてソートしておけば、簡単に個数を求められます。

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


//////////////////// 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()
}


//////////////////// Segment Tree ////////////////////

type Range = (usize, usize);

struct SegmentTree {
    n: usize,
    v: Vec<Vec<usize>>,
}

impl SegmentTree {
    fn count_each(&self, i: usize, rng: Range,
                            first: usize, last: usize) -> usize {
        let w = &self.v[i];
        if w.is_empty() || rng.1 <= w[first] || rng.0 > w[last-1] {
            return 0
        }
        
        let mid = (first + last) / 2;
        if rng.0 <= w[first] && w[last-1] < rng.1 {
            last - first
        }
        else if rng.1 <= w[mid] {
            self.count_each(i, rng, first, mid)
        }
        else if rng.0 >= w[mid] {
            self.count_each(i, rng, mid, last)
        }
        else {
            self.count_each(i, rng, first, mid) +
            self.count_each(i, rng, mid, last)
        }
    }
    
    fn count(&self, rng1: Range, rng2: Range) -> usize {
        if rng1.0 == rng1.1 || rng2.0 == rng2.1 {
            0
        }
        else {
            self.count_core(rng1, rng2, 0, self.n, 0)
        }
    }
    
    fn count_core(&self, rng1: Range, rng2: Range,
                            first: usize, last: usize, i: usize) -> usize {
        if rng1.0 <= first && last <= rng1.1 {
            self.count_each(i, rng2, 0, self.v[i].len())
        }
        else {
            let mid = (first + last) / 2;
            if rng1.1 <= mid {
                self.count_core(rng1, rng2, first, mid, i*2+1)
            }
            else if rng1.0 >= mid {
                self.count_core(rng1, rng2, mid, last, i*2+2)
            }
            else {
                self.count_core(rng1, rng2, first, mid, i*2+1) +
                self.count_core(rng1, rng2, mid, last, i*2+2)
            }
        }
    }
    
    fn ceil_two_pow(n: usize) -> usize {
        if n == 1 { 1 } else { SegmentTree::ceil_two_pow((n+1)/2) * 2 }
    }
    
    fn merge(v1: &Vec<usize>, v2: &Vec<usize>) -> Vec<usize> {
        let mut v: Vec<usize> = vec![];
        let mut k: usize = 0;
        let mut l: usize = 0;
        while k < v1.len() && l < v2.len() {
            if v1[k] <= v2[l] {
                v.push(v1[k]);
                k += 1
            }
            else {
                v.push(v2[l]);
                l += 1
            }
        }
        v.extend(&v1[k..]);
        v.extend(&v2[l..]);
        v
    }
    
    fn create(N: usize, edges: Vec<Edge>) -> SegmentTree {
        let n = SegmentTree::ceil_two_pow(N*2);
        let mut v: Vec<Vec<usize>> = vec![vec![]; n*2-1];
        // 葉
        for (x, y) in edges {
            v[x+n-1].push(y)
        }
        // 葉をソート
        for i in n-1..n*2-1 {
            v[i].sort()
        }
        // 葉以外を葉に近いところから
        for i in (0..n-1).rev() {
            v[i] = SegmentTree::merge(&v[i*2+1], &v[i*2+2])
        }
        SegmentTree { n, v }
    }
}


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

type Edge = (usize, usize);

fn read_edge() -> Edge {
    let v: Vec<usize> = read_vec();
    (v[0] - 1, v[1] - 1)
}

fn read_input() -> (usize, Vec<Edge>, usize) {
    let v: Vec<usize> = read_vec();
    let (N, M) = (v[0], v[1]);
    let edges: Vec<Edge> = (0..M).map(|_| read_edge()).collect();
    let Q: usize = read();
    (N, edges, Q)
}

fn F_each((x, y): Edge, tree: &SegmentTree, N: usize) -> usize {
    tree.count((0, x), (x, y)) + tree.count((x, y), (y, N*2))
}

fn F(N: usize, edges: Vec<Edge>, Q: usize) {
    let tree = SegmentTree::create(N, edges);
    for _ in 0..Q {
        let edge = read_edge();
        println!("{}", F_each(edge, &tree, N))
    }
}

fn main() {
    let (N, edges, Q) = read_input();
    F(N, edges, Q)
}