一次函数最优化数据结构

2025-12-26T21:17:50+08:00 | 13分钟阅读 | 更新于 2025-12-29T19:37:29+08:00

@
一次函数最优化数据结构

↑ 无法上吊之物，冲不走的大便、上勾拳免疫者、生锈海茄子、陆地咕蛹者、虎鲸把子肉、大白鲨放纵餐、狡猾的QQ肠、两栖大海参、斑点密布者、名字很凶的海底掠食者、太阳能量储存器、岸边巨大鹅卵石、忧伤的纺锥形物体、猫猫唇拥有者、薛定谔的脖子、海洋小肉丸、北极熊蒜酱伴侣、毛茄子、报废核潜艇、生气只能打自己。

简单介绍了李超树、凸包（记录了优化 dp 的三个经典 Trick）、KTT（TBD）。

1. 李超线段树

1.1 简介

李超树维护平面上的若干条直线，以查询某个横坐标上所有线段中的最大纵坐标。

1.2 算法过程

直线和线段在应用中本质相同，下面介绍的是维护线段的李超树。

实际上就是普通线段树的一种特例。在线段树中，维护的「信息」与「标记」分别为 区间内最大纵坐标的值 和 最优线段。设当前管辖的区间为 $[l,r]$。

其中，最优线段 在此处为：在 $x=\dfrac{l+r}{2}$ 处，纵坐标最大且覆盖该区间的线段。由于一次函数天生的单调性，易得 最优线段 在当前左右半某一部分，纵坐标一定不小于其他所有覆盖该区间的线段。

这个标记是容易记录的。对于定义域在 $[x_0,x_1]$ 上的一次函数 $y=kx+b$，只需先用线段树划分成 $\mathcal O(\log n)$ 个区间，然后对每个区间进行修改操作。修改过程中，判断新的线段是否优于当前区间，继续用更优线段更新子区间，这部分的复杂度也为 $\mathcal O(\log n)$。故一次新增线段的复杂度为 $\mathcal O(\log^2 n)$。

下面是模板题 P4097 【模板】李超线段树 / [HEOI2013] Segment 的核心代码，实现了加入线段以及某一横坐标上最大函数值查询功能。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

void add (int x0, int y0, int x1, int y1) {
    if (x0 == x1) line[++ tot] = {0, max (y1, y0)};
    else          line[++ tot] = {(y1 - y0) * 1.0 / (x1 - x0), y0 - (y1 - y0) * 1.0 / (x1 - x0) * x0};
}

int comp (double x, double y) {
    if (x - y > eps) return 1;
    if (y - x > eps) return -1;
    return 0;
}

double calc (int t, double x) {
    return line[t].first * x + line[t].second;
}

#define ls (u << 1)
#define rs (u << 1 | 1)
#define mid (l + r >> 1)

int tag[N + 5 << 2];

void upd (int u, int l, int r, int t) {
    int &tt = tag[u];
    int res = comp (calc (t, mid), calc (tt, mid));
    if (res == 1 || !res && t < tt) swap (tt, t);
    if (l == r) return ;
    int f1 = comp (calc (t, l), calc (tt, l)), f2 = comp (calc (t, r), calc (tt, r));
    if (f1 == 1 || !f1 && t < tt) upd (ls, l, mid, t);
    if (f2 == 1 || !f2 && t < tt) upd (rs, mid + 1, r, t); 
}

void update (int ql, int qr, int t, int u = 1, int l = 1, int r = MOD) {
    if (l >= ql && r <= qr) return upd (u, l, r, t);
    if (ql <= mid) update (ql, qr, t, ls, l, mid);
    if (mid < qr)  update (ql, qr, t, rs, mid + 1, r);
}

pdi Max (pdi x, pdi y) {
    return !comp (x.first, y.first) ? (x.second < y.second ? x : y) : (x.first > y.first ? x : y);
}

