Dyd's Blog

He who has a strong enough why can bear almost any how.

优化dp2

Posted on Edited on In
Symbols count in article: 16k Reading time ≈ 15 mins.

然而我 dp 废的一比（三羊开泰）

优化dp2

上回链接：优化dp

这次目标主要介绍斜率优化，它是利用单调性对转移进行优化

斜率优化

歪果仁喜欢叫凸包/凸壳优化（ convex hull trick ）

上次我我们说了，对于 1D/1D 模型：
$$
d[i] = \min_{l(i) \le j \le r(i)} (d[j] + val(i, j))
$$
如果 $val(i, j)$ 的的每一项仅与 $i, j$ 中一个有关，就可以考虑单调队列，那么，如果 $val(i, j)$ 包括了 $i, j$ 的乘积（即和它们同时相关的量），我们就可以考虑斜率优化

斜率优化有两种形式，就我个人而言，比较喜欢先把 dp 方程写出来，然后考虑决策 $j$ 优于决策 $k$ 的条件，把条件化成
$$
\frac{y(j) - y(k)}{x(j) - x(k)} < k
$$
这里 $<$ 可以换，把外层循环都当常量， $k$ 是常数， $x(t), y(t)$ 是仅和 $t$ 有关的函数，这个就是斜率优化的第一种形式，如果是巨佬，一眼就可以看出（或者带几个点算出）它是上凸/下凸然后打代码了

但我比较弱，这个只能用来帮助打代码，只好继续化，在得到了形式一后，我们反回去看 dp 方程，把 $\min (\max)$ 去掉，化为斜率优化的第二种形式
$$
y(j) = k \times x(j) + d[i]’
$$
这里 $d[i]’$ 是只关于 $d[i]$ 的东西（可以通过它直接得到 $d[i]$ ）， $y(t), x(t), k$ 就和形式一一样（所以我化出形式一的目的其实就是为了指导如何化形式二，因为蒟蒻一般无法一眼看穿如何化形式二），然后我就用形式二来斜率优化

具体地，把问题化为对一条斜率为 $k$ 的直线尝试去过点 $(x(j), y(j))$ ，最大/小化直线的截距，我们发现只要维护点集的凸包即可，一般用单调队列实现

实现代码时最好看着这两个形式打（利用它们帮助你明确细节、条件），然后期待自己 rp 够好吧（如果您是巨佬当我没说）

值得一提的是，对于形式一，巨佬可以直接取几个点就看出上凸/下凸/无法优化，但对于用形式二的蒟蒻来说，只好记结论了：

可以简单斜率优化的条件是形式二中的 $k$ 和 $x(t)$ 单调，单调递增/递减（或者 $\min$ / $\max$ ）对应下凸/上凸，这样有一个 $O(n)$ 就可以优化为 $O(1)$ ；而当 $k$ 和 $x(t)$ 有一者不单调时，我们优先考虑改方程（倒着 dp ，重设状态等）来保证 $x(t)$ 单调（要保证新决策横坐标大于/小于之前所有决策），并用二分，将 $O(n)$ 优化为 $O(\log n)$ ；最麻烦的是 $k$ 和 $x(t)$ 都不单调，这就只有动态维护，时间和题目要求以及选取的数据结构有关，具体可以看下面的例题

例题六

Cats Transport

题意

有 $m \le 10^5$ 只猫分布在 $n \le 10^5$ 座山上，第 $i$ 只猫在山 $h_i$ 且会在 $t_i \le 10^9$ 时间下到山脚，然后一直等着，两个山之间的距离已知且 $\le 10^4$ ，现在在第一座山脚有 $p \le 100$ 个铲屎官，速度为 $1$ ，每个铲屎官在你安排的时间出发（每个人出发时间可以不同，出发时间可以为负数），从山 $1$ 走到山 $n$ ，中通遇到在山脚的猫就带走它，要求你最小化猫的等待时间

思路

首先，什么距离、速度、时间很麻烦，我们先对每只猫计算一个 $a_i = t_i - \sum_{j = 1}^{h_i} d_j$ ，表示“如果一个铲屎官想接走第 $i$ 只猫，它必须在 $a_i$ 时刻之后出发”，不难发现如果出发时间为 $x$ ，猫就会等待 $x - a_i$ 的时间，然后就不管题目中的 $d, t$ 和 $h$ 了

