Title:

A sequence is divided into k segments so that the sum of the reverse pairs of each segment is minimized.

Explanation:

dp+cdq.
For the first time, I did the problem of dividing the decision-making into two parts. After seeing the solution, I was forced to get the code this morning
First of all, it is easy to think of the monotony of decision-making. If J > k and j is better than k, then J is always better than k.
Then divide and conquer the decision, that is, pass it into the current transfer range. For the number of reverse pairs, the tree array maintenance is all right. Unclear, specific code
code:

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#define LL long long
using namespace std;
int q[40010],Q[40010];
int n,k,a[40010],f[40010],g[40010],tr[40010],L,R,now;
void change(int k,int c) {for(int i=k;i<=n;i+=i&-i) tr[i]+=c;}
int get(int k) {int ans=0;for(int i=k;i>=1;i-=i&-i) ans+=tr[i];return ans;}
inline void go(int l,int r)
{
  while(R<r) now+=(R-L+1-get(a[R+1])),change(a[R+1],1),R++;
  while(L<l) now-=get(a[L]-1),change(a[L],-1),L++;
  while(L>l) now+=(get(a[L-1]-1)),change(a[L-1],1),L--;
  while(R>r) now-=(R-L+1-get(a[R])),change(a[R],-1),R--;
}
void cdq(int l,int r,int dl,int dr)
{
    int mid=(l+r)/2,dm=dl;
    for(int i=dl;i<=dr&&i<mid;i++)
    {
        go(i+1,mid);
        int t=g[i]+now;
        if(t<f[mid]) f[mid]=t,dm=i;
    }
    if(l<mid) cdq(l,mid-1,dl,dm);
    if(r>mid) cdq(mid+1,r,dm,dr);
}
int main()
{
    scanf("%d %d",&n,&k);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    for(int i=1;i<=n;i++)
    {
        change(a[i],1);
        f[i]=f[i-1]+i-get(a[i]);
    }
    for(int i=2;i<=k;i++)
    {
        memcpy(g,f,sizeof(g));
        memset(f,63,sizeof(f));
        memset(tr,0,sizeof(tr));
        L=R=1;now=0;change(a[1],1);
        cdq(i,n,i-1,n);
    }
    printf("%d",f[n]);
}