接上 去年写的题解 ，本题可以将 $O(n^2k)$ 利用斜率优化搞到 $O(nk)$ ，事实上本题还可以结合 wqs二分进一步优化，搞到 $O(n\log V)$ 。将本题的 $n,k$ 都提升到 $3\times 10^5$ 一样可以做。可以到 这里 挑战该数据梯度的数据。

形象化地来说，这三种做法类似于 邮局 , 邮局 加强版 , 邮局 加强版 加强版 的关系。利用区间拆分模型+指定拆分个数+四边形不等式的性质可以做两步优化。

整体思路不用多说，先排序，然后每一段的代价就变成了段内最右侧减去段内最左侧的平方。求解分成至多 $k$ 个连续段时的代价总和最小是多少。显然本题已经满足了“区间拆分+指定拆分个数”了。最后就是证明本题满足四边形不等式。

显然拆出连续的一段 $a_j,…,a_i$ 的代价为 $w(j,i)=a_i^2 - a_j^2$ ，而 DP 方程前面的一项原本的 $dp_{k-1,j-1}$ （前 $j-1$ 个元素划分了 $k-1$ 段）对于四边形不等式性质没有影响（因为会被抵消掉）。不会四边形不等式的建议先看 诗人小G 一题。

所以我们只要证明包含项大于等于交错项即可。

那么 $w(j,i)+w(j+1,i+1)=(a_i-a_j)^2+(a_{i+1}-a_{j+1})^2$ 这是交叉项

然后 $w(j+1,i)+w(j,i+1)=(a_i-a_{j+1})^2+(a_{i+1}-a_j)^2$ 这是包含项

包含减去交叉为

$$ 2(a_{j+1}a_{i+1}+a_ia_j)-2(a_{i+1}a_j+a_ia_{j+1})\\=2a_{j+1}(a_{i+1}-a_i)+2a_j(a_i-a_{i+1})\\=2(a_{i+1}-a_i)(a_{j+1}-a_j)\ge 0 $$

最后一步 $\ge 0$ 是因为对 $a$ 排序之后满足单调性得到的，没有问题，而一旦区间分拆模型满足四边形不等式，其最小代价关于分拆个数的函数也是一个凸函数。所以可以用 wqs 二分。

wqs 二分的大概原理不讲，这里直接讲怎么求划分为至多 $k$ 段的最小值的流程。

• 首先确定下来代价偏移值域的上下界。
• 以偏移值域进行二分，假设每次查看的答案是 $v$ ，我们将每一段划分的代价变为原来 $+v$ ，然后在不考虑划分段数的限制下进行最小值的 DP。DP 之后查看当前决策的划分段数。
• 易知随着 $v$ 的增加，在下凸壳上，得到的划分段数是单调增的
• 我们需要找出的 $v$ 是最小满足在上述做法中，最优决策选择段数 $\le k$ 的最大值 $v_0$，答案为该情况下的最优决策答案减去 $v_0k$ 。

代价 $+v$ 就是每一段的代价从 $a_i^2-a_j^2$ 变成了 $a_i^2-a_j^2+v$ 。我们指定了搜索的答案之后，以这个代价做不考虑段数限制的最小 DP

设 $f_i$ 为前 $i$ 个人在此种限制条件下的最小划分代价，显然有 $f_i=\min\limits_{0\le j<i}f_j+(a_i-a_{j+1})^2+v$ 。

看到平方项，一眼斜率优化。$f_i=f_j+a_i^2-2a_ia_{j+1}+a_{j+1}^2+v$ 。

所以转成以 $j$ 相关的为横坐标和纵坐标，$i$ 相关的为斜率和截距，有： $f_j+a_{j+1}^2=(-a_i^2+f_i)+2a_ia_{j+1}-v$

然后把 $a_{j+1}$ 当做横坐标 $2a_i$ 当做查询斜率，$f_j+a_{j+1}^2$ 当做纵坐标（由于 $v$ 这一项在计算两点斜率的时候会被抵消，所以不用管），截距最小对应 $a_i$ 最小。插入横坐标单调递增，查询斜率单调递增，所以可以 $O(n)$ 单调队列解决。

所以整个算法流程就是外层对代价的值域偏移做二分答案，内层用单调队列做斜率优化DP。假设我们的值域区间是 $V$ ，那么整个算法的复杂度就是 $O(n\log V)$ 的。

代码

const int N = 300010;
i64 n, k;
i64 a[N];
i64 dp[N];
int opt[N];
i64 X(int idx) { return a[idx + 1]; }
i64 Y(int idx) { return dp[idx] + a[idx + 1] * a[idx + 1]; }
// > k return 1, == k return 0, < k return -1
int judge_slope_real(int i, int j, i64 k)
{
    i64 flag = (Y(j) - Y(i)) - k * (X(j) - X(i));
    return flag > 0 ? 1 : flag == 0 ? 0 : -1;
}
// judge slope(i, j) slope(i, k)
int judge_slope_index(int i, int j, int k)
{
    i64 flag = (Y(j) - Y(i)) * (X(k) - X(i)) - (Y(k) - Y(i)) * (X(j) - X(i));
    return flag > 0 ? 1 : flag == 0 ? 0 : -1;
}
struct monotone_queue_convex
{
    int flag; // flag = -1 : down, flag = 1 : up
    std::deque<int> q;
    monotone_queue_convex(int _flag = -1) : flag(_flag) {}
    void pop_back_by_slope(i64 k)
    {
        while (q.size() >= 2 && judge_slope_real(q.back(), q[q.size() - 2], k) * flag >= 0)
            q.pop_back();
    }
    void push_front_by_convex(int x)
    {
        while (q.size() >= 2 && judge_slope_index(q[1], q.front(), x) * flag <= 0)
            q.pop_front();
        q.push_front(x);
    }
};
void clr() { memset(dp, 0, (n + 1) << 3), memset(opt, 0, (n + 1) << 2); }
std::pair<i64, int> solve(i64 v)
{

    monotone_queue_convex slope_queue(-1);
    slope_queue.push_front_by_convex(0), clr();
    for (int i = 1; i <= n; ++i)
    {
        slope_queue.pop_back_by_slope(a[i] << 1);
        opt[i] = slope_queue.q.back();
        dp[i] = dp[opt[i]] + (a[i] - a[opt[i] + 1]) * (a[i] - a[opt[i] + 1]) + v;
        slope_queue.push_front_by_convex(i);
    }
    int seg = 0, cur = n;
    while (cur) ++seg, cur = opt[cur];
    return std::make_pair(dp[n], seg);
}
int main()
{
    n = rd(), k = rd();
    for (int i = 1; i <= n; ++i)
        a[i] = rd();
    std::sort(a + 1, a + n + 1);
    i64 lo = 0, hi = 1145141919, mi = 0;
    while (lo < hi)
    {
        mi = (lo + hi) >> 1;
        (solve(mi).second >= k) ? (lo = mi + 1) : (hi = mi);
    }
    wr(solve(lo - 1).first - k * (lo - 1));
}