我们先对 $a_i$ 从小到大排序，排完后铲屎官接走的猫一定是连续的，贪心可知，一定存在一种最优解满足每位铲屎官都对应一只刚好接走的猫，即对应一个 $a_i$ （简证 口胡 ：若有为铲屎官没有刚好接走的猫，就让它早点出发，使他接的最后一只猫使被刚好接走，这样答案一定不会变差）

于是考虑第 $x$ 个铲屎官刚好接走猫 $i$ （即在 $a_i$ 出发），上一个人搞好接走猫 $j$ ，那么这个人可以接走猫 $j + 1 \sim i$ ，代价为 $\sum_{k = j + 1}^i a_i - a_k$ ，不妨对 $a_i$ 求个前缀和，然后 $\sum_{k = j + 1}^i a_i - a_k = (i - j)a_i - (sum[i] - sum[j])$ ，设 f[i, j] （ $d$ 又被用了呜呜呜）表示“前 $i$ 个铲屎官带走了前 $j$ 只猫，最小的等待时间”，易得：
$$
f[i, j] = \min_{0 \le k < j} (f[i - 1, k] + (j - k) * a_j - (sum[j] - sum[k]))
$$
直接转移是 $O(pm^2)$ 的，外层 $i$ 当常量就是一个 1D/1D ，有 $val(j, k) = (j - k) * a_j - sum[j] + sum[k]$ ，发现存在乘积量 $(j - k) * a_j$ ，考虑斜率优化

巨佬们可以一眼看穿的就跳过吧，这里是蒻蒟痛苦的推式子：

考虑决策 $q$ 优于决策 $k$ 的条件（下面省略第一维）：
$$
\begin{aligned}
& f[k] + (j - k) * a_j - sum[j] + sum[k] > f[q] + (j - q) * a_j - sum[j] + sum[q] \\
\Rightarrow & f[k] + -k * a_j + sum[k] > f[q] + -q * a_j + sum[q] \\
\Rightarrow & a_j > \frac{(f[q] + sum[q]) - (f[k] + sum[k])}{q - k}
\end{aligned}
$$
于是形式一就有了，然后再化方程就简单了：
$$
\begin{aligned}
& f[i, j] = \min_{0 \le k < j} (f[i - 1, k] + (j - k) * a_j - (sum[j] - sum[k])) \\
\Rightarrow & f[i, j] = f[i - 1, k] + j * a_j - k * a_j - sum[j] + sum[k] \\
\Rightarrow & (f[i - 1, k] + sum[k]) = (a_j) \times (k) + (f[i, j] - a_j * j + sum[j]) \\
\end{aligned}
$$
大家可以对比两个形式和上面给的两个形式的一般式，不难发现它们间的联系

无论如何，式子是推出来了，现在来看单调性，首先 $a_j$ 是排好序的，显然单调递增，而那个 $k$ 是我们顺序枚举的，单调性也显然，剩下的就是打代码了……时间复杂度 $O(pm)$

代码

  1. 仔细看看代码是不是有很多地方和形式一/二有点像？这就是我说的“帮助代码实现”
  2. 为了提高精度建议开 double ，也可以化除为乘
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
#include <bits/stdc++.h>
#define LL long long
#define STC static
using namespace std;
const int N = 1e5 + 5, P = 100 + 5;
int n, m, p, q[N];
LL f[P][N], sum[N], a[N], d[N];
LL Y(int i, int x){ return f[i][x] + sum[x]; }
LL X(int x){ return x; }
LL calc(int i, int j, int k){ return Y(i, k) - X(a[j]) * k; } //计算截距i,j,k含义类似形式二
bool check(int i, int a, int b, int c){ return (Y(i, b) - Y(i, c)) * (X(a) - X(b)) > (Y(i, a) - Y(i, b)) * (X(b) - X(c)); } //检查a优于b,类似形式一,化乘为除
int main()
{
    scanf("%d %d %d", &n, &m, &p);
    if (p >= m) return puts("0"), 0;
    for (int i = 2; i <= n; ++i) scanf("%lld", &d[i]), d[i] += d[i - 1];
    for (int i = 1, h, t; i <= m; ++i) scanf("%d %d", &h, &t), a[i] = t - d[h];
    sort(a + 1, a + 1 + m);
    for (int i = 1; i <= m; ++i) sum[i] = sum[i - 1] + a[i];
    for (int i = 1; i <= m; ++i) f[1][i] = a[i] * i - sum[i]; //先把1算了
    for (int i = 2, j, l, r; i <= p; ++i)
        for (q[l = r = 1] = 0, j = 1; j <= m; ++j) //0也是一个决策点
        {
            for (; l < r && calc(i - 1, j, q[l + 1]) < calc(i - 1, j, q[l]); ++l); //不优排除，注意至少要保证队列中有一个数,故l<r
            f[i][j] = f[i - 1][q[l]] + a[j] * (j - q[l]) - (sum[j] - sum[q[l]]);
            for (; l < r && check(i - 1, j, q[r], q[r - 1]); --r); //保留斜率更优的
            q[++r] = j;
        }
    printf("%lld\n", f[p][m]);
    return 0;
}

