题解：P11831 [省选联考 2025] 追忆

· · 题解

显然，这题的复杂度不可能低于 $O(n^2/w)$。 对时间分块，定期重构，设阈值为 $B$。 那么在每一次重构之前，都最多只会有 $B$ 个点是不确定的，询问时枚举这其中的每个点判断是否可达，只要提前 bitset 预处理出可达性，视 $n,m,q$ 同阶，复杂度是 $O(nB)$。不妨取 $B=n/w$，这样刚好平衡了。 现在考虑另外 $n-B$ 个已经确定的点。对 $a_i$ 分块，设块长为 $D$。对每一块，都预处理出每一个点可达的点中 $b_x$ 的最大值。每次询问，整块查，散块暴力。这样复杂度是 $O(nD+n^2/D+n^2w/D)$。取 $D=\sqrt{nw}$，得到最优复杂度 $O(n^2/w+n\sqrt{nw})$。