自动搬运

查看原文

来自洛谷，原作者为

	伊地知虹夏 下北泽大天使

搬运于2025-08-24 23:03:36，当前版本为作者最后更新于2025-03-22 11:34:51，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

缝合怪。

首先考虑性质 A 怎么做。这就是 P1248 加工生产调度，结论是最优解满足 $\forall 1 \le i < j \le n, \min(a_i,b_j) \le \min(a_j,b_i)$。但是这个条件不满足传递性，所以分 $a_i < b_i$，$a_i = b_i$，$a_i > b_i$ 讨论一下，得到排序方式。然后依次考虑每个人，记 $p_i$ 为 $a_i$ 的前缀和，$q_i$ 为 $[1,i]$ 的答案，则有 $q_i = \max(q_{i-1}, p_i) + b_i$。

然后考虑正解。先把所有人离线下来按照上述规则排序，记 ${\rm rnk}_i$ 为 $i$ 在新序列中的位置，那么方案就是将客人按照 $\rm rnk$ 排序。

接下来我们要加速求答案的过程，考虑把 $p_i$，$q_i$ 的转移写成 $(\max,+)$ 卷积的形式：

$$[q_i, p_i] = [q_{i-1}, p_{i-1}] \times \begin{bmatrix} b_i & -\infin \\ a_i+b_i & a_i \\ \end{bmatrix} $$

我们使用线段树维护矩阵乘法即可。