自动搬运

查看原文

来自洛谷，原作者为

	yzy4090 渴望保留一切终将逝去的事物

搬运于2025-08-24 22:59:59，当前版本为作者最后更新于2024-09-22 20:11:24，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

发现题解中空间复杂度没有较好的证明，所以此处进行一个官方做法的写。

首先可以发现由于要为最坏的情况做打算，正着 DP 比较困难。又由于实验次数不定，所以最好是从反物质质量下手。
因此可以考虑设 $dp_i$ 为反物质质量为 $i$ 克时未来最坏情况的最大利润。$dp_i$ 是下列式子中的最小值：

• $i\cdot 10^9$（停止实验）；
• $\underset{\begin{subarray}{c}1\le j\le n,i+r_j\le a\\l_j\le k\le r_j\end{subarray}}{\min}dp_{i+k}-c_j$（继续做第 $j$ 次实验）。

这样直接做时间复杂度是 $\mathcal O\left(na^2\right)$ 的，可以得到 40 分。

考虑优化。可以简单地使用 ST 表，但是空间是 $\mathcal O\left(a\log a\right)$ 的，不够优。

由于这个 DP 中询问的区间已经给定，所以可以考虑一种离线 RMQ 做法：
按照询问的左端点 $p=i+l_j$ 倒序排序，然后维护一个并查集和单调栈，栈中存放满足 $p\le i\le a,dp_i\le dp_p$ 的 $i$ 集合，每次 pop 掉不满足条件的数 $x$ 时则说明 $p$ 是 $x$ 左侧第一个 $dp$ 值大于等于 $dp_x$ 的数，则将 $x,p$ 合并，这样不断与第一个比它大的合并，即可得到其左侧所有比它大的数的集合。因此询问就比较简单了。

这样的空间复杂度是 $\mathcal O(n+a)$ 的。当使用既路径压缩又按秩合并的并查集时，时间复杂度多一个 $\alpha(a)$。code。