Ender_hz: 朴素的 BFS，罚时一发是因为箱子传递的时候只考虑了 ! 而未考虑 @，另一发是因为没有看清输出格式要先输出步数，准备写 check 的时候才看到（

Ender_hz: 有一点 hash collision 的思想，总之就是进行 $\lfloor\sqrt{1000}\rfloor + 1$ 次模 $\sqrt{10^{18}}$ 的生日悖论草过去，记得最后输出的时候对 $\lfloor\sqrt{1000}\rfloor^2+1\sim 1000$ 项的答案输出 $0$。

Ender_hz: 赛时思路太局限了，只想着拆分 $\lfloor\cdot+\cdot\rfloor$ 用前缀和，没想到倍增。

思路是 $x$ 在 $\lceil\log V\rceil = 30$（$V$ 为值域）次操作后贡献最多为 $1$，利用这个性质做倍增，离线预处理时间复杂度 $\mathcal O\left(\dfrac{n}{\log V}\log^2 V+\dfrac{n}{\log V}\log n\right)=\mathcal O(n\log V)$，单次询问时间复杂度 $\mathcal O(\log n+\log V)$，注意最后答案其实就是终值 $-$ 初值。

Ender_hz: 赛时没有注意到题解里的性质 ;w;

这个题的重点是搜索的状态设计，注意到每个元素减去最小值后的状态一定被访问过，所以可以记忆化。

$12\rm{s}$ 的时限牛客的少爷机可以轻松草过去。

Ender_hz:

_istina_:

MeowScore: