题解：P10439 [JOIST 2024] 逃生路线 2 / Escape Route 2

happybob · 2025-10-25 22:07:14 · 题解

不难发现本质就是个贪心，只要 l \rightarrow l+1 选的是哪个确定，后面的都可以直接贪心得到。

对称的，只要 r-1 \rightarrow r 选的是哪个确定，前面的也不难贪心得到。

直接枚举 l,r-1 中向下一个点的边数较小的一侧并记忆化，显然是 O(n\sqrt n) 的枚举次数。

加个倍增查询贪心的结果就是 O(n\sqrt n \log n) 的。

但是你既然都根号了，写个分块平衡复杂度就能做到 O(n \sqrt n) 了。