下面是这道题的中文翻译。(statement_5507.pdf)

I. 投资者（Investors）

输入： 标准输入
输出： 标准输出
时间限制： 8 秒
内存限制： 1024 MB

题目描述

时间来到 2087 年。人工智能甚至已经解决了那些从未被提出过的超图染色问题，而已经建成的 Hyperloop 网络却成了世界上最慢的地铁。

在题目 H 中开发的软件已经完美运行了 10 年，但和往常一样，计划中最薄弱的环节还是社会学因素：每当系统给出的 Hyperloop 路线包含尽可能长的连接时，乘客看到行程安排后血压都会升得非常高，以至于他们甚至不再需要购买 Melon 公司那些价格高得离谱的咖啡。

为了安抚投资者，Usk 决定展示公司的财务业绩。不幸的是，由于车票收入过低、咖啡采购成本过高，公司的财务数据并不好看。于是，这位古怪的亿万富翁决定稍微“调整”一下数据。(statement_5507.pdf)

公司的业绩可以表示成一个长度为 $n$ 的数列，其中每个数代表连续各个月份的收入。

为了不引起怀疑，Usk 决定进行如下操作：

• 选择数列中的一个连续区间；
• 将该区间中的所有数都增加某个正整数。

做一次操作还不能满足这位梦想家，于是他又做了第二次、第三次……最终，他决定最多进行 $k$ 次这样的增加操作，每次增加的数值可以不同。(statement_5507.pdf)

Usk 知道，投资者最关注的是公司收入的增长，并且不喜欢看到收入比之前取得的水平下降。

因此，他希望在执行至多 $k$ 次操作之后，使财务数据序列中的逆序对数量最少。

你能拯救他的公司未来吗？(statement_5507.pdf)

输入格式

第一行包含测试用例数量 $z$：

$$1 \le z \le 400$$

接下来是每个测试用例的描述。

每个测试用例的第一行包含两个整数 $n,k$：

$$1 \le n \le 6000,\qquad 0 \le k \le n$$

第二行包含一个长度为 $n$ 的序列：

$$a_1,a_2,\ldots,a_n$$

其中：

$$0 \le a_i \le 10^9$$

表示 Melon 公司各个月份的财务收入。

所有测试用例中的 $n$ 之和不超过 6000。(statement_5507.pdf)

输出格式

对于每个测试用例，输出一个整数：

在进行不超过 $k$ 次“将一个连续区间整体增加某个正整数”的操作后，序列能够达到的最小逆序对数量。 (statement_5507.pdf)

样例

输入

text
2
6 1
4 5 6 2 2 1
6 2
4 5 6 2 2 1

输出

text
2
0

逆序对定义

对于序列

$$a_1,a_2,\ldots,a_n$$

如果一对下标 $i,j$ 满足：

$$i<j,\qquad a_i>a_j$$

那么 $(i,j)$ 就称为一个逆序对。(statement_5507.pdf)

这题最关键的不是 DP，而是先把“区间加”看成“切段”。

题目允许最多 $k$ 次操作，每次选择一个连续区间并整体加上某个正整数；目标是让最终序列的逆序对尽量少。(statement_5507.pdf) 逆序对指 $i<j$ 且前面的数严格大于后面的数。(statement_5507.pdf)

1. 最重要的观察：操作一定可以改成“加一个后缀”

假设某次操作是：

text
给 [l, r] 全部 +x

我们把它改成：

text
给 [l, n] 全部 +x

逆序对数一定不会变多。

原因只需要看原来没有加的 r+1 ... n。

对于一个位置 j > r：

如果前面的位置也在 [l,r]，那么原操作只把前面的数增大，这反而可能制造逆序对；改成后缀以后，前后两个数一起加，二者大小关系不变。

如果前面的位置在 l 左边，那么改成后缀只会把后面的数增大，这只可能消灭逆序对，不可能制造逆序对。

如果两个位置都在 r 后面，则一起加，关系仍然不变。

所以：

任意一种方案，都可以改成“每次只给某个后缀加数”，而答案不会更差。

这是整道题最核心的一步。

---

2. 后缀加等价于“把数组切成若干段”

例如我们进行了两次操作：

text
[l1, n] +x
[l2, n] +y

假设 l1 < l2。

那么数组会变成：

text
第一段：原值
第二段：原值 + x
第三段：原值 + x + y

也就是说，相邻两次后缀操作的起点，就是“分段位置”。