例题七

任务安排3

题意

给定 $n \le 3 \times 10^5$ 个任务，要求从时刻 $0$ 开始顺序执行，第 $i$ 个任务耗时 $-512 \le t_i \le 512$ ，有一个机器执行任务，将任务分成若干段，每一段完成耗时就是该段 $t_i$ 之和，而机器开始每段之前要消耗 $S \le 512$ 的启动时间，一个任务的完成时刻就是所在段的完成时刻，最后的费用就是每个任务的完成时刻乘一个系数 $c_i \le 512$ 然后求和，现在求最小费用

思路

首先求出 $t_i$ ， $c_i$ 的前缀和记为 $sum_t[], sum_c[]$ ，定义 d[i, j] 表示“把前 $i$ 个任务分成 $j$ 段最小费用”，方程显然：
$$
d[i, j] = \min_{0 \le k < i} (d[k, j - 1] + (S * j + sum_t[i]) * (sum_c[i] - sum_c[k]))
$$
时间为 $O(n^3)$ ，完全无法接受，考虑到就算把 1D/1D 优化为 $O(1)$ 时间也无法接受，说明要剪去一维状态

我们发现题目并没有要求分成多少段，我们在状态中记录段数完全是为了计算代价，而每一次启动的代价都会累计到此后所有的任务中，用费用提前计算的思想，直接在启动时就把后面的代价累计了，这样就剪去了一维，定义 d[i] 表示“把前 $i$ 个任务分成若干段最小费用”，方程：
$$
d[i] = \min_{0 \le j < i} (d[j] + sum_t[i] * (sum_c[i] - sum_c[j]) + S * (sum_c[n] - sum_c[j]))
$$
时间为 $O(n^2)$ ，考虑 1D/1D 优化， $val(i, j) = sum_t[i] * (sum_c[i] - sum_c[j]) + S * (sum_c[n] - sum_c[j])$ 包含 $i, j$ 乘积，考虑斜率优化，设决策 $k$ 优于 $j$ 有：
$$
\begin{aligned}
& d[j] + sum_t[i] * (sum_c[i] - sum_c[j]) + S * (sum_c[n] - sum_c[j]) > d[k] + sum_t[i] * (sum_c[i] - sum_c[k]) + S * (sum_c[n] - sum_c[k]) \\
& d[j] - (S + sum_t[i]) * sum_c[j] > d[k] - (S + sum_t[i]) * sum_c[k] \\
& (S + sum_t[i]) > \frac{d[k] - d[j]}{sum_c[k] - sum_c[j]}
\end{aligned}
$$
于是得到形式二为：
$$
(d[j]) = (S + sum_t[i]) \times (sum_c[j]) + (d[i] - sum_t[i] * sum_c[i] - S * sum_c[n])
$$
现在来看单调性， $sum_c[j]$ 的单调性显然，但是由于 $t_i$ 可以为负数， $S + sum_t[i]$ 不具有单调性，完蛋，这就是 $k$ 不单调但 $x(t)$ 单调的情况啊

但幸好 $x(t)$ 还是单调的，我们来思考 $k$ 不单调的影响：如果 $k$ 是单调的，由形式一可知我们只需保留凸壳上两点连线斜率大于 $k$ 的部分，而最优决策就一定是队头，因为队头的下一个点被删去，说明它的斜率由 $<k$ 变为 $>k$ ，则队头就是变化点，也就是最优决策点；但是 $k$ 不单调了，所以我们不能只保留凸壳上两点连线斜率大于 $k$ 的部分，而要维护整个凸壳，并最优决策点也不在是队头了，需要在队列中二分一个点，使得它和左侧点斜率 $<k$ ，而和右侧点斜率 $>k$

时间复杂度 $O(n \log n)$

代码

