問題

解法

mark がひとつもないとき（つまりすべてのクエリが全体クエリのとき）は特別で、答えは $(0, q)$ となりますが、そうでないときを考えましょう。

区間 $[l, r[$ に対するクエリが来るたびに、$[l - 1, l + 1[$ を含む節点全てに mark し、また $[r - 1, r + 1[$ を含む節点全てにも mark することにします。このとき mark の深さの最大値を $d$、深さ $d$ の mark の個数の最小値を $c$ とおくと、答えは $(1 + d, 2c)$ の最小値です。ただしペアの辞書式順序で比較するします。

なお mark がひとつもないときも形式的に $(d, c) = (-\infty, 0)$ とみなすことにします。（もちろん答えは合いませんが、後の議論上都合が良くなります。）

DP で表す

区間 $[l, r[$ に対応する部分木について、答えが $(d, c)$ であるとき $\mathrm{dp}(l, r) = c x ^ d + o(x ^ d)$ と定義します。ただし仕切りがひとつもないときには $\mathrm{dp}(l, r) = 0$ であるとみなします。

$\mathrm{dp}(l, r)$ を区間 DP で計算しましょう。$r - l = 1$ のときには当然 $0$ です。$1 < r - l$ のときは$[l, r[$ の内部の仕切りの個数を $w(l, r)$ とおくと、

$$ \mathrm{dp}(l, r) = x \cdot \min _ { l < i < r } \left ( \mathrm{dp}(l, i) + \mathrm{dp}(i, r) \right ) + w(l, r) $$

（ただし多項式同士の順序は、$x \gg 1$ で定める）と表せます。

Knuth–Yao speedup

このように定めた多項式同士の加法と順序は $a < b ⇒ a + c < b + c$ を満たす（つまり順序群をなす）ことと、$w(l, r)$ が Monge かつ包含関係について単調であること、Monge 関数に定数を掛けても Monge であるから、Knuth–Yao speedup の議論がすべて通ります。

実装

ペア $(d, c)$ を (usize, usize) で管理すればよいです。零多項式は $(-\infty, 0)$ に対応しますが、(0, 0) などで代用して場合分けで処理しても良いと思います。

提出

Rust 761 ms

use itertools::Itertools;
use proconio::{input, marker::Usize1};

fn main() {
    input! {
        n: usize,
        q: usize,
        queries: [(Usize1, usize); q],
    }
    let mut w = vec![vec![0; n + 1]; n + 1];
    for &(l, r) in &queries {
        if l != 0 {
            w[l - 1][l + 1] += 1;
        }
        if r != n {
            w[r - 1][r + 1] += 1;
        }
    }
    for (l, r) in (0..=n).tuple_combinations() {
        w[l][r] += w[l][r - 1];
    }
    for (r, l) in (0..=n).rev().tuple_combinations() {
        w[l][r] += w[l + 1][r];
    }
    let mut argmin = vec![vec![usize::MAX; n + 1]; n + 1];
    let mut dp = vec![vec![(0, 0); n + 1]; n + 1];
    for len in 2..=n {
        for (l, r) in (0..).zip(len..=n) {
            let (start, end) =
                if len == 2 { (l + 1, r - 1) } else { (argmin[l][r - 1], argmin[l + 1][r]) };
            let ((d, c), a) = (start..=end)
                .map(|i| {
                    let (d0, c0) = dp[l][i];
                    let (d1, c1) = dp[i][r];
                    let c = (if d0 >= d1 { c0 } else { 0 }) + (if d0 <= d1 { c1 } else { 0 });
                    let d = if c == 0 { 0 } else { d0.max(d1) + 1 };
                    ((d, c), i)
                })
                .min()
                .unwrap();
            argmin[l][r] = a;
            dp[l][r] = if c == 0 { (0, w[l][r]) } else { (d, c) };
        }
    }
    let (d, c) = dp[0][n];
    let (d, c) = if c == 0 { (0, q) } else { (1 + d, 2 * c) };
    println!("{d} {c}");
}