最多 $k$ 次操作，因此最多可以把数组切成：

$$k+1$$

段。

而且我们可以把 x, y, ... 取得任意大。

所以对于相邻两段，我们完全可以让：

text
后一段的所有数 >= 前面所有段的所有数

这样，不同段之间就一个逆序对都没有。

因此最终还可能存在的逆序对，只有：

每一段内部原本就存在的逆序对。

于是原题彻底变成了：

把数组切成至多 $k+1$ 个连续段，让所有段内部的逆序对数之和最小。

这已经和“区间加多少”完全没关系了。

---

3. 样例为什么是 2 和 0

数组：

text
4 5 6 2 2 1

k = 1

最多切成 2 段。

在这里切：

text
4 5 6 | 2 2 1

左边没有逆序对。

右边：

text
2 2 1

两个 2 都和 1 构成逆序对，所以有 2 个。

于是答案是：

text
2

实际操作也很好构造，比如给后三个数整体 +5：

text
4 5 6 7 7 6

现在只剩最后这一段内部的两个逆序对。

k = 2

可以切成：

text
4 5 6 | 2 2 | 1

三段内部全都没有逆序对，所以答案是：

text
0

比如：

text
4 5 6 2 2 1
      +5 +5 +5
           再 +2

得到：

text
4 5 6 7 7 8

完全没有逆序对。

---

4. 于是自然想到区间 DP

定义：

text
cost[l][r]

表示原数组中：

text
a[l ... r]

内部有多少个逆序对。

然后做分段 DP。

我们只保留一个一维数组：

text
dp[r]

表示：

当前已经用了固定数量的段，把前 r 个数切完时的最少逆序对。

假设现在准备添加最后一段，并且最后一段是：

text
p+1 ... r

那么：

text
前 p 个数的答案 + 最后一段内部的逆序对

也就是：

$$dp[p]+cost[p+1][r]$$

枚举最后一个切点 p：

$$next[r]=\min(dp[p]+cost[p+1][r])$$

这就是完整 DP。

---

5. 先用 $O(n^2)$ 算出所有 cost

这里有一个很简单的写法，不需要树状数组。

假设已经知道：

text
cost[l][r-1]

现在把 a[r] 放进来。

新产生的逆序对就是：

text
a[l ... r-1] 中比 a[r] 大的数的个数

固定 r，让 l 从右往左走，就可以顺手维护这个数量：

cpp
for (int r = 1; r <= n; r++) {
    int bigger = 0;

    for (int l = r - 1; l >= 1; l--) {
        if (a[l] > a[r]) {
            bigger++;
        }

        cost[l][r] = cost[l][r - 1] + bigger;
    }
}

例如：

text
4 5 6 2

加入最后的 2 时，从右向左看：

text
6 > 2
5 > 2
4 > 2

所以随着左端点不断向左，新增的逆序对依次是：

text
1, 2, 3

整个预处理只要：

$$O(n^2)$$

---

6. 但是普通 DP 会超时

转移是：

cpp
next[r] = min(dp[p] + cost[p + 1][r]);

如果每个状态都暴力枚举 p：

text
段数 × r × p

最坏就是：

$$O(k n^2)$$

而 $n=6000$，肯定不行。

这里需要一个经典的 分治优化 DP。

---

7. 为什么可以分治优化

关键性质是：

当 r 从左往右增加时，使答案最优的切点 p 不会向左移动。

也就是类似：

text
r = 100，最优切点可能是 37
r = 101，最优切点只可能是 37 或更右
r = 102，继续只会往右

不会突然变回 20。

这个性质来自 cost 的特殊结构。

假设有四个位置：

$$x\le y\le z\le w$$

那么有：

$$cost[x][z]+cost[y][w] \le cost[x][w]+cost[y][z]$$

为什么？

把右边减左边，剩下的东西其实就是：

text
左边 x ... y-1

和

text
右边 z+1 ... w

之间的逆序对数量。

它显然不会是负数。

这就是所谓的 Monge 性质。

给每个候选切点再加上一个 dp[p]，不会破坏这个性质，因此最优切点具有单调性。

于是可以使用标准的分治优化。

---

8. 分治优化到底在干什么

假设我们要计算：

text
next[L ... R]

先算中点：

text
mid = (L + R) / 2

假设我们已经知道 mid 的最优切点一定在：

text
optL ... optR

那就直接枚举这个范围，找到 mid 的最优切点：