注意 long long 相乘要开 int128 

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
#include <bits/stdc++.h>
#define LL long long
#define I128 __int128
using namespace std;
const int N = 3e5 + 5;
LL sumc[N], sumt[N], d[N];
int q[N], l, r;
LL Y(int x){ return d[x]; }
LL X(int x){ return sumc[x]; }
bool check1(int a, int b, LL k){ return Y(a) - Y(b) >= I128(k) * (X(a) - X(b)); } //判断a,b的斜率大于等于k
bool check2(int a, int b, int c){ return I128(Y(b) - Y(a)) * (X(c) - X(b)) >= I128(Y(c) - Y(b)) * (X(b) - X(a)); } //比较斜率,维护凸包
int find(int i, LL k)
{
    if (l == r) return q[l];
    int ll = l, rr = r, mid, res;
    while (ll <= rr)
    {
        mid = ll + rr >> 1;
        if (check1(q[mid + 1], q[mid], k)) rr = (res = mid) - 1;
        else ll = mid + 1; 
    }
    return q[res];
}
int main()
{
    int n, s;
    scanf("%d %d", &n, &s);
    for (int i = 1, t, c; i <= n; ++i)
    {
        scanf("%d %d", &t, &c);
        sumc[i] = sumc[i - 1] + c, sumt[i] = sumt[i - 1] + t;
    }
    q[l = r = 1] = 0;
    for (int i = 1, p; i <= n; ++i)
    {
        d[i] = d[p = find(i, s + sumt[i])] - (s + sumt[i]) * sumc[p] + sumt[i] * sumc[i] + s * sumc[n];
        for (; l < r && check2(q[r - 1], q[r], i); --r);
        q[++r] = i; 
    }
    printf("%lld\n", d[n]);
    return 0;
}

例题八

货币兑换

题意

有两种金卷 $A, B$ ，已知接下来 $n \le 10^5$ 天每天两种金卷的价格 $A_i, B_i \le 10$ ，用户的账户上有三个实数： $a, b, c$ ，分别表示金卷 $A, B$ 的数量和 RMB （软妹币）的数量，用户可以进行两种操作（同一天可以多次操作）：

  1. 提供一个实数 $op \in [0, 100]$ ，然后将 $op\%$ 的 $A, B$ 卷按当天的价格换成 RMB
  2. 提供一个实数 $op$ 表示用 $op$ 元 RMB 买入 $A, B$ 卷，第 $i$ 天买入的 $A, B$ 卷比为 $R_i \in (0, 100]$

现在，假设你第一天有 $S \le 10^9$ 元且没有任何金卷，问第 $n$ 天时你账户中最多有多少 RMB ，保证最后答案 $\le 10^9$ 保留 $3$ 位小数

思路

首先明确一个点：必然存在一种最优的买卖方案，使得每次买进操作使用完所有的人民币，每次卖出操作卖出所有的金券

证明很简单，如果最优解在某天买入了一部分卷，一定是因为买它最优，而继续买和买入一部分的“优越性”相同（因为参数都没变），所有继续买一定优于其它决策；卖出同理

然后我们来考虑 dp ，由于实数不好作为状态，定义 d[i] 为“第 $i$ 天最多得到的钱数”，把实数放到转移里，转移分两种：

  1. 第 $i$ 天不卖出金卷，则 d[i] = max(d[i], d[i - 1])

  2. 第 $i$ 天卖出金卷，设上一次买入（一定是花完了所有 RMB 的）是在第 $j$ 天，有：
    $$
    d[i] = \max _{1 \le j < i} (\frac{d[j]}{A _j * R _j + B _j} * R _j * A _i + \frac{d[j]}{A _j * R _j + B _j} * B _i)
    $$

第一种转移很好搞，问题在第二种，发现包含 $i, j$ 的乘积，于是考虑斜率优化

