AtCoder Beginner Contest 435 D

https://atcoder.jp/contests/abc435/tasks/abc435_e

範囲を覆うので木を利用したいですが、単純にSegment Treeを使うと空間が大きすぎて無理ですし、自力で木を作ると変な入力(1 1、2 2、3 3、…)にも対応しないといけないので平衡木にしなければならずコーディングが難しいです。
クエリーはそんなに大きい数ではないので、その端点を集めてソートして、その点同士の間の範囲を葉にしたSegment Treeを考えればよいです。

// Cover query
#![allow(non_snake_case)]

use std::cmp::{min, max};
use std::collections::BTreeSet;


//////////////////// 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 ////////////////////

const INF: i32 = 2_000_000_000;

type Range = (i32, i32);
type Node = (i32, i32, i32);    // (first, last, counter)
type NodeRange = (usize, usize, usize);

fn add_node((f1, _, c1): Node, (_, r2, c2): Node) -> Node {
    (f1, r2, c1 + c2)
}

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

impl SegmentTree {
    fn ceil_two_pow(n: usize) -> usize {
        if n == 1 { 1 } else { SegmentTree::ceil_two_pow((n+1)/2) * 2 }
    }
    
    fn new(pts: &Vec<i32>) -> SegmentTree {
        let N = pts.len();
        let n = SegmentTree::ceil_two_pow(N-1);
        let mut v: Vec<Node> = vec![(INF, INF, 0); n*2-1];
        for i in n-1..n+N-2 {
            v[i] = (pts[i+1-n], pts[i+2-n], 0)
        }
        for i in (0..n-1).rev() {
            v[i] = (v[i*2+1].0, v[i*2+2].1, 0)
        }
        SegmentTree { n, v }
    }
    
    fn update(&mut self, rng: &Range) {
        self.update_core(rng, (0, self.n, 0))
    }
    
    fn update_core(&mut self, rng: &Range, (first, last, n): NodeRange) {
        let f = self.v[n].0;
        let l = self.v[n].1;
        if self.v[n].1 - self.v[n].0 == self.v[n].2 {
            // 全て黒
            return
        }
        else if rng.0 <= f && l <= rng.1 {
            self.v[n] = (f, l, l - f)
        }
        else {
            let m = self.v[n*2+1].1;
            let mid = (first + last) / 2;
            if rng.0 < m {
                self.update_core(rng, (first, mid, n*2+1))
            }
            if m < rng.1 {
                self.update_core(rng, (mid, last, n*2+2))
            }
            self.v[n] = add_node(self.v[n*2+1], self.v[n*2+2])
        }
    }
    
    fn count(&self, rng: &Range) -> i32 {
        self.count_core(rng, (0, self.n, 0))
    }
    
    fn count_core(&self, rng: &Range, (first, last, n): NodeRange) -> i32 {
        let f = self.v[n].0;
        let l = self.v[n].1;
        if self.v[n].2 == l - f {
            min(l, rng.1) - max(f, rng.0)
        }
        else if rng.0 <= f && l <= rng.1 {
            self.v[n].2
        }
        else {
            let m = self.v[n*2+1].1;
            let mid = (first + last) / 2;
            let mut s: i32 = 0;
            if rng.0 < m {
                s += self.count_core(rng, (first, mid, n*2+1))
            }
            if m < rng.1 {
                s += self.count_core(rng, (mid, last, n*2+2))
            }
            s
        }
    }
}


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

fn read_input() -> (i32, usize) {
    let v: Vec<i32> = read_vec();
    let (N, Q) = (v[0], v[1] as usize);
    (N, Q)
}

fn read_range() -> Range {
    let v: Vec<i32> = read_vec();
    let (L, R) = (v[0], v[1]);
    (L-1, R)
}

fn collect_end_points(ranges: &Vec<Range>) -> Vec<i32> {
    let mut s: BTreeSet<i32> = BTreeSet::new();
    for &(first, last) in ranges.iter() {
        s.insert(first);
        s.insert(last);
    }
    let mut v: Vec<i32> = s.into_iter().collect();
    v.sort();
    v
}

fn F(N: i32, Q: usize) {
    let mut s = N;
    let ranges: Vec<Range> = (0..Q).map(|_| read_range()).collect();
    let pts = collect_end_points(&ranges);
    let mut tree = SegmentTree::new(&pts);
    for range in ranges {
        let n1 = tree.count(&range);
        tree.update(&range);
        let n2 = range.1 - range.0;
        s -= n2 - n1;
        println!("{}", s)
    }
}

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