小圆抱抱 | 【题解】P11833 [省选联考 2025] 推箱子

· · 题解

赛时第一反应是什么都不会，然后瞎写了个暴力过了所有样例，得到了下述观察。

观察

对于两个要求 i,j，若 t_i\le t_j，则应当先满足要求 i，再满足要求 j。

证明

若 i 操作不会影响到 j，则是简单的：设 i 操作用时 a，j 操作用时 b，显然 a\le t_i\land a+b\le t_j 比 a+b\le t_i\land b\le t_j 更易满足。

否则将 j 移动到不会被 i 影响的位置（容易证明这一定让它离目标点更近了），转化成上述情况。

\square

基于上述观察，不难写出暴力：维护一个全局的时间戳 cur，每次要将 i 移动到 b_i 时，检查 i+1 的位置是否 \gt b_i（或者 i-1 的位置 \lt b_i），如果是的话就直接操作；否则先递归将 i+1 移动到 b_i+1（i-1 同理），再移动 i。这样是 \mathcal{O}(n^2) 的。

观察到暴力之所以慢，是因为每次可能将连续的一长段做了平移。（我们称 i 和 i+1 是连续的，当且仅当它们位置绝对值相差为 1。）

于是使用 ODT 维护连续段即可。每次移动的时候至多分裂一次，然后暴力往后（前）找下一段是否被影响了。这样这些所有被暴力找到的段会被合并称一段，所以复杂度是 \Theta(n\log n)。

小圆抱抱/kel