决策 $k$ 优于决策 $j$ 当且仅当：
$$
\begin{aligned}
& \frac{d[j]}{A _j * R _j + B _j} * R _j * A _i + \frac{d[j]}{A _j * R _j + B _j} * B _i < \frac{d[k]}{A _k * R _k + B _k} * R _k * A _i + \frac{d[k]}{A _k * R _k + B _k} * B _i \\
& \frac{d[j] * R _j}{A _j * R _j + B _j} * \frac{A _i}{B _i} + \frac{d[j]}{A _j * R _j + B _j} < \frac{d[k] * R _k}{A _k * R _k + B _k} * \frac{A _i}{B _i} + \frac{d[k]}{A _k * R _k + B _k} \\
& \frac{d[j]}{A _j * R _j + B _j} - \frac{d[k]}{A _k * R _k + B _k} < (\frac{d[k] * R _k}{A _k * R _k + B _k} - \frac{d[j] * R _j}{A _j * R _j + B _j}) * \frac{A _i}{B _i} \\
& \frac{\frac{d[j]}{A _j * R _j + B _j} - \frac{d[k]}{A _k * R _k + B _k}}{\frac{d[k] * R _k}{A _k * R _k + B _k} - \frac{d[j] * R _j}{A _j * R _j + B _j}} < \frac{A _i}{B _i} \\
& \frac{\frac{d[k]}{A _k * R _k + B _k} - \frac{d[j]}{A _j * R _j + B _j}}{\frac{d[k] * R _k}{A _k * R _k + B _k} - \frac{d[j] * R _j}{A _j * R _j + B _j}} > - \frac{A _i}{B _i} \\
\end{aligned}
$$
相信你和我一样看见这个式子就脑壳疼，所以我们设 $Y(t) = \frac{d[t]}{A _t * R _t + B _t}, X(t) = \frac{d[t] * R _t}{A _t * R _t + B _t}$ ，就很明显是形式一了：
$$
\frac{Y(k) - Y(j)}{X(k) - X(j)} > - \frac{A _i}{B _i}
$$
于是就推得形式二：
$$
Y(j) = - \frac{A _i}{B _i} \times X(j) + \frac{d[i]}{B _i}
$$
奈斯~，似乎维护一个最大截距就结束了（注意本题是维护上凸壳了，上两题都是下凸壳）？来检查一下单调性， what’s up ， $X(j) = \frac{d[j] * R _j}{A _j * R _j + B _j}$ 有个寂寞的单调性，再看 $- \frac{A _i}{B _i}$ ，更没有了，我们遇到了两个都没有单调性的情况

这下完蛋， $k = - \frac{A _i}{B _i}$ 不具有单调性还好，可以像例七一样二分决策位置，但 $X(j)$ 没有单调性，这意味着我们凸包上的点不是按照横坐标排好序的，当前点可能不是插在凸包最右（左）边，而是插到凸包的中间已经维护好的部分里，这意味着我们必须动态维护凸包，对于本题来，说如果对于点 $j$ 左边的线斜率小于当前 $k$ ，显然用左边的点截距更大（画图一下就看出来了）；如果右边的线斜率大于当前 $k$ ，那么用右边的点更优；最后最优决策点左边直线斜率 $> k$ （在爬升），右边斜率直线斜率 $< k$ （在下降）

下面介绍三种不同数据结构维护这个凸包，其中前两种比较常用，各有优劣，第三种不太常见，但有些题目用上会有奇效

平衡树维护

把凸包上的点维护成一棵按照 $X(j)$ 排序的平衡树，每个点维护其在凸包上左边直线的斜率 $lk$ 和右边的直线斜率 $rk$ 每次插入新点 $x$ 时：

  1. 先将新点旋转到根
  2. 寻找其左边最后一个可以与其构成凸包的点，并把之间的不能构成凸包的点删除（直接把该点旋转到 $x$ 下面，然后删除该点的左/右儿子即可），计算出 $lk$ （如何判断是否构成凸包：对于当前找到的点 $t$ ，如果 $lk(t)$ 大于直线 $t - x$ 的斜率，并且点 $t, x$ 之间有不在凸包内的节点，就说明要找的点在 $t, x$ 之间，就往右走）
  3. 同理维护右边
  4. 如果发现这个点在原来的凸包内，即 $lk(x) < rk(x)$ ，直接删除该点

平衡树的有点是好想、好理解，且时间好算，缺点当然是码量和常数（但其实三种方法的常数差不多）

为了方便拓展和迁移，不用常数小的 SBT 而用拓展性强（并且不用打 push_up ）的 splay 打代码前，我又想起蒟蒻我当初打脸的话：“我的 splay 常数小”

时间复杂度 $O(n \log n)$

代码：

