CF1175G Yet Another Partiton Problem

WZH2026-07-142026-07-27

CF1175G Yet Another Partiton Problem

人生中第三次写出特别强的黑题。

题目链接： CF1175G Yet Another Partiton Problem 。

题目描述：

给定一个数组 $a_1, a_2, \dots, a_n$ ，你需要将其分成 $k$ 个子段（每个元素恰好属于一个子段）。

一个子段 $a_l, a_{l+1}, \dots, a_r$ 的权值定义为 $(r - l + 1) \cdot \max\limits_{l \le i \le r}(a_i)$ 。一个划分的权值是所有子段权值之和。

请你找到权值最小的划分方案。

$n\le 2\times 10^4,k\le 100$ 。

时限 $5s$ ，空间限制 $500MB$ 。

根据范围可以猜测正解时间为 $O(nk\log n)$ 或者 $O(nk\log^2 n)$ 。

先设 $f_{i,k}$ 为以 $i$ 结尾，划分 $k$ 个子段的最小权值，则可以得到转移：

f_{i,k}=\min_{k-1\le j <i}\{f_{j,k-1}+(i-j)(\max_{j<p\le i}a_p)\}

先拆分可得：

f_{i,k}=\min_{k-1\le j <i}\{f_{j,k-1}-j(\max_{j<p\le i}a_p)+i(\max_{j<p\le i}a_p)\}

这是一个一次函数的形式，即，我们要找到一些一次函数的在某一条线 $x=i$ 上的最值，直接用李超树就行。

不过还有一个问题，那就是这个一次函数的一次项系数系数和常数项会随 $i$ 变化而变化。

注意到 $(\max_{j<p\le i}a_p)$ 具有单调性。也就是说，对于任意一个 $i$ ，存在一个 $j$ 使得对于任意 $j<p\le i$ 都有 $\max_{p\le q \le i}\{a_q\}=a_i$ 。

那么，我们就可以用树状数组和二分对于每个 $i$ 计算 $j$ ，那么所有的 $j$ 以后的一次函数，他们的系数都一样。对于 $j$ 之前的一次函数，他们保持不变。

我们知道，系数一样的一次函数只需要比较常数项就能确定在任意点值最小的一次函数。

那么如果我们能知道区间内常数项最小的一次函数就行了。

刚好这个常数项 $f_{j,k-1}-j((\max_{j<p\le i}a_p))$ 也是一次函数的形式！

那么我们有两种解决方案，第一种是线段树套李超树，显然不合适，空间太大了。

还有第二种方案，那就是暴力李超树合并。

为什么可以第二种方案呢？因为每一个点最多被合并一次，于是可以得到总的合并次数是 $O(n)$ 的，那么李超树合并的总复杂度就是 $O(n\log n)$ 的。

那么现在我已经做完了。现在只需要一个支持插入和回滚的李超树就行了，这一点可以用可持久化李超树实现。

那么这样总复杂度 $O(nk\log^2n)$ ，复杂度瓶颈在计算 $j$ ，这部分其实可以用单调栈和二分代替，不过我懒的改了。反正树状数组常数小，跑不满。

最终 $5s$ 的时限下， $O(nk\log^2n)$ 的算法跑了不超过 $1s$ 。

代码：