pdi query (int k, int u = 1, int l = 1, int r = MOD) {
    double res = calc (tag[u], k);
    pdi now = {res, tag[u]};
    if (l == r) return {res, tag[u]};
    if (k <= mid) return Max (now, query (k, ls, l, mid));
    else          return Max (now, query (k, rs, mid + 1, r));
}

1.3 李超树的拓展操作

动态开点李超树

和普通线段树一样。维护的直线的话空间复杂度是线性的，时间复杂度同前。

李超树合并

啊对，李超树也可以合并。合并的时间复杂度是线性对数，空间回收的空间复杂度可以做到线性。可持久化不带空间回收是线性对数。

以上两个拓展详见例题 2 的代码。

可持久化李超树

是的，和普通线段树一样，李超树也可以可持久化。

带删李超树

普通的李超树不能实现删除操作。必须搭配上 线段树分治 离线使用。

如果非要在线，那只能用平衡树维护凸包了，详见 2. 凸包。

1.4 例题

1. P4097 【模板】李超线段树 / [HEOI2013] Segment

板子。

2. CF932F Escape Through Leaf

理解题意比做题困难。

设 $f_u$ 表示 $u$ 跳到某一叶子结点的最小值，易得转移式：$f_u=\min\limits_{v\in\operatorname{subtree}(u)}(f_v+a_u\cdot b_v)$。

注意到这个东西是个一次函数，将 $f_u$ 视作 $y$，$f_v$ 视作 $b$，$b_v$ 视作 $k$，$a_u$ 视作为 $x$。得到的就是标准的一次函数方程：$y=\min (kx+b)$。

直接对于每个叶子节点建动态开点的李超树，然后用李超树自下而上合并，就做完了。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35


void update (int& u, int t, int l = -U, int r = U) {
    if (!u) return u = newnode (), tag[u] = t, void ();
    if (calc (tag[u], mid) > calc (t, mid)) swap (tag[u], t);
    if (l == r) return ;
    if (calc (t, l) < calc (tag[u], l)) update (ls[u], t, l, mid);
    if (calc (t, r) < calc (tag[u], r)) update (rs[u], t, mid + 1, r);
}

int merge (int u, int v, int l = -U, int r = U) {
    if (!u || !v) return u | v;
    update (u, tag[v], l, r);
    ls[u] = merge (ls[u], ls[v], l, mid);
    rs[u] = merge (rs[u], rs[v], mid + 1, r);
    return u;
}

ll query (int u, int t, int l = -U, int r = U) {
    if (!u) return 1e18;
    ll now = calc (tag[u], t);
    if (l == r) return now;
    if (t <= mid) now = min (now, query (ls[u], t, l, mid));
    else          now = min (now, query (rs[u], t, mid + 1, r));
    return now;
}

void dfs (int u, int fa) {
    if (u != 1 && g[u].size () == 1) return update (rt[u], add (b[u], ans[u] = 0)), void ();
    for (const auto& v : g[u]) {
        if (v == fa) continue;
        dfs (v, u);
        rt[u] = merge (rt[u], rt[v]);
    }
    update (rt[u], add (b[u], ans[u] = query (rt[u], a[u])));
}

2. 二维凸包

2.1 定义

凸多边形：内角范围都在 $[0,\pi]$ 范围内的简单多边形。 凸包：平面上有若干个点，构成点集 $X$，包含所有点的最小凸多边形就是这个点集的凸包。定义是这样的：在实数向量空间 $V$ 中，对于给定集合 $X$，所有包含 $X$ 的凸集的交集称为 $X$ 的凸包。

实际上你可以想象，用钉子打在墙上，再用一根橡皮筋去围住所有钉子，形成的就是一个凸包。

alt text

图源 Wikipedia。

2.2 求凸包

Andrew 算法

将所有点按照横坐标为第一关键字、纵坐标为第二关键字排序。那么第一个点和最后一个点必然是凸包内的点，而中间点构成上下凸壳。

从一个点逆时针出发，构成的轨迹总是向左拐的，一旦出现「右拐」，那么这一段一定不在凸包上。所以我们用单调栈维护凸包。

