部分点解法

\(dp[i]:= a[1:i]\) から作ることのできる数列の数、と定義してDPをすることを考えます。

このとき、\(dp[i]\) の値は、「\(a[{j+1}:i]\) をどこで \(2\) つに分けても、常に（左側部分の \(\max\)）\(\gt\)（常に右側部分の\(\min\)）」となるような \(j\) \((\lt i)\) について \(dp[j]\) の合計になります。（区間がこの条件を満たすことを「validである」と呼ぶことにします。）

さて、上記の式に登場する加算される条件について考えます。この区間が \(1\) つ右に伸びる時（ \(a[l:r]\) → \(a[l:r+1]\) ）のことを考えます。

validな区間がinvalidになる

これは、 \(a_{r+1} \gt \max(a_l, a_{l+1}, \cdots, a_r)\) の時に発生します。

invalidな区間がvalidになる

これは、 （左側部分の \(\max\)）\(\lt\)（常に右側部分の\(\min\)） となるような切り方のうち最も左側のものについて、（左側部分の \(\max\)）\(\gt\) \(a_{r+1}\) の場合に発生します。

よって、\(dp[i]\) の値を計算しようとするとき、validな区間に対しては区間の \(\max\) 、invalidな区間に対しては上記の（左側部分の \(\max\)）を管理すれば良いです。

ここまでの議論で、 \(O(N^2)\) の解法を実装可能で、部分点を獲得できます。

満点解法

それぞれの区間に \(a_i\) を右端に追加する時、

• validな区間が、\(a_i\) 以下の値を持っている場合、invalidにする
• invalidな区間が、\(a_i\) 以上の値を持っている場合、validにして、持っている値を区間中の \(\max\) に更新する。

の \(2\) 種類の操作を実現する必要があります。

DPの値を管理するために、\(seg[i]\) := 値 \(i\) を持つ区間により遷移するDPの値の合計、と定義します。

\(1\) つ目の操作は簡単で、valid/invalidの境界線を単に移動させれば良いです。 \(2\) つ目の操作は、境界線を移動させて、その最中に交差した \(seg\) 中の値それぞれに対して、適切な場所（区間の最大値）に移動させる、という操作が必要になります。

\(2\) つ目の操作の「移動させる」操作は、全体で \(O(N)\) 回しか登場しないため、setやmapなどを用いて値を管理することで間に合います。

よって、\(O(N \log N)\) でこの問題を解くことができました。