反物质 题解

· · 题解

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

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

这样直接做时间复杂度是 \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。