青春猪头少年不会梦到 Slope Trick 学姐

lovely_nst · 2026-02-03 10:53:09 · 算法·理论

我的 Slope Trick 题单

前言

本文讲的 Slope Trick 与传统 Slope Trick 在求得答案的过程有少量差别，个人感觉更好理解。

本文存在大量平衡树。

Slope Trick 简介

Slope Trick 就是用数据结构维护呈凸性的 DP 值以优化复杂度。常见的形式有：

由于绝对值函数是凸函数，因此经常在 Slope Trick 相关题目中出现。

凸函数

在 Slope Trick 中一般提到的都是下凸函数。

上图就是常见的凸函数，其具有几个性质：

• 凸函数上相邻的两点的斜率随着横坐标的增加而递增（这一性质是大部分斜率优化题目的根基，可以用二分，单调栈，优先队列等维护）
• 两个凸函数按位相加后还是凸函数（把凸包按位加和斜率想象成序列相加和差分数组，两个递增的差分数组相加还是递增的）

Slope Trick

结合例题讲解。

例题 1 P4597 序列 sequence

题意

给定一个序列，每次操作可以把某个数 +1 或 −1。要求把序列变成非降数列。

暴力

设 f_{i,j} 表示枚举到第 i 位，这一位变成了 j 的最小操作次数。

容易得到：

于是我们就有了 O(nV^2) 的暴力 DP 了，加上前缀和可以进一步优化。

正解

发现 \left|j-a_i\right| 与 k 无关，可以提前。那么原式变为：

考虑 f(x)=\left|x-v\right| 函数长啥样的。

当 x<v 时，f(x) 随 x 递减而递增，斜率为 -1。

当 x>v 时，f(x) 随 x 递增而递增，斜率为 1。

因此是凸的。

设 f_i(x)=f_{i,x}，那么 f_0(x)=0 也可以看作是凸的。

对一个凸函数 f(x) 做前缀 \min 可以分类讨论：

• 当 f(i)<f(i-1) 时（斜率为负），f(i) 更优。
• 当 f(i)=f(i-1) 时（斜率为 0），f(i) 取全局最小值。
• 当 f(i)>f(i-1) 时（斜率为正），因为到 i 时已经经过上一种情况，因此 f(i)\ge \min f(x)，f(i) 取全局最小值。

由上，做前缀 \min 可以看成将后面一段斜率为正的推平成全局最小值（即修改斜率为 0），因此做完还是凸的。

因为凸函数相加还是凸函数，可以推得 f_i(x) 是凸的。

考虑用优先队列维护拐点横坐标，每经过一个拐点斜率加 1（当在一个位置的斜率差大于 1 时也要对应加入相同个数的拐点），加绝对值函数相当于在 a_i 处加入两个拐点（-1 和 1 差了 2，加入后斜率差也会加 2）。

做完前面的，目前第一条直线的斜率会是 -i（因为加入了 i 个绝对值函数，当一个点的横坐标比 a_i 的最小值还小时，所有绝对值函数的贡献均为 -1，斜率就会是 -i）。做前缀 \min 推平就是只保留前 i 个拐点（只保留斜率为 -i 到 0 的直线，对应的只有 i 个拐点）。

以下与传统 Slope Trick 有差别

最后计算答案，我们先计算 f_{n,-inf}，最后暴力计算斜率为 0 的平台的高度，即暴力还原凸函数。

具体见代码。

:::success[AC Code]

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int inf = 2e9;
priority_queue <int> q;
stack <int> s;
signed main ()
{
    ios::sync_with_stdio (0) , cin.tie (0) , cout.tie (0);
    int n;
    cin >> n;
    int f = 0;
    for (int i = 1;i <= n;i ++)
    {
        int x;
        cin >> x;
        f += x + inf; // f[n][-inf]
        q.push (x);
        q.push (x);
        // 加入两个拐点
        q.pop (); // min 推平
    }
    while (!q.empty ()) s.push (q.top ()) , q.pop ();
    int lst = -inf;
    for (int i = n;i >= 1;i --)
        f -= (s.top () - lst) * i , lst = s.top () , s.pop ();
    // 暴力还原凸函数
    cout << f;
    return 0;
}

:::

相较于传统维护平台的方法，这样更加直接，但也存在缺陷（见例二）。

例二 P11598 [NOISG 2018 Finals] Safety

题意

给定一个序列，每次操作可以把某个数 +1 或 −1（不能小于 0）。给定 h，要求序列满足：

题解

设 f_{i,j} 表示枚举到第 i 位，改位最终为 j 的最小操作次数。容易得到方程：

通过斜率为 0 的区间 \left[L,R\right] 分类讨论：

• 其余情况，\left[j-h,j+h\right] 一定可以取到 \left[L,R\right] 内的任意位置，最小值为全局最小值。

