[BJWC2018] 序列合并-526互联

朴素的 \(O(n^4)\) 是容易的，考虑如何优化，通过一些观察可以发现 \(\texttt{dp}\) 不具有凸性和决策单调性，所以只能用普通的矩阵乘法来优化，我们令 \(\texttt{dp}\) 数组构成的矩阵为 \(A\)，那么 \(dp_{l,r}\) 则可以从所有 \(L\leqslant x \leqslant R\) 的 \(A^x\) 转移而来，我们采用类似快速幂的方法实现这个事情，记 \(B_{k}=A^{\lfloor\frac{l}{2^k}\rfloor},C_{k}=min_{i=0}^{\lfloor\frac{r-l}{2^k}\rfloor}A^i\)，注意到事先这些矩阵我们都是不知道的，所以我们可以采用一个半在线矩乘的东西，按长度从小到大考虑每一个区间，每次转移时枚举分界点，由于前面的区间已经求出，所以转移时可以直接调用，由于 \(A^0\) 是难以定义的，所以需要一定的特殊处理，于是可以做到 \(O(n^3 log n)\)。