其实为了卡常可以存下 $X(j), Y(j)$ ，防止每次都算，但我懒

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
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
#include <bits/stdc++.h>
#define DB double
using namespace std;
const int N = 1e5 + 5;
const DB eps = 1e-9, INF = 0x3f3f3f3f;
int n;
DB d[N];
struct Day{ DB a, b, r; }day[N];
int cmp(DB x, DB y){ return fabs(x - y) < eps ? 0 : (x > y ? 1 : -1); }
DB Y(int x){ return d[x] / (day[x].a * day[x].r + day[x].b); }
DB X(int x){ return Y(x) * day[x].r; }
DB K(int a, int b){ return !cmp(X(a), X(b)) ? -INF : (Y(b) - Y(a)) / (X(b) - X(a)); }
namespace Splay
{
    int rt, tot;
    struct Node
    {
        int fa, ch[2], id;
        DB lk, rk;
    } tr[N];
    #define fa(x) tr[(x)].fa
    #define ch(x) tr[(x)].ch
    #define lk(x) tr[(x)].lk
    #define rk(x) tr[(x)].rk
    #define id(x) tr[(x)].id
    void rot(int x)
    {
        int y = fa(x), z = fa(y), k = ch(y)[1] == x;
        ch(z)[y == ch(z)[1]] = x, fa(x) = z;
        ch(y)[k] = ch(x)[k ^ 1], fa(ch(x)[k ^ 1]) = y;
        ch(x)[k ^ 1] = y, fa(y) = x;
    }
    void splay(int x, int k)
    {
        for (int y, z; fa(x) != k; rot(x)) if ((z = fa(y = fa(x))) != k) (ch(y)[1] == x) ^ (ch(z)[1] == y) ? rot(x) : rot(y);
        if (!k) rt = x;
    }
    int find(int x, DB k) //寻找最优解,当前斜率为k
    {
        if (!x || cmp(lk(x), k) == 1 && cmp(rk(x), k) == -1) return x;
        return (cmp(lk(x), k) == -1 ? find(ch(x)[0], k) :  find(ch(x)[1], k));
    }
    int pre(int x)
    {
        int y, res;
        for (y = ch(x)[0], res = y; y; )
            if (cmp(lk(y), K(id(y), id(x))) >= 0) res = y, y = ch(y)[1];
            else y = ch(y)[0];
        return res;
    }
    int suf(int x)
    {
        int y, res;
        for (y = ch(x)[1], res = y; y; )
            if (cmp(rk(y), K(id(x), id(y))) <= 0) res = y, y = ch(y)[0];
            else y = ch(y)[1];
        return res;
    }
    void check(int x)
    {
        splay(x, 0);
        int t;
        if (ch(x)[0])
        {
            splay(t = pre(x), x), ch(t)[1] = 0; //删去凸包内的
            lk(x) = rk(t) = K(id(t), id(x));
        }
        else lk(x) = INF; //保证不往左,下面同理
        if (ch(x)[1])
        {
            splay(t = suf(x), x), ch(t)[0] = 0;
            rk(x) = lk(t) = K(id(x), id(t));
        }
        else rk(x) = -INF;
        if (cmp(lk(x), rk(x)) <= 0)
        {
            rt = ch(x)[0], ch(rt)[1] = ch(x)[1], fa(ch(x)[1]) = rt, fa(rt) = 0;
            lk(rt) = rk(ch(rt)[1]) = K(id(rt), id(ch(rt)[1]));
        }
    }
    void ins(int id)
    {
        int u = rt, ff = 0;
        while (u && id(u) != id) u = ch(ff = u)[(cmp(X(id), X(id(u))) <= 0 ? 0 : 1)];
        if (u) return ;
        u = ++tot;
        if (ff) ch(ff)[(cmp(X(id), X(id(ff))) <= 0 ? 0 : 1)] = u;
        id(u) = id, fa(u) = ff, ch(u)[0] = ch(u)[1] = 0, check(u);
    }
}
int main()
{
    scanf("%d %lf", &n, &d[0]);
    for (int i = 1, j; i <= n; Splay::ins(i), ++i)
    {
        scanf("%lf %lf %lf", &day[i].a, &day[i].b, &day[i].r);
        j = Splay::find(Splay::rt, -(day[i].a / day[i].b));
        d[i] = max(d[i - 1], X(j) * day[i].a + Y(j) * day[i].b);
    }
    printf("%.3lf\n", d[n]);
    return 0;
}

CDQ分治

直接 CDQ 的话伪代码如下

1
2
3
4
5
6
7
cdq(l, r)
if (l = r) 用 d[i - 1] 跟新 d[i] 
cdq(l, mid)
将 [l, mid] 按 X 排序, 将 [mid + 1, r] 按 k 排序
用正常的斜率优化 O(n) 把左区间转移到右区间
cdq(mid + 1, r)
end dcq

