Count Binary Sequence

条件の正規化

---

この問題の制約について、以下の3つの性質が成り立ちます。

①$L_i$が同一で$R_i$のみが異なる条件が複数ある場合、最も$R_i$が小さい条件のみを考慮すれば他の条件は考慮する必要はありません。

（最も$R_i$が小さい条件のみを考慮すれば、他の条件は自動的に満たされます。）

したがって各$L_i$について最も$R_i$が小さい条件のみを残すことで、高々$N$個の条件のみを残して他を無視することができます。

②また、2つの条件[$L_i$, $R_i$], [$L_j$, $R_j$] ($i \neq j$)であって$L_i < L_j$、$R_i > R_j$となる条件がある場合、

これらの条件を[$L_i$, $\underline{R_j}$], [$L_j$, $R_j$]と置き換えても良いことも分かります。

③最後に、ある$L$についてそこから始まる制約が一つもない場合ですが、これは$L_i > L$となる全ての制約に渡って$R_i$の最小値を取った値を$R$として、制約$[L, R]$を問題に追加しても構いません。この条件は他の条件が満たされれば自動的に満たされます。

これらの3つの性質から、任意の条件は以下のような$N$個の条件に置き換えることができることが分かります。

[$1$, $R_1$], [$2$, $R_2$], ... [$N$, $R_N$] ($1 \leq R_0 \leq R_1 \leq \cdots \leq R_N \leq N+1$)

（ただし、$R_i=N+1$となる条件は任意の数列について常に満たされているとみなします。）

これを数列$R =$[$R_0$, $R_1$, ..., $R_N$]と同一視します。

$R$の計算は愚直に行って$O(M+N)$で可能です。

DP

---

以下のDPを考えます。

$dp[i]=$（長さ$i$の01列で、全ての条件を満たすものの個数）

長さ$i$の数列が与えられたとき、その末尾に$0$もしくは$1$のうち

現在数列の末尾ではない方の数字を高々$R_i - i + 1$個付け加えた数列も

全ての条件を満たしているため、

配るDPとして$dp[i]$からの遷移は以下のように書くことができます。

$dp[j] = dp[j] + dp[i]$ $(i+1 \leq j \leq R_i)$

計算量はO($M + N^2$)です。

累積和等を用いてDPの遷移をO($1$)にすることで、この問題をO($N+M$)でも解くことができます。