小圆抱抱 | 【题解】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

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

文章操作

相关推荐

评论

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