不难发现这样是 $O(n \log^2 n)$ 的，虽然可过，但这样显得 CDQ 不优于平衡树，其实 CDQ 的归并和归并排序有点像，可以利用它排序

具体地，我们先在进入 CDQ 前把原序列按 $k$ 排序，并同时记下每个数在原序列中的位置，在区间 $[l, r]$ 中，把在原序列中位置 $< mid$ 的全部放在左边， $> mid$ 的全部放在右边（保证左右仍然按 $k$ 有序） ，然后去归并

我们希望一个区间归并回来后是按 $X$ 排序的，于是在 CDQ 的最后做归并排序即可

另外，其实上面的 $k, X$ 可以互换，只要改动分治顺序即可

不难发现，相比平衡树， CDQ 有码量小，轻便的优点，但缺点是如果要保证时间复杂度的话需要一些冗余操作，且个人觉得思维量比平衡树大，另外 CDQ 是离线的，我也不知道这是优点还是缺点

时间复杂度 $O(n \log n)$

代码：

中间分两边的步骤可以自己开临时数组做，别用 nth_element （它不稳定），另外，平衡树中说的记录下 $X, Y$ 的卡常在本题中很优秀，但我懒

（话说 CDQ 是真的短）

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
#include <bits/stdc++.h>
#define DB double
#define STC static
using namespace std;
const int N = 1e5 + 5;
const DB eps = 1e-12, INF = 0x3f3f3f3f;
int n, p[N];
DB d[N];
struct Day{ DB a, b, r; }day[N];
int cmp(DB x, DB y){ return fabs(x - y) < eps ? 0 : (x > y ? 1 : -1); }
DB Y(int x){ return d[x] / (day[x].a * day[x].r + day[x].b); }
DB X(int x){ return Y(x) * day[x].r; }
DB K(int a, int b){ return !cmp(X(a), X(b)) ? -INF : (Y(b) - Y(a)) / (X(b) - X(a)); }
void cdq(int l, int r)
{
    STC int q[N], tmp[N];
    if (l == r) return void(d[l] = max(d[l], d[l - 1]));
    int mid = l + r >> 1, ll = 1, rr = 0, lp = l - 1, rp = mid, tp;
    for (int i = l; i <= r; ++i) p[i] <= mid ? tmp[++lp] = p[i] : tmp[++rp] = p[i];
    for (int i = l; i <= r; ++i) p[i] = tmp[i];
    cdq(l, mid);
    for (int i = l; i <= mid; q[++rr] = i++)
        for (; ll < rr && cmp(K(p[q[rr]], p[i]), K(p[q[rr - 1]], p[q[rr]])) == 1; --rr);
    for (int i = mid + 1; i <= r; ++i)
    {
        for (; ll < rr && cmp(K(p[q[ll]], p[q[ll + 1]]), -(day[p[i]].a / day[p[i]].b)) == 1; ++ll);
        d[p[i]] = max(d[p[i]], X(p[q[ll]]) * day[p[i]].a + Y(p[q[ll]]) * day[p[i]].b);
    }
    cdq(mid + 1, r);
    for (lp = tp = l, rp = mid + 1; lp <= mid && rp <= r; ) tmp[tp++] = (cmp(X(p[lp]), X(p[rp])) == -1 ? p[lp++] : p[rp++]);
    for (; lp <= mid; tmp[tp++] = p[lp++]); 
    for (; rp <= r; tmp[tp++] = p[rp++]); 
    for (int i = l; i <= r; ++i) p[i] = tmp[i];
}
int main()
{
    scanf("%d %lf", &n, &d[0]); //都先初始化为s
    for (int i = 1; i <= n; d[i] = d[0], p[i] = i, ++i) scanf("%lf %lf %lf", &day[i].a, &day[i].b, &day[i].r);
    sort(p + 1, p + 1 + n, [&](int a, int b){ return -(day[a].a / day[a].b) > -(day[b].a / day[b].b); });
    cdq(1, n);
    printf("%.3lf\n", d[n]);
    return 0;
}

李超线段树

这个就是邪教了

看到形式二：
$$
Y(j) = - \frac{A _i}{B _i} \times X(j) + \frac{d[i]}{B _i}
$$
我们把它化回去（是的，倒退，但不完全退）：
$$
\frac{d[i]}{B_i} = \max (X(j) * \frac{A _i}{B _i} + Y(j))
$$
我们明确一下我们要干嘛：对于一个 $i$ ，我们找到一个最优的 $j$ 使得上式最小

