(略解です。正式な解説は後日公開されます。)

区間を \((L_i, R_i)\) 昇順にソートする。そして次の DP を考える：

• \(dp[n][r][k]\) : \(n\) 個目の区間まで見て、選択した区間に占められた領域の右端が \(r\) で、占められた区間の長さが \(k\)

これで 3 乗オーダーで解けているが、in-place に DP しても空間が 2 乗オーダーかかり MLE する。

そこで DP が多項式の積と和で表現できることに注目する。言い換えると、この DP は多項式を陽に係数として持った DP で、答えもまた多項式と考えられる。
そこで DP において「\(x=0,1,\dots,M\) において答えを評価した値」を計算して、得られた答えを多項式補間で戻すことにすると空間計算量を \(2\) 乗から線形に落とせる。また、DP 自体も lazyseg に乗る形になるため \(1\) 回あたりの DP の計算量を \(\mathrm{O}(N \log M)\) に減らせる。

よってこの問題を時間 \(\mathrm{O}(MN \log M)\) 空間 \(\mathrm{O}(M)\) で解くことが出来る。

なお、包除原理を用いた解法もあるらしい。