减少地皮码量，重铸 Larsch 荣光

· · 算法·理论

其他对于此算法的介绍/文章：

在线决策单调性地皮还能单老哥分治做？

OIwiki

update on 2026/4/15：修改了某些 larsch 打成 larcsh 的笔误。

1.算法介绍

众所周知啊，一个具有决策单调性的 DP，它是有很多实现方法的，比如二分队列大家应该都会写吧。但是经过后人的总结，我们发现二分队列的码量还是有一点大了，它还可以做的更简洁。

于是出现了一个新科技——在线决策单调性 DP 单 log 分治，也叫简化版 Larsch 算法。

它的优点是：可以处理半在线 DP 转移，码量小，常数也极小。

先说说什么是在线。设 dp_i 的决策点为 p_i。

对于一个具有决策单调性的 DP，如果它的转移系数为 0，那么它是离线的，

也就是说，dp_i=\min_{j=1}^{i-1}\{w(j,i)\} 的问题。容易发现这个问题中，我们要算 dp_x 的值不需要算出任何 dp_i 的值（i<x），所以可以离线二分。也就是每次全部扫一遍，计算出 dp_{mid} 和 p_{mid} 的值，直接向下传即可。

而半在线的转移系数不为 0。

也就是说，dp_i=\min_{j=1}^{i-1}\{dp_j+w(j,i)\} 的问题。在这个问题中，我们要算 dp_x 的值至少要算出 dp_{p_x} 的值，而离线分治无法做到这一点。

那么 larsch 是如何实现的呢？下面是我的见解：

以下该算法解决的问题为 dp_i=\min_{j=1}^{i-1}\{dp_j+w(j,i)\}，其中函数 w(l,r) 是定义在非负整数域上的二元函数。

要实现这个算法，我们要设计一个函数 \textup{solve}(l,r)，使得经过此函数后，dp_{l+1}\sim dp_r 的值都算对了。那么我们如果能保证进入 \textup{solve}(l,r) 之前，dp_1\sim dp_l 和 p_1\sim p_l 的值都算对了，并且只考虑 1\sim l 的话，dp_r 和 p_r 都算对了，那么只需要递归二分即可算对所有 dp 的值。

考虑一下正确性。如果我们能保证刚才那些成立，那么递归到最后一层 \textup{solve}(x,x+1) 时，dp_1\sim dp_x 和 p_1\sim p_x 的值都算对了，并且已经考虑完了 1\sim x，所以 dp_{x+1} 的值一定是对的，返回即可。在此情况下我们只需保证左边的 dp 值先算出来，右边的 dp 值后算出来，就可以处理半在线 DP 转移了。

然后考虑实现方法。假设当前进行到了 \textup{solve}(l,r)，mid=\frac{l+r}{2}。想要继续向 \textup{solve}(l,mid) 递归，就得保证只考虑 1\sim l，dp_{mid} 和 p_{mid} 都算对了。根据决策单调性，此时已经考虑了 1\sim l，所以 p_{mid} 一定在 p_l 和 p_r 之间。遍历 p_1 到 p_r，更新 dp_{mid} 的答案即可。想要继续向 \textup{solve}(mid,r) 递归，就得保证只考虑 1\sim mid，dp_{r} 和 p_{r} 都算对了。因为进入这个函数之前，我们已经考虑了 1\sim l，而刚刚对于 \textup{solve}(l,mid) 的递归才结束，dp_{l+1}\sim dp_{mid} 的值都算对了。所以只需遍历 l+1\sim mid，更新 dp_r 的值即可。

容易发现时间复杂度是 O(n\log n) 的（假设 w 函数可以 O(1) 算出）。

2.实现细节

接下来来到我真正想说的环节了（bushi），因为感觉大家或多或少都听说过这个算法却没写过。这个算法的唯一缺点就是边界情况不太好判断。就写了俩题，我踩了 998244353 个坑了已经。

:::epigraph[——卡帕瓦_KAPawa] 世界上最绝望的五个字是——“找不到差异”。 :::

易错点一：

首先，因为 \textup{solve}(l,r) 是解决 l+1\sim r 之间的问题的。所以一般物体（比如这只猫）肯定会先想到调用的时候要调用 \textup{solve}(0,n)。但是这样很容易出错，因为假如你的 w(l,r) 里写了 dp_{l-1} 啊，或者出现了 dp_0 未初始化啊等等问题，都会导致最终答案出错。我认为在调用函数时最好单独考虑 dp_0 和 dp_1，再调用 \textup{solve}(1,n)。所以在写代码之前一定要想一想在 DP 转移时需不需要用到 dp_0 的值。（比如上图的这道题，就因为不小心考虑了 dp_0 导致 97\text{pts} 调了一晚上。）若不需要，强烈建议你在计算 w 的值时特判一下。

以下是实现参考。

:::info[不需考虑 dp_0]

inline ll w(ll j,ll i){

    if(j==0) return inf;
    //else ...
}

inline void check(ll j,ll i){

    if(w(j,i)>f[i]) f[i]=w(j,i),p[i]=j;
    return;
}

inline void larsch(ll l,ll r){

    //...
    return;
}

inline void work(){

    for(int i=0;i<=n;i++) p[i]=0,f[i]=-inf;

    //check(1,1);
    check(1,n);
    //check(n,n);
    larsch(1,n);

    return;
}

:::

:::info[需要考虑 dp_0]

inline ld w(ll j,ll i){

    //return ...
}

inline void check(ll j,ll i){

    if(w(j,i)>f[i]) f[i]=w(j,i),p[i]=j;
    return;
}

inline void larsch(ll l,ll r){

    //...
    return;
}

inline void work(){

    for(int i=0;i<=n;i++) p[i]=0,f[i]=-inf;

    check(0,1);
    check(0,n);
    check(1,n);
    larsch(1,n);

    return;
}

:::

易错点二：

容易发现，我上面的第一个代码中，出现了注释掉的 check(1,1) 以及 check(n,n)。这是怎么一回事呢？因为有些题目比较特殊，dp_i 的决策点可以是它自己（也就是 p_i=i，依旧参见上面这道题）。所以就要考虑决策点是自己的这种情况。还要注意，当决策点可以是它本身时，你的 larsch 在递归到最后一层的时候，要写一个这个。

:::info[这个]

inline void larsch(ll l,ll r){

    if(l+1==r){

        check(r,r);
        return;
    }
}

:::

而如果没有这种情况的出现，只需要写那个就可以了。

:::info[那个]

inline void larsch(ll l,ll r){

    if(l+1==r) return;
}

:::

下面是一般情况实现参考。

:::success[代码]

inline void check(ll j,ll i){

    if(w(j,i)>f[i]) f[i]=w(j,i),p[i]=j;
    return;
}

inline void larsch(ll l,ll r){

    if(r==l+1){

        //check(r,r);
        return;
    }

    ll mid=(l+r)>>1;

    for(int j=p[l];j<=p[r];j++) check(j,mid);
    larsch(l,mid);

    for(int j=l+1;j<=mid;j++) check(j,r);
    larsch(mid,r);

    return;
}

inline void work(){

    for(int i=0;i<=n;i++) p[i]=0,f[i]=-inf;

    //check(1,1);
    //check(0,0);
    //check(0,1);
    //check(0,n);
    check(1,n);
    //check(n,n);
    larsch(1,n);

    return;
}

:::

和二分队列的代码一对比，就能看出来码量优势了。虽然不一定短了多少，但是清晰了不少。在这道题中，larsch 直接进入了最优解第二页开头（减去套数据 30\text{ms} 的），和某些单老哥做法平起平坐。