題意：給定序列，把序列分成 \(k\) 段，使每一段相同元素對數之和最小。\(n\le 10^5,k\le 20,a_i\le n\)。

容易寫出轉移方程：\(dp[i][j]=\min_{k=1}^{i}(dp[k-1][j-1]+w(k,i))\)，其中 \(w(k,i)\) 表示 \(a_k\sim a_i\) 的相同元素對數。

第一想法是 wqs 二分，然后發(fā)現 \(w(k,i)\) 實在太惡心了，既沒辦法拆貢獻也沒辦法快速計算。

其次考慮四邊形不等式優(yōu)化。\(w(l,r)\) 滿足四邊形不等式的性質比較顯然。

然后考慮到二分隊列。遇到了同樣的問題：\(w(l,r)\) 沒辦法快速計算，也就沒辦法快速比較段首和 \(i\) 的決策孰優(yōu)孰劣。

思路卡住了。于是這里有一個新的技巧：類莫隊在分治過程中維護 \(w\)。

考慮用分治的方法做，即枚舉 \(d=1\sim k\)，每一次把 \(dp[?][d]\) 求出來。

設當前到 \(slv(l,r,posl,posr)\)，表示求 \(dp[l\sim r][d]\)，這一段的最優(yōu)決策點在 \([posl,posr]\) 里。

按照一般的流程，接下來我們會取 \(m=(l+r)/2\)，然后枚舉 \(j=posl\sim m\)，找到 \(dp[j-1][d-1]+w(j,m)\) 最小的 \(j\)，令 \(dp[m][d]=dp[j-1][d-1]+w(j,m)\) 然后分治計算 \(slv(l,m-1,posl,j)\) 和 \(slv(m+1,r,j,posr)\)。

再次遇到了一樣的問題：\(w(j,m)\) 難以計算！！！

但是這里我們有解決辦法。我們考慮開全局變量 \(l,r,cnt[],sum\) 記錄當前記錄了區(qū)間 \([l,r]\) 的 \(cnt\) 數組和 \(w\)。類似莫隊。在我們詢問 \(w(j,m)\) 時，直接暴力挪動左右端點獲取答案。

正確性顯然，問題是復雜度怎么是對的。

從上一層 \([L,R]\) 的最后一次計算轉移到本層 \([L,M]\) 的第一次計算，復雜度是 \(O(posR-posL)\) 的。站在 \([L,R]\) 的角度看，無論 \(slv(L,M),slv(M,R)\) 干了什么事，它轉移到下一層的工作最多是 \(O(posR-posL)\) 次移動端點：把當前層端點移動到 \(slv(L,M)\) 所需的位置是 \(R-L\) 次，再移動到 \(slv(M,R)\) 位置也是 \(R-L\) 次。

而在一層內部，移動次數總共是 \(O(n)\) 的。因為一層內的 \([posl,posr]\) 是不相交的。

所以總復雜度是 \(O(n\log n)\)。