概要
解法
区間 $[L_i, R_i)$ が $M$ 個与えられて、それぞれ選ぶ・選ばないで $2^M$ 通りの選択肢があります。すべての点が $2$ 枚以上の区間に被覆されるような選び方を数え上げる問題です。
区間を $L$ 昇順でソートしておいて、その順に区間を置くかどうか決めていくことを考えます。
区間 $[L,R)$ を置く時点では、$[0,L)$ 部分が $2$ 枚以上の区間に覆われている必要があります。その条件のもと、区間 $[L,R)$ を置いた直後の状態は、ある $a, b$ に対して
- $[0,a)$ 部分は $2$ 枚以上に覆われている
- $[a,b)$ 部分はちょうど $1$ 枚に覆われている
- $[b,N)$ 部分はちょうど $0$ 枚に覆われている
が成り立ちます。実際、$x<L$ の部分は $2$ 枚以上で覆われてということでした。これまで置いた区間はすべて左端が $L$ 以下であるため、$x\geq L$ 部分の被覆枚数は $x$ について単調減少です。
この状態 $(a,b)$ に対する数え上げを $\dp[a,b]$ として、ひとつずつ区間を置く・置かない場合の遷移を計算していくことにより、本問題は （ソート $O(M\log M)$ 時間を除き）$O(MN^2)$ 時間で解くことができます。
$N$ の制約が大きいですが、はじめに座標圧縮しておくことで、$N = O(M)$ の場合に帰着できます。したがって、座標圧縮後に上述の dp を計算することで、本問題は $O(M^3)$ 時間で解くことができます。