观察下面求凸包的过程。当前维护上凸壳最右端点为 $B$，与其相连的点为 $A$，下一个候选点为 $C$。若 $C$ 的方向向右旋转，即 $\vec{AB}\times\vec{BC}<0$ 时，弹出栈顶，继续检测。直至 $\vec{AB}\times\vec{BC}\ge 0$ 或者栈内只剩下一个元素。

图源 OI-Wiki。

Graham 扫描法

TBD。

2.3 动态维护凸包

CF70D Professor’s task

直接上板子，这里参考了 Elegia 的在 题解 中的写法。值得注意的是在维护上下凸壳时，分别只需保留相同横坐标上一个点。用 map 比 set 好写一点点。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71

set < pair <int, int> > tp, dw;

ll cross (int x, int y, int a, int b) {
    return x * 1ll * b - y * 1ll * a;
}

bool intop (int x, int y) {
    auto suff = tp.lower_bound ({x, -1e9});
    if (suff == tp.end ()) return false;
    if (suff -> first == x) return y <= suff -> second;
    if (suff == tp.begin ()) return false;
    auto prev = suff; prev --;
    return cross (suff -> first - prev -> first, suff -> second - prev -> second, x - prev -> first, y - prev -> second) <= 0ll;
}

bool indown (int x, int y) {
    auto suff = dw.lower_bound ({x, -1e9});
    if (suff == dw.end ()) return false;
    if (suff -> first == x) return y >= suff -> second;
    if (suff == dw.begin ()) return false;
    auto prev = suff; prev --;
    return cross (suff -> first - prev -> first, suff -> second - prev -> second, x - prev -> first, y - prev -> second) >= 0ll;
}

bool del_top (set < pair <int, int> > :: iterator it) {
    if (it == tp.begin ()) return false;
    auto jt = it, kt = it;
    -- jt; ++ kt;
    if (kt == tp.end ()) return false;
    if (cross (it -> first - jt -> first, it -> second - jt -> second, kt -> first - jt -> first, kt -> second - jt -> second) >= 0) 
        return tp.erase (it), true;
    return false;
} 

bool del_down (set < pair <int, int> > :: iterator it) {
    if (it == dw.begin ()) return false;
    auto jt = it, kt = it;
    -- jt; ++ kt;
    if (kt == dw.end ()) return false;
    if (cross (it -> first - jt -> first, it -> second - jt -> second, kt -> first - jt -> first, kt -> second - jt -> second) <= 0) 
        return dw.erase (it), true;
    return false;
} 

void ins_top (int x, int y) {
    if (intop (x, y)) return ;
    auto it = tp.lower_bound ({x, -1e9});
    while (it != tp.end () && it -> first == x) it = tp.erase (it);
    tp.insert ({x, y});
    it = tp.find ({x, y});
    auto jt = it;
    if (it != tp.begin ()) {
        -- jt;
        while (del_top (jt ++)) jt --;
    }
    if (++ jt != tp.end ()) while (del_top (jt --)) jt ++;
}

void ins_down (int x, int y) {
    if (indown (x, y)) return ;
    auto it = dw.lower_bound ({x, -1e9});
    while (it != dw.end () && it -> first == x) it = dw.erase (it);
    dw.insert ({x, y});
    it = dw.find ({x, y});
    auto jt = it;
    if (it != dw.begin ()) {
        -- jt;
        while (del_down (jt ++)) jt --;
    }
    if (++ jt != dw.end ()) while (del_down (jt --)) jt ++;
}

P2521 [HAOI2011] 防线修建

动态维护上凸壳周长，仅支持删除点以及查询操作。

类比 Andrew 静态求凸包的过程，这里采用平衡树按照横坐标排序维护上/下凸壳。这道题维护上凸壳，于是以上凸壳为例。

