整数 \(s, t\ (1\le s \le t \le M)\) について、数列 \((s, \ldots, t)\) を区間 \([s,t]\) と呼ぶことにする。また、\(1\le s\le t\le M\) を満たさないとき、\([s,t]\) は空列を意味するものとする。

長さ \(k\) の良い数列でない区間を数えて、長さ \(k\) の区間の総数 \(M-k+1\) から引くことにする。

区間 \([s,t]\) が良い数列でないとき、すべての \(i\) について \([s,t]\) は \([1, A_i-1], [A_i+1, B_i-1], [B_i+1, M]\) のいずれかの部分列である。よって、高々 \(3N\) 個の区間について、そのいずれかに含まれる区間の数を長さごとに求められればよい。

上で挙げた高々 \(3N\) 個の区間を \([C_1, D_1], \ldots, [C_K, D_K]\) と書く。\([C_i, D_i]\) のうち \(C_i = s\) であるようなものの長さの最大値を \(l_s\) とおけば、\(s\) から始まる区間であって良い数列でないものの長さの最大値 \(L_s\) は漸化式 \(L_s = \max\{l_s, L_{s-1} - 1\}\) を用いて求められる。

\(s\) から始まる区間であって長さ \(L_s\) 以下の数列はすべて良い数列でないから、長さ \(k\) の区間であって良い数列でないものの数は、\(L_s = k\) であるような \(s\) を数えた後に累積和を用いて求めることができる。

実装例 (Rust)

use proconio::{input, marker::Usize1};
fn main() {
    input!(n: usize, m: usize, ab: [(Usize1, Usize1); n]);
    let mut l = vec![0; m];
    for &(a, b) in &ab {
        if a > 0 {
            l[0] = l[0].max(a);
        }
        if a + 1 < b {
            l[a + 1] = l[a + 1].max(b - a - 1);
        }
        if b + 1 < m {
            l[b + 1] = l[b + 1].max(m - b - 1);
        }
    }
    // l を L にする
    for i in 1..m {
        l[i] = (l[i] + 1).max(l[i - 1]) - 1;
    }
    let mut g = vec![0; m];
    for &k in &l {
        if k > 0 {
            g[k - 1] += 1;
        }
    }
    for k in (1..m).rev() {
        g[k - 1] += g[k];
    }
    let f = g
        .iter()
        .enumerate()
        .map(|(i, &g)| m - i - g)
        .map(|f| f.to_string())
        .collect::<Vec<_>>()
        .join(" ");
    println!("{}", f);
}