提供一種不一樣的狀態設計。

將所有區間按右端點排序后，設 \(dp_{i,j,k}\) 表示前 \(i\) 個區間中，選出的右端點最靠右的顏色為 \(k\) 的區間，其右端點位于 \(j\) 的方案數。

如果不選第 \(i\) 個區間，\(dp_{i-1,j,k}\) 對 \(dp_{i,j,k}\) 作貢獻。

如果選第 \(i\) 個區間：

對于 \(k \not= c_i,j<l_i\)，也就是不與任何異色區間相交的情況，\(dp_{i-1,j,k}\) 同樣對 \(dp_{i,j,k}\) 作貢獻。

對于 \(k = c_i\)，右端點最靠右的顏色為 \(k\) 的區間必定為區間 \(i\)，故對于任意 \(j<l_i\)，\(dp_{i-1,j,k \operatorname{xor}1}\) 對 \(dp_{i,r_i,k}\) 作貢獻。

整理可得：

特別地，

滾動數組后，操作就變為了區間乘 \(2\)，單點加，區間求和，兩種顏色分別建一棵線段樹來維護即可。

代碼