因此可以使用平衡树切割区间维护拐点。对于左侧（L 那一侧），f_{i,j}=f_{i,j+h}，也就是拐点横坐标集体减 h；对于右侧（R 那一侧），f_{i,j}=f_{i,j-h}，也就是拐点横坐标集体加 h。

之后的流程都是一样的，不同点在 f_{n,0} 的计算。

由转移方程可以得到：

普通堆无法做到双向获取值，因此使用平衡树或 set 维护。

AC Code

:::success[FHQ Treap]

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e6 + 5;
mt19937 rd (time (0));
struct Treap
{
    int cc = 0;
    struct Node
    {
        int l , r , v , w , sz , tag;
    } tr[N];
    int get_new (int x) // 创建节点
    {
        tr[++ cc] = {0 , 0 , x , rd () , 1};
        return cc;
    }
    void push_down (int p) // 下传标记
    {
        if (tr[p].tag)
        {
            tr[tr[p].l].v += tr[p].tag;
            tr[tr[p].r].v += tr[p].tag;
            tr[tr[p].l].tag += tr[p].tag;
            tr[tr[p].r].tag += tr[p].tag;
            tr[p].tag = 0;
        }
    }
    void add (int p , int x) {tr[p].v += x , tr[p].tag += x;} // 子树加
    void spl (int p , int x , int &l , int &r) // <= x 分裂
    {
        if (!p)
        {
            l = r = 0;
            return ;
        }
        push_down (p);
        if (tr[p].v <= x)
        {
            l = p;
            spl (tr[p].r , x , tr[p].r , r);
        }
        else
        {
            r = p;
            spl (tr[p].l , x , l , tr[p].l);
        }
        tr[p].sz = tr[tr[p].l].sz + tr[tr[p].r].sz + 1;
    }
    void splsz (int p , int x , int &l , int &r) // 长度 < x 分裂
    {
        if (!p)
        {
            l = r = 0;
            return ;
        }
        push_down (p);
        if (tr[tr[p].l].sz < x)
        {
            l = p;
            splsz (tr[p].r , x - tr[tr[p].l].sz - 1 , tr[p].r , r);
        }
        else
        {
            r = p;
            splsz (tr[p].l , x , l , tr[p].l);
        }
        tr[p].sz = tr[tr[p].l].sz + tr[tr[p].r].sz + 1;
    }
    int mrg (int l , int r) // 合并
    {
        if (!l || !r)
            return l | r;
        if (tr[l].w <= tr[r].w)
        {
            push_down (l);
            tr[l].r = mrg (tr[l].r , r);
            tr[l].sz = tr[tr[l].l].sz + tr[tr[l].r].sz + 1;
            return l;
        }
        else
        {
            push_down (r);
            tr[r].l = mrg (l , tr[r].l);
            tr[r].sz = tr[tr[r].l].sz + tr[tr[r].r].sz + 1;
            return r;
        }
    }
    void ins (int &rt , int x) // 加入新点
    {
        int rl , rr;
        spl (rt , x - 1 , rl , rr);
        rt = mrg (mrg (rl , get_new (x)) , rr);
    }
    int get (int p , int x) // 获取第 x 位的值
    {
        while (true)
        {
            push_down (p);
            int u = tr[tr[p].l].sz + 1;
            if (u == x)
                return tr[p].v;
            if (x >= u) p = tr[p].r , x -= u;
            else p = tr[p].l;
        }
        return -1;
    }
    int size (int rt) {return tr[rt].sz;} // 子树大小
} T;
int n , h , a[N];
int rt;
signed main ()
{
    ios::sync_with_stdio (0) , cin.tie (0) , cout.tie (0);
    cin >> n >> h;
    for (int i = 1;i <= n;i ++) cin >> a[i];
    int sl = -1 , f0 = a[1]; // sl 维护第一段的斜率，f0 维护 f[i][0]
    T.ins (rt , a[1]) , T.ins (rt , a[1]); // 加入绝对值函数
    for (int i = 2;i <= n;i ++)
    {
        int L , R , calc;
        T.splsz (rt , -sl , L , R); // 将其从斜率为 0 的段拆开
        T.spl (L , h , calc , L); // 原本横坐标 <= h 的拐点会被删除
        int lst = 0;
        for (int i = 1;i <= T.size (calc);i ++)
        {
            f0 += sl * (T.get (calc , i) - lst) , lst = T.get (calc , i);
            sl ++; // 删除一段（一个拐点），下一段斜率加一
        }
        f0 += sl * (h - lst);
        f0 += a[i];
        // 原本横坐标 <= h 的拐点计算新的 f[i][0]
        T.add (L , -h); // 左侧 -d
        T.add (R , h); // 右侧 +d
        rt = T.mrg (L , R);
        T.ins (rt , a[i]) , T.ins (rt , a[i]); // 加入绝对值函数
        sl --; // 加入后 a[i] 之前的斜率减一，从而第一段斜率也要减一
    }
    int lst = 0;
    for (int i = 1;i <= T.size (rt);i ++)
    {
        if (sl >= 0) break; // 仅计算最低点，之后会开始上升，不计入答案
        f0 += sl * (T.get (rt , i) - lst);
        lst = T.get (rt , i);
        sl ++;
    }
    cout << f0;
    return 0;
}

