题解 CF1175G

· · 题解

这个题是套娃题！（确信）

拿到题，我们就可以发现那个 k 就只是一个做 k 轮的事情，所以我们现在只需要考虑一轮中的转移就可以了。

然后就可以有一个暴力的转移 ： dp_{i} = \min_{j<i}\{pdp_{j}+(i-j)\times\max_{j<k\le i}a_k\}。（pdp 表示上一轮的 dp 值）

我们的目的是优化，所以那个 max 就显得很格格不入，所以我们考虑把它干掉。

很容易想到，一个位置为结尾的后缀 max 是一段一段的，所以我们可以考虑开一个单调栈，对于每一段后缀 max 相等的位置来维护信息，这样每一段中那个 max 就是一个定值了。

假设我们现在有一段连续的起始位置，他们到当前 i 的后缀 max 都是 M。

拆开 dp 式子 ：dp_i= \min(pdp_j-jM+iM)。

对于这种 Dp 式子其它优化方式都行不通，所以我们考虑斜率优化（李超线段树）。

分析一下，前面 pdp_j-jM 只与这段中的 j 与 M 有关，取这一段中的最小值即可，所以我们将它看做直线中的 b，那么 i 就自然是 x，M 就是 k。

那么这样每一个连续的 max 不变的段就可以表达为一条直线，然后每一次都相当于询问 i 处的直线最值，用李超线段树维护即可。

但是事情还没有完，我们忘了一个阴间操作——单调栈的弹栈。

弹栈所带来的影响由有：

首先，因为是单调栈维护的，所以这个删除本质上是撤销。所以直接可撤销李超树即可（就是开一个栈将所有修改操作记下来，或者你也可以选择可持久化李超树）。

对于第二个问题，我们很明显不可以每次暴力扫一遍被合并的区间，否则一个单增序列就卡得掉。

所以我们只能考虑对于每一段维护一个数据结构，支持合并，并在 M 改变时迅速求出 pdp_j-jM 的极值。

想到什么了吗？李超树。

我们将 pdp_j 看做 b，j 看做 k，M 看做 x，这就又变成了一个李超树能维护的形式。

对于合并，我们采用类似 CF932F 的方式合并即可，复杂度可以由将每条直线在李超树上所处的深度看做势能证明为均摊 O(n\log n)。

所以，我们就使用单调栈维护的可撤销李超树和李超树合并解决了这个题，总复杂度 O(kn\log n)。

所以这是套娃题！（确信）

代码：

#include <cstdio>
#include <climits>
#include <cstring>
#include <algorithm>
using std::min;using std::swap;
typedef long long ll;
const int maxn = 2e4+5;
int n,k,a[maxn];
int st[maxn],top;
ll dp[maxn],pdp[maxn];
int lcnt;
struct Line{
    int k;ll b;
    Line(int K=0,ll B=0):k(K),b(B){};
    ll val(int x){return 1ll*k*x+b;}
}L[maxn<<1];
int rt[maxn],ch[maxn*20][2],Lid[maxn*20],tot;
void clear(){memset(rt,0,sizeof(rt));for(int i=1;i<=tot;++i)ch[i][0] = ch[i][1] = Lid[i] = 0;tot = 0;}
struct Op{int t,p,x;};
int optop,tim;
Op opst[maxn*20];
void ins(int &u,int l,int r,int id,int ty){
    if(!u)return Lid[u=++tot]=id,(ty?opst[++optop]=(Op){tim,u,0}:Op()),void();
    if(l == r)return (L[Lid[u]].val(l)>L[id].val(l)?((ty?opst[++optop]=(Op){tim,u,Lid[u]}:Op()),Lid[u]=id):0),void();
    int mid = l+r>>1;
    if(L[Lid[u]].val(mid) < L[id].val(mid))L[Lid[u]].k < L[id].k ? ins(ch[u][0],l,mid,id,ty) : ins(ch[u][1],mid+1,r,id,ty);
    else (L[Lid[u]].k < L[id].k ? ins(ch[u][1],mid+1,r,Lid[u],ty) : ins(ch[u][0],l,mid,Lid[u],ty)),(ty?opst[++optop]=(Op){tim,u,Lid[u]}:Op()),Lid[u] = id;
}
int merge(int A,int B,int l,int r){
    if(!A||!B)return A+B;
    if(l == r)return Lid[A] = (L[Lid[A]].val(l)<L[Lid[B]].val(l)?Lid[A]:Lid[B]),A;
    int mid = l+r>>1;
    if(L[Lid[A]].val(mid) > L[Lid[B]].val(mid))swap(Lid[A],Lid[B]);
    ch[A][0] = merge(ch[A][0],ch[B][0],l,mid),ch[A][1] = merge(ch[A][1],ch[B][1],mid+1,r),ins(A,l,r,Lid[B],0);
    return A;
}
ll qrymin(int u,int l,int r,int p){
    if(!u)return LLONG_MAX;
    int mid = l+r>>1;
    return min(L[Lid[u]].val(p),(p<=mid?qrymin(ch[u][0],l,mid,p):qrymin(ch[u][1],mid+1,r,p)));
}
int main(){
    scanf("%d %d",&n,&k),L[0] = Line(0,LLONG_MAX);
    for(int i=1;i<=n;++i)scanf("%d",&a[i]);
    memset(pdp,0x3f,sizeof(pdp)),pdp[0] = 0;
    for(int R=1;R<=k;++R){
        clear(),top = lcnt = optop = 0;
        for(int i=1;i<=n;++i){
            int now = i,nowval = a[i];
            L[++lcnt] = Line(-(i-1),pdp[i-1]),ins(rt[i],1,2e4,lcnt,0); 
            while(top && a[st[top]] < a[i]){
                while(optop && opst[optop].t == st[top])Lid[opst[optop].p] = opst[optop].x,--optop;
                rt[i] = merge(rt[i],rt[st[top]],1,2e4),--top;
            }
            L[++lcnt] = Line(a[i],qrymin(rt[i],1,2e4,a[i])),tim = st[++top] = i,ins(rt[0],1,n,lcnt,1);
            dp[i] = qrymin(rt[0],1,n,i);
        }
        memcpy(pdp,dp,sizeof(dp));
    }
    return printf("%lld\n",dp[n]),0;
}

求勿喷码风。