考虑插入新的点 $P$ 对凸壳的影响。如果该点被凸壳包含，无需操作。反之，设凸壳上横坐标在其之前的点为 $A$，之后点为 $B$。先向左后向右删掉不合法点：只要 $\vec{AP}\times\vec{AB}> 0$ 就一直删。

本题的周长维护注意以下几点：

  • 对于要删除的 $A,B,C$ 中 $B$，应减去 $\vert AB\vert +\vert BC\vert$ 后加上 $\vert AC\vert$。
  • 注意检查前后是否有点。
  • 需要考虑特殊修改同一横坐标的点时带来的变化。

另外，该题中删除操作难以做到，可以考虑离线下来反过来做。

2.4 闵可夫斯基和 (Minkowski Sum)

标准定义的闵可夫斯基和是对于两个点集描述的，即对于点集 $A$、$B$，二者的闵可夫斯基和 $C$： $$C=A+B=\{\boldsymbol{a}+\boldsymbol{b}\mid \boldsymbol{a}\in A,\boldsymbol{b}\in B\}$$

这里的 $\vert C\vert=\vert A\vert\times\vert B\vert$。

这里我们只讨论凸包的闵可夫斯基和，二者的闵可夫斯基和仅保留外侧的凸壳，如下。

mks1 mks2

上图难以溯源了，总之来自网络。仔细看这张图，你会发现初始两个凸包上的向量都在由绿边组成的凸包上出现过恰好一次。且新凸壳是在两个凸壳按照斜率排序后顺次连接而成。

  • 计算两个凸包的闵可夫斯基和

由于新凸壳的优秀性质，直接按照斜率排序即可。而凸壳具有天然的单调性，因此直接归并即可。假设两个凸壳分别为 $f,g$，复杂度即为 $\mathcal O(\vert f\vert + \vert g\vert)$。实际上，需要将二者先进行极角排序后再归并。

P4557 [JSOI2018] 战争

给出两个凸包 $A,B$，多次询问将 $A$ 按照 $\vec p$ 平移后是否与 $B$ 有交。

写出答案的贡献式，即 $\boldsymbol{a}+\vec p=\boldsymbol{b}\quad(\boldsymbol{a}\in A,\boldsymbol{b}\in B)$。

移项，得 $\vec p=\boldsymbol{b}+(-\boldsymbol{a})\quad(\boldsymbol{a}\in A,\boldsymbol{b}\in B)$，后者是 $B$ 与 $-A$ 的闵可夫斯基和，只要判断 $\vec p$ 是否在其中即可。这里 $(-A)$ 只需对 $A$ 内所有点的横纵坐标取相反数即可。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70

ll cross (Point x, Point y, Point z) {
    return Point (y.x - x.x, y.y - x.y) * Point (z.x - x.x, z.y - x.y);
}

void Andrew (int& n, Point* p) {
    sort (p + 1, p + n + 1, [&](const auto& x, const auto& y) { return x.x < y.x || (x.x == y.x && x.y < y.y); });
    stk[tp = 1] = 1;
    for (int i = 2; i <= n; i ++) {
        while (tp > 1 && cross (p[ stk[tp - 1] ], p[ stk[tp] ], p[i]) <= 0) -- tp;
        stk[++ tp] = i;
    }
    int now = tp;
    for (int i = n - 1; i; i --) {
        while (tp > now && cross (p[ stk[tp - 1] ], p[ stk[tp] ], p[i]) <= 0) -- tp;
        stk[++ tp] = i;
    }
    if (n > 1) -- tp;
    Point b[N];
    for (int i = 1; i <= n; i ++) b[i] = p[i];
    n = tp;
    for (int i = 1; i <= n; i ++) p[i] = b[stk[i]];
    p[n + 1] = p[1];
}

void Reorder (int& n, Point* p) {
    int pos = 1;
    for (int i = 2; i <= n; i ++) if (p[i].y < p[pos].y || (p[i].y == p[pos].y && p[i].x < p[pos].x)) pos = i;
    rotate (p + 1, p + pos, p + n + 1);
    p[n + 1] = p[1];
}

