链接：https://www.luogu.com.cn/problem/P5574
题目描述：将序列分为\(k\)段，最小化每一段的顺序对之和。
题解：将序列分为\(k\)段，这样让我们想到\(dp\)。令\(dp_{i,j}\)表示划分了\(i\)，末端为\(j\)的最小代价。
可以发现它有决策单调性，证明：
令\(p\)是\(j\)的决策点，\(t<p\)。
则\(f_{p}+w(i,j)<=f_{t}+w(t,j)\)
又有\(w(i,j+1)-w(i,j)<=w(t,j+1)-w(t,j)\)(因为\([p,j]\)属于\([t,j]\)的一段，所以所有\(j+1\)对\([p,j]\)产生的贡献都在\([t,j]\)产生了，所以\(j+1\)对\(p\)的贡献小于等与对\(t\)的贡献。
两式相加得\(f_{p}+w(i,j+1)<=f_{t}+w(t,j+1)\)
即\(dp\)方程具有决策单调性。
那么我们可以整体二分求决策点的范围，但是如何快速求\(w\)函数呢\(?\)
\(w_{i,j}=s_{j}+S_{i-1}-g_{i,j}\)(其中\(s_{i}\)表示\([1,i]\)的顺序对个数，\(S_{i}\)表示\([1,i]\)的逆序对个数，\(g_{i,j}\)表示\([1,i]\)与\([1,j]\)中前者序列中一个元素小于后者序列中一个元素的对数，这个容斥可以得到)
然后\(g\)可以用莫队快速求出，在这上面跑莫队复杂度正确，证明以后再写(太长了，不好写)。
则复杂度\(O(nk log n)\)。
#include<iostream>
#include<cstdio>
using namespace std;
long long res,fans,ll,rr,c[2][100001],a[100001],S[2][100001],n,k;
long long dp[26][100001];
int lowbit(int x)
{
return x&(-x);
}
void add(int K,int x,int y)
{
for (;x<=n;x+=lowbit(x))
c[K][x]+=y;
return;
}
long long sum(int K,int x)
{
res=0;
for (;x>=1;x-=lowbit(x))
res+=c[K][x];
return res;
}
int read()
{
int sum=0;
char c=0;
while (c<'0'||c>'9')
c=getchar();
while ('0'<=c&&c<='9')
{
sum=sum*10+c-'0';
c=getchar();
}
return sum;
}
void movepos(bool type,int x,int d)
{
if (type==0)
{
fans+=d*sum(1,n-a[x]);
add(0,a[x],d);
}
else
{
fans+=d*sum(0,a[x]-1);
add(1,n-a[x]+1,d);
}
return;
}
long long f(int x,int y)
{
while (ll<x)
movepos(0,++ll,1);
while (ll>x)
movepos(0,ll--,-1);
while (rr<y)
movepos(1,++rr,1);
while (rr>y)
movepos(1,rr--,-1);
return fans;
}
long long g(int x,int y)
{
if (x>y)
return 1e18;
return S[0][y]+S[1][x-1]-f(x-1,y);
}
void solve(int K,int l,int r,int L,int R)
{
if (l>r)
return;
long long ans=0,p=L,mid=(l+r)/2;
for (int i=L;i<=R;++i)
if (dp[K-1][i-1]+g(i,mid)<dp[K][mid])
{
dp[K][mid]=dp[K-1][i-1]+g(i,mid);
p=i;
}
solve(K,l,mid-1,L,p);
solve(K,mid+1,r,p,R);
return;
}
int main()
{
n=read(),k=read();
for (int i=1;i<=n;++i)
a[i]=read();
for (int i=0;i<=k;++i)
for (int j=0;j<=n;++j)
dp[i][j]=1e18;
dp[0][0]=0;
for (int i=1;i<=n;++i)
{
S[0][i]=S[0][i-1]+sum(0,a[i]);
add(0,a[i],1);
S[1][i]=S[1][i-1]+sum(1,n-a[i]+1);
add(1,n-a[i]+1,1);
}
for (int i=1;i<=k;++i)
{
ll=0;
rr=0;
fans=0;
for (int j=1;j<=n;++j)
c[0][j]=c[1][j]=0;
solve(i,1,n,1,n);
}
printf("%lld\n",dp[k][n]);
return 0;
}