#include <bits/stdc++.h>
using namespace std;
const int N=20010,M=1000010,R=20000;
int ls[M],rs[M],rt[N],idx,n,K,b[N],f[N][110],s[M],c[N],RT[N],Id;
struct dline{
    int k,b;
    dline(){}
    dline(int k,int b):k(k),b(b){}
    int at(int x){return k*x+b;}
}a[N<<1];
void copy(int x,int y){ls[x]=ls[y],rs[x]=rs[y],s[x]=s[y];}
int build(int p,int l,int r){
    p=++idx;
    if(l==r)return p;
    int mid=(l+r)>>1;
    ls[p]=build(p,l,mid);
    rs[p]=build(p,mid+1,r);
    return p;
}
void Upd(int &p,int l,int r,int x){
    if(!p)return (void)(p=++idx,s[p]=x);
    int &y=s[p],mid=(l+r)>>1;
    int t=a[x].at(mid)-a[y].at(mid);
    if(t<0)swap(x,y);
    int tl=a[x].at(l)-a[y].at(l),tr=a[x].at(r)-a[y].at(r);
    if(tl<0)Upd(ls[p],l,mid,x);
    if(tr<0)Upd(rs[p],mid+1,r,x);
}
int upd(int p,int l,int r,int x){
    ++idx,copy(idx,p);p=idx;
    int &y=s[p],mid=(l+r)>>1;
    int t=a[x].at(mid)-a[y].at(mid);
    if(t<0)swap(x,y);
    int tl=a[x].at(l)-a[y].at(l),tr=a[x].at(r)-a[y].at(r);
    if(tl<0)ls[p]=upd(ls[p],l,mid,x);
    if(tr<0)rs[p]=upd(rs[p],mid+1,r,x);
    return p;
}
int merge(int p,int q,int l,int r){
    if(!p||!q)return p+q;
    if(l==r){
        int t=a[s[p]].at(l)-a[s[q]].at(l);
        if(t<0)swap(s[p],s[q]);
        return p;
    }
    int mid=(l+r)>>1;
    Upd(p,l,r,s[q]);
    ls[p]=merge(ls[p],ls[q],l,mid);
    rs[p]=merge(rs[p],rs[q],mid+1,r);
    return p;
}
int query(int p,int l,int r,int x){
    if(l==r)return a[s[p]].at(x);
    int mid=(l+r)>>1;
    return min(a[s[p]].at(x),(mid>=x?query(ls[p],l,mid,x):query(rs[p],mid+1,r,x)));
}
void clear(){for(int i=1;i<=n;i++)c[i]=0;}
void add(int x,int y){for(int i=x;i>=1;i-=(i&-i))c[i]=max(c[i],y);}
int Query(int x){int cnt=0;for(int i=x;i<=n;i+=(i&-i))cnt=max(cnt,c[i]);return cnt;}
int id[N],tot;
int main(){ 
    scanf("%d%d",&n,&K);
    memset(f,0x3f,sizeof(f));
    for(int i=1;i<=n;i++)scanf("%d",&b[i]);
    for(int i=1,t=0;i<=n;i++)t=max(t,b[i]),f[i][1]=i*t;
    a[0]=dline(0,2e9);
    Id=n;
    for(int i=2;i<=K;i++){
        rt[0]=build(1,1,n);
        for(int j=i;j<=n;j++){
            add(j,b[j]);
            a[j-1]=dline(b[j],f[j-1][i-1]-(j-1)*b[j]);
            a[++Id]=dline(-(j-1),f[j-1][i-1]);
            Upd(RT[j-1],1,R,Id);
            id[++tot]=j-1;
            rt[tot]=upd(rt[tot-1],1,n,j-1);
            int l=1,r=tot;
            while(l<r){
                int mid=(l+r)>>1;
                if(Query(id[mid]+1)<=b[j])r=mid;
                else l=mid+1;
            }
            if(l<tot){
                for(int k=l+1;k<=tot;k++)RT[id[l]]=merge(RT[id[l]],RT[id[k]],1,R);
                tot=l;
                a[id[l]]=dline(b[j],query(RT[id[l]],1,R,b[j]));
                rt[tot]=upd(rt[tot-1],1,n,id[l]);
            }
            f[j][i]=query(rt[tot],1,n,j);
        }
        clear();
        for(int j=0;j<=idx;j++)s[j]=ls[j]=rs[j]=0;
        for(int j=1;j<=n;j++)rt[j]=RT[j]=id[j]=0;
        idx=tot=0;Id=n;
    }
    printf("%d\n",f[n][K]);
    return 0;
}