自动搬运

查看原文

来自洛谷，原作者为

	Great_Influence **

搬运于2025-08-24 22:11:04，当前版本为作者最后更新于2019-07-16 14:57:18，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

---

这题就是这道题的加强版。

首先，我们不考虑位置的限制，只考虑过程。

我们可以设 $dp[i]$ 表示在时刻 $i$ 时的最小烦躁值减去 $q_{s_k}$ ，则有:

对于一条路径 $(p_r,q_r)$(我们此时不考虑 $x$ 和 $y$ ):

$$dp[q_r]=\min_{j\le p_r}dp[j]+A(p_r-j)^2+B(p_r-j)+C $$

明显可以利用斜率优化加速转移。

但是问题在于路径是一个持续性的过程，即 $p_i$ 和 $q_i$ 之间可能相距很远。不过我们完全可以将 $p_i$ 和 $q_i$ 拆成 一次询问 和 一次尾部插入 两个事件，这样事件就可以通过排序变成时间单调递增的了。

接下来考虑 $x$ 和 $y$ ，也就是起点和终点。不过这可以用上面一样的方法处理，也就是将起点和终点拆成两个操作。我们依然维护单调队列，但是因为每个事件对应的地点有区别，因此我们对每个点开一个 $vector$ ，分别维护即可。

记得在 $1$ 号点预先放一个 $0$ 时刻 $0$ 代价的点作为起点。答案可以在路径终点是 $n$ 的时候直接统计，$n$ 号点就没必要再开 $vector$ 了。

时间复杂度瓶颈在排序上。因为数据范围特别小，因此可以直接采用统排。时间复杂度 $O(M+T)$，其中 $T$ 是时间范围的最大值。

代码就不贴了。