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

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[i][j]=Min_{p<i}(dp[p][j-1]+w(p+1,i))
\]

答案即为 \(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]+w\le 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];

}

巴特西

【BZOJ 5125】小Q的书架