題目描述

傳送門

題解

n2k$n^2k$的dp是比較好想好寫的 f(i,j,0/1)表示劃分了i段，以第j個結尾，最后一段是上升0/下降1的方案數 f(i,j,0)=∑k=i+1j?1∑y(k)<y(j)f(i,k,0)+∑k=i+1j?1∑y(k)>y(j)f(i?1,k,1)$f(i,j,0)=/sum/limits_{k=i+1}^{j-1}/sum/limits_{y(k)<y(j)}f(i,k,0)+/sum/limits_{k=i+1}^{j-1}/sum/limits_{y(k)>y(j)}f(i-1,k,1)$ f(i,j,1)=∑k=i+1j?1∑y(k)<y(j)f(i?1,k,0)+∑k=i+1j?1∑y(k)>y(j)f(i,k,1)$f(i,j,1)=/sum/limits_{k=i+1}^{j-1}/sum/limits_{y(k)<y(j)}f(i-1,k,0)+/sum/limits_{k=i+1}^{j-1}/sum/limits_{y(k)>y(j)}f(i,k,1)$ 兩個限制條件，第一個邊做邊維護，第二個用bit維護前綴和，01分開維護，滾動數組 然后就是O(nlogn)$O(nlogn)$了

代碼