:::

:::success[Set]

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e6 + 5;
mt19937 rd (time (0));
struct Set
{
    int tag = 0;
    multiset <int> s;
    inline void insert (int x) {s.insert (x - tag);}
    inline void add (int x) {tag += x;}
    inline int front () {return (*s.begin ()) + tag;}
    inline int back () {return (*(-- s.end ())) + tag;}
    inline void pop_front () {s.erase (s.begin ());}
    inline void pop_back () {s.erase (-- s.end ());}
    inline int size () {return s.size ();}
    inline bool empty () {return s.empty ();}
} TL , TR;
int n , h , a[N];
int rt;
signed main ()
{
    ios::sync_with_stdio (0) , cin.tie (0) , cout.tie (0);
    cin >> n >> h;
    for (int i = 1;i <= n;i ++) cin >> a[i];
    int sl = -1 , f0 = a[1]; // sl 维护第一段的斜率，f0 维护 f[i][0]
    TL.insert (a[1]) , TR.insert (a[1]); // 加入绝对值函数
    for (int i = 2;i <= n;i ++)
    {
        int lst = 0;
        while (!TL.empty ())
        {
            int p = TL.front ();
            if (p > h) break;
            TL.pop_front ();
            f0 += sl * (p - lst);
            lst = p;
            sl ++;
        }
        f0 += sl * (h - lst);
        f0 += a[i];
        TL.add (-h);
        TR.add (h);
        int R = TR.front ();
        if (a[i] < R)
        {
            TL.insert (a[i]) , TL.insert (a[i]);
            TR.insert (TL.back ());
            TL.pop_back ();
        }
        else
        {
            TR.insert (a[i]) , TR.insert (a[i]);
            TL.insert (TR.front ());
            TR.pop_front ();
        }
        sl --;
    }
    int lst = 0;
    for (int p : TL.s)
    {
        if (sl >= 0) break;
        f0 += sl * (p + TL.tag - lst);
        lst = p + TL.tag;
        sl ++;
    }
    cout << f0;
    return 0;
}

:::

其它 Slope Trick

P13954 红黑树

题意

给定 n 个点的树，每个节点有红黑之一的颜色。对于每个节点 k，求最少翻转节点颜色的次数，使得以 k 为根的子树中任意节点 u 都满足：从 u 出发到其所有后代叶子节点的简单路径上所经过的黑色节点数量相等。

暴力

设 f_{u,i} 表示点 u 为根的子树中的叶子节点到 u 的路径上黑点个数均为 i，此时的最小修改数。

分两种情况考虑。

第一种，点 u 的颜色最终为红色，可得转移方程：

第二种，点 u 的颜色最终为黑色，可得转移方程：

两种情况取 \min 即可。

void dfs (int u)
{
    if (g[u].size () == 0)
    {
        f[u][0] = a[u];
        f[u][1] = !a[u];
        return ;
    }
    f[u][0] = a[u];
    for (int v : g[u]) dfs (v) , f[u][0] += f[v][0];
    for (int j = 1;j <= n;j ++)
    {
        int l1 = 0 , l2 = 0;
        for (int v : g[u]) l1 += f[v][j - 1] , l2 += f[v][j];
        f[u][j] = min (l1 + !a[u] , l2 + a[u]);
    }
}

可以使用 STL 优化以获取更多的分数。

优化

把 f_{u,i} 看成一个图像 f_u(x)，可以发现图像是一个凸包（因为最底层的 f_u 可以看作一个只有两个点的凸包，而凸包与凸包按位加也会是一个凸包）。设 \sum_{v\in \text{son}(u)} f_{v,x} 的图像为 F(x)， \sum_{v\in \text{son}(u)} f_{v,x-1} 的图像为 F'(x)。如下图所示：

例如这是一个 F(x) 的图像，那么将其向右移一个单位长度即可变成 F'(x) 的图像，如下：

设 (\sum_{v\in \text{son}(u)} f_{v,x})(x) 斜率为 0 的一段区间是 \left[L,R\right]。接下来分成两种情况。

s_u=0

此时 F'(x) 的图像会向上一个单位长度，如图：

发现当 x\le R 时 F(x) 会更小；否则，F'(x) 更小。而形成的新图像则是 F(x) 在 R 的位置插入了一条斜率为 1 的线段。

s_u=1

此时 F(x) 的图像会向上一个单位长度，如图：

发现当 x\le L 时 F(x) 会更小；否则，F'(x) 更小。而形成的新图像则是 F(x) 在 L 的位置添加了一条斜率为 -1 的线段。

那么就使用小根堆存储 f_u(x) 对应图像每一位的斜率，在最后插入新线段即可。