text
best

由于最优切点单调：

text
L ... mid-1

的最优切点不会超过 best。

所以左半边只需要搜索：

text
optL ... best

而：

text
mid+1 ... R

的最优切点不会小于 best。

所以右半边只需要搜索：

text
best ... optR

代码就是经典模板：

cpp
solve(L, R, optL, optR)

这样一层 DP 不再需要 $O(n^2)$，而是大约：

$$O(n\log n)$$

总复杂度：

$$O(n^2 + kn\log n)$$

最坏可以写成：

$$O(n^2\log n)$$

这里我故意没有使用更复杂的 SMAWK 等优化，因为 $n=6000$，这份分治写法更容易读，已经足够实用。

---

9. 为什么可以直接用恰好 $k+1$ 段

题目说的是“最多 $k$ 次操作”。

但是把一段拆成两段，只会让一些原来属于“段内”的逆序对变成“段间”逆序对。

而段间逆序对可以全部消掉。

所以：

多切一刀永远不会让答案变差。

因此直接使用最多能用的段数：

cpp
min(n, k + 1)

即可。

如果每个数单独一段，显然答案就是 0。

---

10. 完整 C++17

下面这份代码优先考虑可读性，所以直接开了完整的二维 cost 数组。

cpp
#include <bits/stdc++.h>
using namespace std;

const int INF = 1e9;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;

    while (T--) {
        int n, k;
        cin >> n >> k;

        vector<int> a(n + 1);

        for (int i = 1; i <= n; i++) {
            cin >> a[i];
        }

        // cost[l][r]：
        // a[l ... r] 内部的逆序对数量。
        vector<vector<int>> cost(
            n + 2,
            vector<int>(n + 2)
        );

        // O(n^2) 预处理所有区间的逆序对。
        for (int r = 1; r <= n; r++) {
            int bigger = 0;

            for (int l = r - 1; l >= 1; l--) {
                if (a[l] > a[r]) {
                    bigger++;
                }

                cost[l][r] =
                    cost[l][r - 1] + bigger;
            }
        }

        // 最多能切成这么多段。
        int blocks = min(n, k + 1);

        // 一段时：
        // 前 r 个数全部放在同一段。
        vector<int> dp(n + 1, INF);
        vector<int> next(n + 1, INF);

        for (int r = 1; r <= n; r++) {
            dp[r] = cost[1][r];
        }

        // 从 2 段开始逐层计算。
        for (int block = 2; block <= blocks; block++) {
            fill(next.begin(), next.end(), INF);

            // 计算 next[L ... R]，
            // 并且已知最优切点处于 [optL, optR]。
            auto solve = [&](auto&& self,
                             int L,
                             int R,
                             int optL,
                             int optR) -> void {
                if (L > R) {
                    return;
                }

                int mid = (L + R) / 2;

                int bestValue = INF;
                int bestCut = -1;

                // 最后一段是 cut+1 ... mid。
                // cut 必须小于 mid。
                int right = min(mid - 1, optR);

                for (int cut = optL;
                     cut <= right;
                     cut++) {

                    int value =
                        dp[cut]
                        + cost[cut + 1][mid];

                    // 保留最靠左的最优切点，
                    // 方便维持单调性。
                    if (value < bestValue) {
                        bestValue = value;
                        bestCut = cut;
                    }
                }

                next[mid] = bestValue;

                self(
                    self,
                    L,
                    mid - 1,
                    optL,
                    bestCut
                );

                self(
                    self,
                    mid + 1,
                    R,
                    bestCut,
                    optR
                );
            };

            // block 段至少需要 block 个元素。
            // 最后一个切点至少是 block-1。
            solve(
                solve,
                block,
                n,
                block - 1,
                n - 1
            );

            dp.swap(next);
        }

        cout << dp[n] << '\n';
    }

    return 0;
}

---

11. 用一句话记住整题

这题可以压缩成三步：

任意区间加可以改成后缀加 → 后缀加等价于切段 → 最小化各段内部逆序对，用 Monge 分治 DP。

其中真正需要自己想出来的是第一步。一旦发现“区间可以无损延长到数组末尾”，后面的分段 DP 就比较自然了。

还有一个很有用的理解方式：每切一刀，就相当于拥有一次机会，把右边整个部分抬到足够高，因此这条切口两侧的所有逆序对都可以免费消失；我们只需要支付每个块内部仍然存在的逆序对。