void Solve (int& n, Point* p, int cons = 0) {
    for (int i = 1; i <= n; i ++) {
        ll x, y; 
        scanf ("%lld%lld", &x, &y); if (cons) x = -x, y = -y; 
        p[i] = Point (x, y);
    }
    Andrew (n, p);
}

void Minkowski (int n, Point* A, int m, Point* B, Point* res, int& sz) {
    Reorder (n, A);
    Reorder (m, B);

    vector <Point> dif1 (n + 5, Point ()), dif2 (m + 5, Point ());
    for (int i = 1; i <= n; i ++) dif1[i] = A[i + 1] - A[i];
    for (int i = 1; i <= m; i ++) dif2[i] = B[i + 1] - B[i];
    res[sz = 1] = A[1] + B[1];
    int a = 1, b = 1;
    while (a <= n && b <= m) {
        ++ sz;
        if (dif1[a] * dif2[b] >= 0) res[sz] = res[sz - 1] + dif1[a ++];
        else                        res[sz] = res[sz - 1] + dif2[b ++];
    }
    while (a <= n) ++ sz, res[sz] = res[sz - 1] + dif1[a ++]; 
    while (b <= m) ++ sz, res[sz] = res[sz - 1] + dif2[b ++]; 
}

int check (Point vec) {
    if (vec * minks[2] > 0 || vec * minks[sz] < 0) return 0;
    if (vec * minks[2] == 0 && vec.size() > minks[2].size()) return 0;
    if (vec * minks[sz] == 0 && vec.size() > minks[sz].size()) return 0;
    int l = 2, r = sz - 1, ans = 1;
    while (l <= r) {
        int mid = l + r >> 1;
        if (minks[mid] * vec > 0) ans = mid, l = mid + 1;
        else                      r = mid - 1;
    }
    return (minks[ans + 1] - minks[ans]) * (vec - minks[ans]) >= 0;
}

这里的 Reorder 是为了使凸包首位为左下角的点，使其称为极角排序后的顺序。

P8101 [USACO22JAN] Multiple Choice Test P

P4118 [Ynoi2018] 末日时在做什么？有没有空？可以来拯救吗？

  • 优化 dp

闵可夫斯基和的优秀性质可以放在全凸壳上，当然也可以用在半凸壳上。这和上述过程是类似的。考虑两个半凸壳 $f,g$，我们要求 $h_i=\min\limits_{j}(f_j+g_{i-j})$，即 $f$ 与 $g$ 的 $(\min,+)$ 卷积。发现这就是对两个点集求闵可夫斯基和，直接求出两个下凸壳的闵可夫斯基和的下凸壳即可。$(\max,+)$ 卷积运算也是类似的。

P11459 [USACO24DEC] It’s Mooin’ Time P

ABC383G Bar Cover

P9962 [THUPC 2024 初赛] 一棵树

2.5 wqs 二分

通常用于优化 dp，是一种凸优化方法，可以有效地降低 dp 维度。

通常带有的问题标签为「恰好选 $k$ 个」，即限物品个数的相关 dp。假设 $f(i)$ 为恰好选 $i$ 个物品的答案，当 $f$ 是凸的时候，就可以使用 wqs 二分了。通常可以通过 打表、猜测（当 $nk$ 做不了时）、比较任意 $\dfrac{f(i+1)+f(i-1)}{2}$ 与 $f(i)$ 大小等方式得到。

我们构想一个 $f$ 上的凸包，用斜率为 $k$ 的直线去切。假设切点为 $(i,f(i))$，那么纵截距 $b_k=f(i)-i\cdot k\iff f(i)=i\cdot k+b_k$。实际意义即将所有物品价值减去 $k$ 后，恰选 $i$ 个物品的最优解。注意凸包上切线的性质，在所有斜率相同的直线中，该直线纵截距最大。由 $f(i)=i\cdot k+b_k$ 得，此时 $f(i)$ 为所求。

