LXI.CF868F Yet Another Minimization Problem

这种题一般来说只有决策单调性一种优化方法。不过，决策单调性可以有很多种应用，例如单调队列或是斜率优化。这题可以选择比较少见的分治优化。

明显，可以设\(f[i][j]\)表示前\(i\)个位置分成\(j\)段的最大收益。显然，暴力是\(O(n^2k)\)的。

如果我们按照\(j\)一遍一遍地跑的话，是可以考虑在\(i\)上面进行优化的、

考虑设\(f[i]\)表示\(f[i][j-1]\)，\(g[i]\)表示\(f[i][j]\)，

然后设\(w[l,r]\)表示区间\([l,r]\)的费用，

则我们是否可以证明它具有决策单调性？

即：

对于\(\forall i_1<i_2\)，设它们分别从\(j_1\)，\(j_2\)转移来最优，则必有\(j_1\leq j_2\)。

则必有

\(g_{j_1}+w[j_1+1,i_1]\leq g_{j_2}+w[j_2+1,i_1],g_{j_2}+w[j_2+1,i_2]\leq g_{j_1}+w[j_1+1,i_2]\)

我们可以考虑反证法。假设有\(j_1>j_2\)，

则对于上面的两个不等式里，如果两个都取到了\(=\)，则交换\(j_1,j_2\)没有影响。

否则，我们不妨设在第一个式子里取到了\(<\)，

即

\(g_{j_1}+w[j_1+1,i_1]<g_{j_2}+w[j_2+1,i_1],g_{j_2}+w[j_2+1,i_2]\leq g_{j_1}+w[j_1+1,i_2]\)

移项得

\(w[j_1+1,i_1]-w[j_2+1,i_1]<g_{j_2}-g_{j_1},g_{j_2}-g_{j_1}\leq w[j_1+1,i_2]-w[j_2+1,i_2]\)

两边合并\(g_2-g_1\)，得

\(w[j_1+1,i_1]-w[j_2+1,i_1]<w[j_1+1,i_2]-w[j_2+1,i_2]\)

这两项全部只有后面的\(i_1\)和\(i_2\)不同。但\(i_1<i_2\)，因此这是不可能成立的，往区间后面加数后答案必不会减少。

然后就可以分治了。每一轮我们存储对于当前区间\([l,r]\)可行的决策点\([L,R]\)，对于\([l,r]\)的中点\(mid\)，我们找到最优转移位置\(mp\)，然后继续分治\(([l,mid-1],[L,mp])\)与\(([mid+1,r],[mp,R])\)。

关于如何计算\(w[l,r]\)吗……类似的莫队一下，因为单次分治中左右端点总移动距离是\(n\log n\)的（每一层里面左右端点总次数是\(O(n)\)的，然后一共\(\log n\)层）。

总复杂度\(O(nk\log n)\)。

代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,m,num[101000],cnt[101000],res,f[100100],g[100100];
int u,v;
void Push(int x){
	res+=cnt[num[x]],cnt[num[x]]++;
}
void Pop(int x){
	cnt[num[x]]--,res-=cnt[num[x]];
}
int Calc(int l,int r){
	while(u>l)Push(--u);
	while(v<r)Push(++v);
	while(u<l)Pop(u++);
	while(v>r)Pop(v--);
	return res;
}
void solve(int l,int r,int L,int R){
	if(l>r||L>R)return;
	int mp=-1,mn=0x3f3f3f3f3f3f3f3f,mid=(l+r)>>1;
	for(int i=L;i<=R;i++){
		int tmp=Calc(i+1,mid);
		if(f[i]+tmp<mn)mp=i,mn=f[i]+tmp;
	}
	g[mid]=mn;
	solve(l,mid-1,L,mp),solve(mid+1,r,mp,R);
}
signed main(){
	scanf("%lld%lld",&n,&m);
	for(int i=1;i<=n;i++)scanf("%lld",&num[i]);
	u=v=1,cnt[num[1]]++;
	for(int i=1;i<=n;i++)f[i]=Calc(1,i);
	while(--m)solve(1,n,0,n-1),memcpy(f,g,sizeof(g));
	printf("%lld\n",f[n]);
	return 0;
}