Problem
Description
小 (Q) 有 (n) 本书，每本书有一个独一无二的编号，现在它们正零乱地在地上排成了一排。
小 (Q) 希望把这一排书分成恰好 (k) 段，使得每段至少有一本书，然后把每段按照现在的顺序依次放到 (k) 层书架的每一层上去。
将所有书都放到书架上后，小 (Q) 这才突然意识到它们是乱序的，他只好把每一层的书分别按照编号从小到大排序。排序每次可以在 (1) 单位时间内交换同一层上两本相邻的书。
请写一个程序，帮助小 (Q) 计算如何划分这 (k) 段，且如何交换这些书，使得总交换次数最少。
Input Format
第一行包含两个正整数 (n,k)。
第二行包含 (n) 个互不相同的正整数 (a_1, a_2, ..., a_n)，分别表示地面上每本书的编号。
Output Format
输出一行一个整数，即最少的总交换次数。
Sample
Input
6 3
4 3 6 2 5 1
Output
1
Explanation
Explanation for Input
按 ([4, 3, 6][2, 5][1]) 划分，需要排序 (1 + 0 + 0 = 1) 次。
Range
(1 le n le 40000, 1 le k le min(10, n), forall 1 le a_i le n)
Algorithm
(DP) ，决策单调性
Mentality
其实决策单调性也没啥可怕的地方，主要重点在于你的思考！
我们先列出最朴素的 (dp) 方程：(dp[i][j]) 表示将前 (i) 本书划分到 (j) 层书架的最小代价，那么我们设 (w(i,j)) 代表区间 ([i,j]) 内的逆序对数目，我们就有如下方程：
答案即为 (dp[n][k]) 。
这样 (dp) 的复杂度为 (n^2k) ， 时间显然过不去。
那么由于式子非常决策单调性，那么我们考虑打表证明，果然有 (w) 函数满足四边形不等式。
随后当我们枚举一个 (j) 时，我们设 (g[i]) 为 (dp[i][j]) 的最优决策点，即 (dp[i][j]=dp[g[i]][j-1]+w(g[i]+1,i))，则有 (g[i-1]le g[i]) 。
这个证明很简单，对于两个决策点 (p<q) ，如果 (dp[q]+wle dp[p]+w) ，由于 (w) 函数越来越大，所以如果 (q) 比 (p) 更优，那么 (q) 永远比 (p) 更优。所以我们的最优决策点必定单调右移，即 (g[i-1]le g[i]) 。
那么根据这个单调性搞事情，我们考虑分治 (dp) ，对于区间 ([l,r]) 的 (dp) ，我们考虑确定它的最优决策点所在的区间 ([L,R]) 。那么我们找出 (mid) 处的最优决策点 (p)，根据决策单调性，则区间 ([mid+1,r]) 的最优决策区间必定为 ([p,R]) ，而区间 ([l,mid-1]) 的最优决策区间则必定为 ([L,p]) 。
根据这样递归分治，每次枚举最优决策区间更新 (mid) ，并递归处理，枚举决策区间便构成了一颗类似线段树的情况，那么对于同一递归层数，决策区间的和正好就是 (O(n)) ，那么决策区间枚举的总复杂度就是 (nlog) ，均摊下来，则我们枚举决策点的复杂度变为 (log) ，枚举状态复杂度为 (O(nk)) 。
样例的递归分治，当 (k=2) 时如下图：
由此可见，每层的决策点枚举只会是 (O(n)) ，那么总复杂度为 层数× (n) ，即 (O(nlog)) 。
接下来还剩一个状态转移，那么我们只需要管 (w) 函数如何快速地求出来就好了。这里我们先看我们的处理顺序为先递归左区间再递归右区间，那么大多数时候 (w) 的右端点只是根据 (dp) 需求不断增加 (1) ，递归下去的时候也只是减少一些。
则我们可以考虑维护一个类似莫队的东西，维护一个全局的 (L) 与 (R) ，每次需要获取答案的时候，我们就将 (L) 和 (R) 一步一步移动到指定位置，用树状数组动态维护逆序对即可。这样做的话大概总复杂度是 (nlog) 带个玄学常数？那么均摊下来就是 (log) 的复杂度。
则最后的时间复杂度=枚举状态×枚举决策点×状态转移=(O(nk)×O(log)×O(log))=(O(nklog^2)) 。能够通过题目。
Code
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
int n, K, sum, L, R, now, a[40001], c[40001], f[40001][11];
void add(int k, int x) {
for (int i = k; i <= n; i += i & -i) c[i] += x;
}
int query(int x) {
int ans = 0;
for (int i = x; i > 0; i -= i & -i) ans += c[i];
return ans;
}
void Move(int l, int r) //莫队式移动
{
while (L < l) sum -= query(a[L] - 1), add(a[L++], -1);
while (L > l) sum += query(a[L - 1] - 1), add(a[--L], 1);
while (R < r) sum += R - L + 1 - query(a[R + 1]), add(a[++R], 1);
while (R > r) sum -= R - L + 1 - query(a[R]), add(a[R--], -1);
}
void solve(int l, int r, int L, int R) {
if (l > r) return;
int mid = (l + r) >> 1, p = L;
for (int i = L; i <= min(mid - 1, R); i++) {
Move(i + 1, mid);
int Sum = f[i][now - 1] + sum;
if (Sum < f[mid][now]) f[mid][now] = Sum, p = i; //确定最优决策点
}
solve(l, mid - 1, L, p);
solve(mid + 1, r, p, R); //递归
}
int main() {
cin >> n >> K;
L = 1; //初始化莫队指针
for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
memset(f, 10, sizeof(f));
for (int i = 1; i <= n; i++) Move(1, i), f[i][1] = sum; //先计算 k=1
for (now = 2; now <= K; now++) solve(1, n, 1, n); //开始递归
cout << f[n][K];
}