首先这道题很容易发现如果已经知道了最后的答案序列，那么操作顺序是无所谓的
所以我们可以假设从头操作到尾
由于题目给的是非严格递增序列，我们猜想最后的答案一定是一段一段的，段与段之间单调递增
比如1 1 1 2 2 2 2 2 3 3 4 5 5
反证：如果最终的答案序列存在\(a_{i}\)和\(a_{j}\)，其中\(i＜j\)且\(a_{i}＞a_{j}\)，那我们让\(a_{i}\)变成\(a_{j}\)，\(a_{j}\)变成\(a_{i}\)，则改变后的序列仍然符合题意而且总操作次数不变，所以最终的答案序列没有逆序对
这样就简单了，我们设\(f_{i}\)表示前\(i\)个数字的最小操作次数，考虑最后一个数字最终会变成什么样，由题，每一段的大小是大于等于k的
所以有$$f_{i}=min_{j=k}^{i} (f_{i-j}+\sum_{k=i-j+1}^{i}(a_{k}-a_{i-j+1}))$$
这里运用了一个小贪心：每一段的最开始的数字一定不会变化，变化了肯定没有不变化优
拆开后发现\(i-j\)不好看，为了符合习惯，让\(m=i-j\)
于是有$$s_{m}-f_{m}-m\cdot a_{m+1}=-i\cdot a_{m+1}-f_{i}+s_{i}$$
这里发现斜率是负数，而且绝对值越来越大，不能运用让队头出队，必须要运用二分查找
然而，这个时候我们只需要将原式取反就迎刃而解了：
\[-s_{m}+f_{m}+m\cdot a_{m+1}=i\cdot a_{m+1}+f_{i}-s_{i}
\]
然后就是套模板了
代码有注释，一定要看
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=5e5+10;
int t;
int n,k;
ll a[N],s[N],f[N];
int l,r,q[N];
ll F(int x)
{
return f[x]+x*a[x+1]-s[x];
}
int main()
{
scanf("%d",&t);
while(t--)
{
scanf("%d%d",&n,&k);
for(int i=1;i<k;i++) f[i]=0x7fffffff;
//这个初始化一定要有
//因为当i<k时是不合法的
//我们不能让之后的状态从这些状态转移过来
for(int i=1;i<=n;i++)
{
scanf("%lld",&a[i]);
s[i]=s[i-1]+a[i];
}
l=r=1;
q[1]=0;
for(int i=k;i<=n;i++)
{
while(l<r&&F(q[l+1])-F(q[l])<=i*(a[q[l+1]+1]-a[q[l]+1])) l++;
f[i]=F(q[l])+s[i]-i*a[q[l]+1];
while(l<r&&(F(i-k+1)-F(q[r]))*(a[q[r]+1]-a[q[r-1]+1])<=(F(q[r])-F(q[r-1]))*(a[i-k+1+1]-a[q[r]+1])) r--;
q[++r]=i-k+1;
//这里放的是i-k+1
//对应的是博客中的m
}
printf("%lld\n",f[n]);
}
return 0;
}