介于凸包斜率的单调性，于是考虑二分这个斜率，复杂度降为 $\mathcal O(P(n)\log n)$，其中 $P(n)$ 是求切点（即逆向上述过程）的复杂度。

注意一点，在初学时，可能认为这个凸包是事先求好进而难以理解其表述含义。实际上，在固定一个斜率 $k$ 后，我们可以较为容易地求出该斜率下选择物品的最优数量，又由凸性，进而可在可观的复杂度内求出所求。

三（及以上）点共线的处理

其实不用管，只用钦定越多越好还是越少越好，然后在二分中判一下即可。细节见例题 Tree I 的排序规则。

P2619 [国家集训队] Tree I

给出 $m$ 条边，每条边有权有黑白。求恰选 $k$ 条白边的最小生成树权值和。

这里讲几个实现的细节。

  • 考虑共线情况，此时几个点斜率相同，我们不妨选横坐标最大者。体现在更新时就是将答案减去 $k$ 条边的多余贡献。而最终必然会更新到合法状态，故直接合法覆盖答案即可。
  • 根据最优性，代价必然单增，体现在图形上即斜率递增，故这里的答案呈下凸壳。
  • 注意二分 check 是对 $l$ 还是对 $r$ 更新。考虑当前选择是「罚款」还是「奖励」（即 $f(i)=b_k\pm i\cdot k$），对于统计的 $+$，合法时应更新 $r$（即奖励多了）。反之亦然。
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

bool operator < (edge& x, edge& rhs) const {
    return x.w == rhs.w ? x.typ < rhs.typ : x.w < rhs.w; // 优先选白边使得共线时横坐标最大。
}

pair <int, int> check (int mid) {
    auto e = :: e;
    for (auto& [u, v, w, typ] : e) if (!typ) w += mid;
    sort (e.begin (), e.end ());
    dsu.init (n);
    int cnt = 0, ed = 0, res = 0;
    for (const auto& [u, v, w, k] : e)
        if (dsu.merge (u, v)) res += w, cnt += !k, ed ++;
        else if (ed == n - 1) break ;
    return make_pair (res, cnt); 
}

void binary_search () {
    int l = -150, r = 150;
    while (l <= r) {
        int mid = l + r >> 1;
        auto [res, cnt] = check (mid);    
        if (cnt >= k) ans = res - k * mid, l = mid + 1;
        else          r = mid - 1; 
    }
}

P6246 [IOI 2000] 邮局 加强版 加强版

ARC168E Subsegments with Large Sums

2.6 Slope Trick

满足如下条件的两个函数 $f,g$：

  • 连续的。
  • 分段线性函数。
  • 具有凸性。

假设函数 $f$ 的转折点为 $L_f$，则对于函数 $h=f+g$，$L_h=L_f\cup L_g$。

具体的，我们维护拐点多重集来维护整个凸壳。假设已知当前凸包拐点不重集合 ${c_1,c_2,\cdots,c_n}\quad(c_1\le \cdots\le c_n)$ 表示了分段为 $n+1$ 的函数，第 $i$ 个元素数量为 $a_i$。设最左测直线的斜率为 $k$，那么第 $2$ 条直线的斜率为 $k+a_1$，第 $i+1$ 条线段的斜率为 $k+\sum\limits_{1\le j\le i}a_j$。

CF713C Sonya and Problem Without a Legend

给出序列 $a_i$，一次操作可以任选 $a_i\gets a_i\pm 1$。最小化操作次数，使该序列严格单增。

若非严格单增，显然取值在原序列中。令 $a_i\gets a_i-i$，发现就能实现。

设 $f_{i,j}$ 表示前 $i$ 个元素不降，第 $i$ 个元素等于 $j$ 的最优解。有 $f_{i,j}=\min\limits_{k\le j}f_{i-1,k}+\vert j-a_i\vert$，令 $g_{i,j}=\min\limits_{k\le j}f_{i-1,k}$，容易用离散化+前缀和优化到 $\mathcal O(n^2)$。

