CF1175G - Yet Another Partiton Problem
题目大意
给定序列(a_i)，现在将其分成(k)段，每段([l,r])的权值定义为((r-l+1)max{a_{l..r}})
求最小化权值总和
分析
显然有(mathbb{Naive})的(dp)
(dp_{i,j})表示前(i)个分了(j)段的答案，直接做复杂度为(O(n^2k))
优化它有几种常见思路：
1.贪心简化决策
设每个段最大值(b_i)，则一个段不能向左边扩展的条件是
两端的(b_{i-1}<b_i)（扩展会亏），或者(a_{l_i-1}>b_i)（扩展会改变(b_i)）
这样能稍微限制一下转移，然而并不好优化
2.决策单调性
枚举区间进行决策的问题通常具有单调性
于是尝试通过分治决策单调性优化到(O(nklog n))
然而已经被垃圾数据击毙 尝试证明这是假的
3.斜率优化
考虑确定(max a_i)之后，两侧(r-l+1)就是一个斜率优化的转移形式
考虑如何实现这个斜率优化
首先将(dp_{i,j})两个维护交换，按照分段数一层层进行转移
每一层，可以考虑在(a_i)的笛卡尔树上进行转移
每次考虑所有跨过当前节点的转移区间
那么就要支持：
1.查询左子树(dp_l-l cdot a_u)的最小值
2.更新右子树(dp'_r+rcdot a_u)的最小值
option1
为了实现1操作，容易想到从子树中合并凸包，或者直接进行区间凸包查询
合并凸包的问题可以暴力李超树合并维护
但事实上区间凸包是可以维护的，方法如下
1.维护一个静态线段树，(O(nlog n))归并预处理凸包
2.查询(a_u)递增，具有单调性，可以在每个被查询节点上处理一个指针
复杂度为就是均摊(O(nlog n))
option2
子树更新答案，可以通过可持久化李超树|李超树区间修改实现
复杂度分别为(O(nlog n),O(nlog^2n))，鉴于区间修改常数不满，差别不会太大
但实际上也可以通过朴素凸包实现：
从根开始dfs，每次插入一个(x+y cdot i)的线段形式
(y)是递增的，插入具有单调性，可以维护一个栈凸包
每次二分弹掉节点，插入自己
（不能直接弹，因为要支持回撤，会使得原先是均摊(O(n))的弹栈操作退化为(O(n^2))）
查询也可以通过二分解决（这实际上是一个经典树上斜率优化问题）
我当然写了李超树啦
const int N=2e4+10,U=2e4,INF=1e9+10;
int n,m,A[N];
struct Node{
ll k,b;
Node(){}
Node(ll k,ll b):k(k),b(b){}
ll operator [] (ll x) const { return k*x+b; }
};
struct Tree{
static const int M=N*20;
Node s[M];
int ls[M],rs[M],cnt;
int New(){
int u=++cnt;
ls[u]=rs[u]=0,s[u]=Node(INF,INF);
return u;
}
void Upd(int &p,int l,int r,int ql,int qr,Node x){
if(x.k==INF) return;
if(!p) p=New();
int mid=(l+r)>>1;
if(ql<=l && r<=qr) {
if(x[mid]<s[p][mid]) swap(s[p],x);
if(l==r) return;
if(x[l]<s[p][l]) Upd(ls[p],l,mid,ql,qr,x);
if(x[r]<s[p][r]) Upd(rs[p],mid+1,r,ql,qr,x);
return;
}
if(ql<=mid) Upd(ls[p],l,mid,ql,qr,x);
if(qr>mid) Upd(rs[p],mid+1,r,ql,qr,x);
}
ll Que(int p,int l,int r,int x){
if(!p) return INF;
if(l==r) return s[p][x];
int mid=(l+r)>>1;
return min(s[p][x],x<=mid?Que(ls[p],l,mid,x):Que(rs[p],mid+1,r,x));
}
int Union(int x,int y,int l,int r){
if(!x||!y) return x|y;
Upd(x,l,r,l,r,s[y]);
int mid=(l+r)>>1;
ls[x]=Union(ls[x],ls[y],l,mid),rs[x]=Union(rs[x],rs[y],mid+1,r);
return x;
}
} X,Y;
int ls[N],rs[N],stk[N],top,mk[N];
int dp[110][N];
int rt[N],Rt;
void Solve(int k,int u,int l,int r){
if(l>r) return;
Solve(k,ls[u],l,u-1),Solve(k,rs[u],u+1,r);
rt[u]=rt[ls[u]];
if(u>1) X.Upd(rt[u],1,U,1,U,Node(-(u-1),dp[k][u-1]));
int res=X.Que(rt[u],1,U,A[u]);
Y.Upd(Rt,1,n,u,r,Node(A[u],res));
rt[u]=X.Union(rt[u],rt[rs[u]],1,U);
}
int main(){
X.s[0]=Y.s[0]=Node(INF,INF);
n=rd(),m=rd();
rep(i,1,n) {
A[i]=rd();
while(top && A[stk[top]]<A[i]) ls[i]=stk[top--];
if(top) rs[stk[top]]=i;
stk[++top]=i;
}
rep(i,1,n) mk[ls[i]]=mk[rs[i]]=1;
int rt=0;
rep(i,1,n) if(!mk[i]) rt=i;
int ma=0;
rep(i,1,n) cmax(ma,A[i]),dp[1][i]=ma*i;
rep(i,1,m-1) {
X.cnt=0,Y.cnt=0;
Solve(i,rt,1,n);
rep(j,1,n) dp[i+1][j]=Y.Que(1,1,n,j);
}
printf("%d
",dp[m][n]);
}