LOJ3494「JOISC 2021 Day3」保镖 题解
JOI 街是一条贯通东西的长街。我们将其抽象为一条数轴。
从现在起，将有 \(N\) 个贵宾（VIP）来到 JOI 街并大逛特逛。VIP 们以 \(1\) 到 \(N\) 编号。VIP \(i\ (1 \le i \le N)\) 将会在时刻 \(T_i\) 从坐标 \(A_i\) 前往坐标 \(B_i\)。其速度是每单位时间 \(1\) 单位长度。
如果 \(A_i < B_i\)，VIP \(i\) 将会以不变的速度在正方向上移动。类似地，如果 \(A_i > B_i\)，VIP \(i\) 将会以不变的速度在负方向上移动。
一个保镖的工作是在 JOI 街上巡逻并保护 VIP 们。为了保护一个 VIP，很有必要和 TA 一起逛一会街，同时保护 TA。当然，允许保镖在他们逛街逛到一半时才开始保护，或在他们逛街结束前就停止保护。开始和停止保护的时刻不必为一个整数。
特别地，尽管可能有多个 VIP 在同一坐标，保镖也最多只能保护一个 VIP。
保镖可以在 JOI 街上以每单位时间最多 \(1\) 单位长度的速度随意走动。在他们停止保护一个 VIP 之后，可以去到另一个地方再开始保护另一个 VIP。如果一个保镖和 VIP \(i\) 一起逛街，那么 VIP 将会对他们一起走过的距离的每单位长度给保镖 \(C_i\) 元小费。这里保证 \(C_i\) 是偶整数。
作为一个安保公司的员工，您正在计划 \(Q\) 份保护 VIP 的方案。这些方案以 \(1\) 到 \(Q\) 编号。对于方案 \(j\ (1 \le j \le Q)\)，一个保镖在时刻 \(P_j\) 时从坐标 \(X_j\) 开始工作。您的任务是分别最大化每个方案中的保镖能够得到的总小费。
请您编写一个程序对于给定的 VIP 和保镖的信息，计算每一个方案中保镖的最大总小费。
在此题的限制下，可以证明答案一定是个整数。
\(1 \le N \le 2\,800\)，\(1 \le Q \le 3\,000\,000\)。
数据结构 斜率优化 李超树 坐标转换
神仙的题目，曾经的噩梦。
原来的问题是一个一维的，但是还有根据时间的决策，于是我们可以把位置当做 \(x\) 轴，时间当做 \(y\) 轴，建立一个二维的坐标系描述问题。
那么每一个 VIP 的走路方向就是从 \((A_i, T_i) \to (B_i, T_i+|A_i - B_i|)\)，是一条斜率为 \(+1\) 或者 \(-1\) 的直线，为了方便，我们可以将整个坐标轴顺时针旋转 \(45\) 度，也就是将 \((x, y) \to (x + y, x - y)\) 但是会将距离 \(\times \sqrt{2}\)，有因为之前转换成二维问题，也将距离 \(\times \sqrt{2}\)，于是总共答案 \(\times 2\)，那么我们可以将 \(C_i\) 除以 \(2\)（所以 \(C_i\) 是偶数？）。
为了方便，我们可以将所有 VIP 坐标离散化，那么转化出了一个 \(2N \times 2N\) 的网格图，然后转化后的问题如下：
有一张网格图，沿着每次只能向下或者向左走，每个网格图上的边都有自己的边权 \(C_i\)，只要沿着该边走 \(x\) 步，那么可以获得 \(C_ix\) 的收益。
现在给出 \(Q\) 个初始点，问走出的最大收益是什么？
因为网格图的大小可以承受，于是我们可以用 DP 求出当走到网格图格点 \((i, j)\) 上的最大收益 \(dp(i, j)\)。
然后考虑从一个非格点的最大收益，最优方案一定是 先向左走到某一条网格边上然后向下走到格点 / 先向下走到某一条边上然后向左走到格点。
先将所有询问离线，然后考虑每一行 / 每一列，计算 先向左再向下 / 先向下再向左 的贡献。
注意到所有贡献是一个一次函数的形式，于是可以李超树求解，复杂度 \(\mathcal O(n^2\log n + Q\log n)\)。
但是注意到 DP 数组有单调性，也就是每次加入的线段斜率必须递减，否则不优，于是可以用单调栈 + 二分维护，具体维护的是一个上凸壳，但是因为插入线段的 \(k\) 值依次递减，相当于我们在倒着插入，于是可以将图像关于 \(y\) 轴对称，然后就是正着插入了，复杂度 \(\mathcal O(n^2 +Q\log n)\)。
具体实现有亿些细节，可以看代码。
btw，本来这个代码可以更短的，但是在校内 OJ 上被卡空间了，很有可能是因为评测机是 \(64\) 位，于是开的一堆 vector 就炸了，于是将原来 \(N\times N\) 的 vector 变成了 \(2 \times N\) 的 vector，常数空间有所优化，终于在校内 OJ 上卡过去了。