【Codeforces 1175G】Yet Another Partiton Problem
分治、李超树、凸包优化动态规划。
题目大意：
给定一个长度为 $n$ 的数列 $a_1,a_2,a_3,\ldots,a_n$，要求将其划分为恰好 $k$ 段（不能为空），并且使每段的权值的总和最小。
对于一段划分 $[l,r]$，它的权值定义为 $(r−l+1)\cdot \max\limits_{i=l}^r a_i$。
题解：
首先有一个非常简单的 $O(n^2k)$ 的 dp：设 $f_{i,j}$ 表示前 $i$ 个数分成 $j$ 段的信息，然后转移按照题意即可。
由于每层的信息只会从上一层转移过来，考虑依次处理出分成 $1\sim k$ 段的值。
考虑分治进行转移，每次只考虑左边对右边的贡献。
每次分治的时候，我们先处理出左、右每个点到中间的前缀、后缀 $\max$，然后分两种情况讨论：
最大值在左边。对于左边的每个数，它都会对右边的一段区间产生贡献，有贡献的条件是左边这个数到中点的最大值大于等于右边这个数到中点的最大值。
容易发现，它对右边的这段区间产生的贡献是一个一次函数，我们要求的是最小值。因此可以使用李超树来维护。
最大值在右边。对于右边的每个数，左边都有一段区间能对它产生贡献，有贡献的条件是左边这个数到中点的最大值大于等于右边这个数到中点的最大值。
此时，由于 $\max a_i$ 固定且单调递增，左边每个数对右边的所有数的贡献都是一次函数，所以我们考虑对左边的点维护下凸壳，每次在凸壳上二分最小值来进行转移即可。
由于前缀、后缀 $\max$ 具有单调性，所以两种情况都可以双指针转移。
时间复杂度 $O(nk\log^3n)$，空间复杂度 $O(n)$。
其中的三个 $\log$ 分别是分治的一个 $\log$ 和李超树的两个 $\log$。由于李超树的常数很小，所以可以轻松通过。
Code：
#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long LL;
const int N=2e4+5;
int n,k,a[N],dp[N],h[N],d[N];
struct node{
int k,b;
inline node(int K,int B):k(K),b(B){}
inline node(){k=5e4,b=1e9;}
inline int operator()(const int&x)const{return k*x+b;}
};
namespace sgt{
node f[N<<2];
void add(int l,int r,int o,const int&L,const int&R,const node&g){
if(L<=l&&r<=R){
int vL=g(l),vR=g(r);
int nL=f[o](l),nR=f[o](r);
if(nL<=vL&&nR<=vR)return;
if(nL>=vL&&nR>=vR){f[o]=g;return;}
}
if(l==r)return;
const int mid=l+r>>1;
if(L<=mid)add(l,mid,o<<1,L,R,g);
if(mid<R)add(mid+1,r,o<<1|1,L,R,g);
}
inline int query(int l,int r,int o,const int&x){
if(l==r)return f[o](x);
const int mid=l+r>>1;
int res=f[o](x);
if(x<=mid)return min(res,query(l,mid,o<<1,x));
return min(res,query(mid+1,r,o<<1|1,x));
}
inline void rebuild(int l,int r,int o){
f[o]=node();
if(l<r){
const int mid=l+r>>1;
rebuild(l,mid,o<<1),rebuild(mid+1,r,o<<1|1);
}
}
}
struct point{
int x,y;
inline point operator-(const point&rhs)const{return(point){x-rhs.x,y-rhs.y};}
}sta[N];
inline LL cross(const point&a,const point&b){return(LL)a.x*b.y-(LL)a.y*b.x;}
int top;
void insert(int x,int y){
point t=(point){x,y};
while(top>1&&cross(sta[top]-sta[top-1],t-sta[top-1])<=0)--top;
sta[++top]=t;
}
inline int calc(const point&a,int L,int k){return(a.x+L)*k+a.y;}
inline int binary(int len,int k){
int res=0x3fffffff;
if(top<=20){
for(int i=1;i<=top;++i)
res=min(res,calc(sta[i],len,k));
}else{
res=calc(sta[1],len,k);
int l=2,r=top,ans=1;
while(l<=r){
const int mid=l+r>>1;
int dlt=calc(sta[mid],len,k)-calc(sta[mid-1],len,k);
if(dlt<0)l=(ans=mid)+1;else r=mid-1;
}
res=min(res,calc(sta[ans],len,k));
}
return res;
}
void solve(int l,int r){
if(l==r){
d[l]=min(d[l],dp[l-1]+a[l]);
return;
}
const int mid=l+r>>1;
solve(l,mid);
solve(mid+1,r);
h[mid]=a[mid],h[mid+1]=a[mid+1];
for(int i=mid-1;i>=l;--i)h[i]=max(a[i],h[i+1]);
for(int i=mid+2;i<=r;++i)h[i]=max(a[i],h[i-1]);
int it=mid+1;
for(int i=mid;i>=l;--i){
while(it<=r&&h[i]>=h[it])++it;
int L=mid+1,R=it-1;
if(L>R)continue;
int k=h[i],b=dp[i-1]+(L-i+1)*k-L*k;
sgt::add(1,n,1,L,R,node(k,b));
}
top=0;
it=mid;
for(int i=mid+1;i<=r;++i){
while(it>=l&&h[it]<h[i])
insert(mid-it+1,dp[it-1]),--it;
if(top)d[i]=min(d[i],binary(i-mid,h[i]));
}
}
int main(){
scanf("%d%d",&n,&k);
for(int i=1;i<=n;++i)scanf("%d",a+i);
for(int i=1,mx=0;i<=n;++i){
mx=max(mx,a[i]);
dp[i]=mx*i;
}
for(int t=2;t<=k;++t){
for(int i=1;i<=n;++i)d[i]=2e9;
solve(1,n);
for(int i=1;i<=n;++i)dp[i]=min(d[i],sgt::query(1,n,1,i));
sgt::rebuild(1,n,1);
}
printf("%d\n",dp[n]);
return 0;
}