题解：CF1990E2 Catch the Mole(Hard Version)

happybob · 2024-07-21 13:24:03 · 题解

请先阅读 Easy Version 题解。

树分块后，考虑我们的询问瓶颈其实在于找到答案上方的第一个关键点后，我们要进行两倍链长次询问以确定什么时候这个点移动到了关键点。

优化的一个想法是考虑在里面再做一次分块状物，既每 k 次询问叶子后询问一次关键点，然而很不幸地，这个做法的最坏次数略微超过了询问次数限制。

考虑另一个做法。先对叶子进行链长次操作，保证这个点已经到了关键点上面，然后进行二分。取链长为 64 可以通过。

Submission Link。