设 $t = \frac{A _i}{B _i}$ ，不再把每个 $j$ 当作点而是把它当作线段 $y = X(j) * x + Y(j)$ （即 $y = k * x + b$ 的形式），问题转化为对于每个 $t$ ，在一堆直线中找到当 $x = t$ 时，使得 $y$ 最大的一个，这很像李超线段树的板子，只是 $x = t$ 为小数，当然也可以就用小数直接查（动态开点），但这样精度要开很大，常数也很大，更优秀的方法是将 $x$ 离散化，这样也可以保证时间复杂度

说实话这已经不算斜率优化了，但这种方法可以也解决很大一部分斜率优化题，所以也写这里

时间复杂度 $O(n \log n)$

代码：

也算短吧（主要数据结构部分长，不好压）？但李超线段树不常打，另外其实这种方法 d[i] 只由 d[i - 1] 转移，可以压掉，但那样就要记录 $X, Y$ ，我懒（艹）

有一个小点是要注意离散化后下标要从 $1$ 开始，因为建树是建在 $[1, n]$ 上的（这是值域线段树，离散化后值域应该是 $[1, n]$ ）

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
#include <bits/stdc++.h>
#define DB double
using namespace std;
const int N = 1e5 + 5, INF = 0x3f3f3f3f;
const DB eps = 1e-9;
int n;
DB d[N];
struct Day{ DB a, b, r, x; }day[N];
vector<DB> xx;
int cmp(DB x, DB y){ return fabs(x - y) < eps ? 0 : (x > y ? 1 : -1); }
DB Y(int x){ return d[x] / (day[x].a * day[x].r + day[x].b); }
DB X(int x){ return Y(x) * day[x].r; }
namespace LC
{
    struct Line
    {
        DB k, b, l, r;
        DB calc(int xid){ return ((xid > r || xid < l) ? -INF : xx[xid] * k + b); }
    } li[N];
    int cnt = 0;
    struct Node
    {
        int l, r, id;
    } tr[N << 2];
    #define l(x) tr[(x)].l
    #define r(x) tr[(x)].r
    #define id(x) tr[(x)].id
    #define Mid (tr[u].l + tr[u].r >> 1)
    #define lc (u << 1)
    #define rc (u << 1 | 1)
    bool judge(int a, int b, int x){ return cmp(li[a].calc(x), li[b].calc(x)) <= 0; }
    void build(int u, int l, int r)
    {
        tr[u] = {l, r, 0};
        if (l == r) return ;
        int mid = Mid;
        build(lc, l, mid), build(rc, mid + 1, r);
    }
    void upd(int u, int l, int r, int d)
    {
        int mid = Mid;
        if (l <= l(u) && r >= r(u))
        {
            if (judge(id(u), d, mid)) swap(id(u), d);
            if (judge(id(u), d, l(u))) upd(lc, l(u), r(u), d);
            if (judge(id(u), d, r(u))) upd(rc, l(u), r(u), d);
            return ;
        }
        if (l <= mid) upd(lc, l, r, d);
        if (r > mid) upd(lc, l, r, d);
    }
    void ins(Line x){ li[++cnt] = x, upd(1, 1, n, cnt); }
    DB ask(int u, int x)
    {
        if (l(u) == r(u)) return li[id(u)].calc(x);
        int mid = Mid;
        DB res = (x <= mid ? ask(lc, x) : ask(rc, x));
        return max(res, li[id(u)].calc(x));
    }
}
void lsh(){ xx.push_back(-INF); for (int i = 1; i <= n; ++i) xx.push_back(day[i].x);sort(xx.begin(), xx.end()); } //这里就不必去重了,因为是实数
int main()
{
    scanf("%d %lf", &n, &d[0]);
    for (int i = 1; i <= n; ++i) scanf("%lf %lf %lf", &day[i].a, &day[i].b, &day[i].r), day[i].x = day[i].a / day[i].b;
    lsh(), LC::build(1, 1, xx.size() - 1); //注意是size-1,因为xx多插了一个-INF,多建点会RE
    for (int i = 1, t; i <= n; LC::ins({X(i), Y(i), 1, DB(n)}), ++i) d[i] = max(d[i - 1], day[i].b * LC::ask(1, lower_bound(xx.begin(), xx.end(), day[i].x) - xx.begin()));
    printf("%.3lf", d[n]);
    return 0;
}

待续

话说我好懒啊，记录卡常一直懒得打，另外代码有点压行非常抱歉

其它的下次再写，会挂链接的

优化dp3