AtCoder Beginner Contest 260 E問題 At Least One解説

問題

$N$個の整数の組 $(A_1,B_1), (A_2,B_2),..., (A_N,B_N)$ の$A_i$か$B_i$の少なくとも片方を含むような連続部分列を考えます。
考えられる連続部分列の長さをそれぞれ出力する問題。

観察

最初の例の場合で観察します。

• $N = 3$
• $M = 5$
• $(A_i, B_i) = (1,3), (1,4), (2,5)$

良い数列を列挙したものは以下のようになります。

• $(1,2)$
• $(1,2,3)$
• $(1,2,3,4)$
• $(1,2,3,4,5)$
• $(2,3,4)$
• $(2,3,4,5)$
• $(3,4,5)$

ここで、連続部分列の先頭の数字を$L$とおきます。
よく観察すると以下の点に気づくことができます。

気付き1

観察から、各$L$に対して数$R$が存在し、
$R$以降$M$を最後尾とする連続部分列が$S$になるということができそうです。
上記の例の場合だと $(L_i,R_i) = (1,2), (2,4), (3,5)$です。

今回は$(A,B)$のうち少なくとも片方選べばよいので、確かに成り立ちます。
(連続部分列を伸ばしても選ぶ数字は増えることはあっても減ることはないので)

気付き2

$L$の最大値は$B$の最小値になっています。
全ての$B$を含んでいれば題意の条件を満たすので、$L$が$B$の最小値の場合はギリギリ成立します。

ただ、それよりも1大きくなってしまうと、
$(A,B)$のどちらも選ばれない組が出てしまうために成立しません。

気付き3

$L$が1のとき、$R$は$A$の最大値となっています。
これも気付き2と似ていますが、全ての$A$を含んでいれば題意の条件を満たすので、$R$が$A$の最大値の場合はギリギリ成立します。

ただ、それよりも1大きくなってしまうと、
$(A,B)$のどちらも選ばれない組が出てしまうために成立しません。

気付き4

$L$が $j$ から $j+1$ に遷移するとき、$R$は $A_i = j$ を満たす $i$ のうち、 $MAX(B_i)$に遷移する。
もともと$A_i$を選択していたので、必ず$B_i$を選択しなければなりません。

なので、$B_i$のうちの最大値を$R$とすることで引き続き題意の条件を満たすことができます。

まとめ

上記の気付きといもす法を使うことで答えをだすことができます。

• $A$のとりうる値 - $B$の最大値を管理しておく(*)
• $L$を0から$B$の最小値まで探索
• $R$の初期値は$A$の最大値、遷移は(*)の値の方が大きければ更新する
• $L$と$R$の値を使っていもす法でそれぞれの長さを更新して求める

通常の尺取り法と比べて、不要な遷移を行わない分たいがいの場合はより高速に動作します。
アルゴリズムもシンプルなので実装量も比較的少なくなってると思います。

回答

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

#[fastout]
fn main() {
    input! {
        n:usize,m:usize,
        ab:[(Usize1,Usize1);n],
    }
    let mut ans = vec![0; m + 1];
    let mut least = vec![0; m];
    let mut maxa = 0;
    let mut minb = m;
    for (a, b) in ab {
        maxa = maxa.max(a);
        minb = minb.min(b);
        least[a] = least[a].max(b);
    }
    let mut r = maxa;
    for l in 0..=minb {
        ans[r - l] += 1;
        ans[m - l] -= 1;
        r = r.max(least[l]);
    }
    for i in 1..=m {
        ans[i] += ans[i - 1];
    }
    ans.remove(m);
    println!("{}", ans.iter().join(" "));
}