实际上原题已经做完了，但是 Slope Trick 还没讲。现在来细说一下。

设 $F_i(x)=f_{i,x}$，$G_i(x)=g_{i,x}$。容易从 $i=1$ 时归纳得到 $G_i(x),F_i(x)$ 均为下凸的函数。且有如下的良好性质：

  • $G_i(x)$ 的最后一条直线水平，这是前缀最小值带来的。
  • $F_i(x)$ 的最后一条直线斜率为 $1$，这是 $\vert x-a_i\vert$ 最后一条直线斜率为 $1$ 且 $G_i(x)$ 最后的直线水平相加得来。

综上二点，考虑维护 $G_i(x)$ 的拐点集合 $S$。对于新加入的 $a_k$，将 $\{a_k,a_k\}$ 插入 $S$。插入两个的原因是，加上 $\vert x-a_i\vert$ 会使得 $x<a_i$ 斜率减 $1$，使 $x>a_i$ 斜率加 $1$，即斜率差增加 $2$。此时变为 $F_i(x)$ 的拐点集合，只要删掉最大的横坐标的点即可（相当于给最后一条直线斜率加 $1$ 再减 $1$。）。删除后最右边的拐点后接的水平直线即最小值所在。于是考虑用大根堆维护就做完了。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

ll ans = 0;
priority_queue <int> pq;
for (int i = 1; i <= n; i ++) {
    int a; scanf ("%d", &a);
    a -= i; 
    if (!pq.empty () && pq.top () >= a) ans += pq.top () - a;
    pq.push (a);
    pq.push (a);
    pq.pop ();
}
printf ("%lld\n", ans);

这里注意的细节是 push 和 pop 的顺序，大根堆的首个元素的意义是 $G_{i-1}(x)$ 的最优 $x$，当前的 $a_i$ 如果大于 $x$，显然选 $a_i$ 即可，反之差一下即可。

P4272 [CTSC2009] 序列变换

给出长度为 $n$ 的不降序列 $X_i\in[1,Q]$，$A$ 与 $B$。找到一组绝对值和最小的序列 $\delta_i$，使得 $Y_i=X_i+\delta_i \in[1,Q]$ 不降且 $\forall i\in[]Y_{i+1}-Y_{i}\in[A,B]$。

$n\le 5\times10^5$。

设 $f_{i,j}$ 表示前 $i$ 个数符合条件，$Y_i=j$ 的 $\vert\delta_i\vert$ 最小和。有转移：$f_{i,j}=\min\limits_{j-k\in[\max(j-B,1),j-A]} f_{i-1,j}+\vert j-X_i\vert$。用滑动窗口容易做到 $\mathcal O(nQ)$。

考虑进一步优化，设 $g_{i,j}=\min\limits_{k\in[\max(1,j-B),j-A]}f_{i,k}$，则 $f_{i,j}=g_{i,j}+\vert j-X_i\vert$。当 $i=1$ 时，$f_{i,j}$ 关于 $j$ 具有下凸性，进而 $g_{i,j}$ 关于 $j$ 有凸性。据此归纳可知对于任意 $i$，$f_{i,j},g_{i,j}$ 均为下凸的。

接下来考虑 $f,g$ 凸包之间的相互转化，设 $F_{i}(x)=f_{i,x},G_{i}(x)=g_{i,x}$。

假设已经维护出 $G_{i-1}$ 的凸包，转化成 $F$ 的凸包是简单的。具体的，维护对顶堆，表示斜率为 $0$ 的直线的左右两部分。

P3642 [APIO2016] 烟花表演

3. KTT (Kinetic Tournament Tree)

没遇到，不会，不写。

© 2025 - 2026 Toorean's Blog

🌱 Powered by Hugo with theme Dream.

About Me

来自安徽合肥，目前在合肥市第一中学读高中。

弱小的 OIer，或许就要退役了呢？

QQ: 3427463298 Email: phantomxbee@outlook.com