省选联考 2025 D1T2 题解

3.3k，赛时写过最长的题。极限调出来真的是奇迹。

数据结构乱搞题。

以下认为 $n,m,q$ 同阶。

首先看到有向图（本题是 DAG）可达性就可以直接上 bitset 预处理了，这东西只能 $O(\frac{n^2}{w})$。再注意到本题特别的时空限制基本就一眼真了。

需要区间查询，那就开一个bitset维护当前区间的每个点是否符合 $l\le a_y\le r$，查询的时候 $x$ 能到 $y$ 的限制就是维护的区间合法点集 and $x$ 可达点集。

每次询问合并 $O(\log n)$ 个 bitset 显然不行，那么就不能在外面套线段树，所以直接莫队。有修改，那就带修莫队。

需要查询 bitset 里面为 $1$ 的位置对应的 $b$ 的最大值，一个一个枚举显然不行，那就手写bitset，对于每 $w$ 个 bit 组成的 unsigned long long，在里面二分最大值，这样每次查询一个 $w$ 集合的最大值的复杂度就能做到 $O(\log w)$。

这要求在修改 $b$ 的过程中维护每个 $w$ 集合里面对应位置的第 $1\sim w$ 大的 $b$ 值，那么每次修改 $b$ 就是 $O(w)$ 的，套在莫队里显然不行，所以先预处理，在一开始就把每次修改后 $b$ 对应的 $w$ 集合直接存下来，然后再开一个数组维护每个 $w$ 集合对应的版本编号，莫队里修改 $b$ 的时候直接修改对应的版本编号就可以做到 $O(1)$ 了。

时间复杂度 $O(n^{5/3}+\frac{n^2\log w}{w})$。

然后这道题就做完了，剩下的是一份巨大长丑的代码，考场大样例 8s，可能还要卡常才能通过。

GD代码压缩包有密码，所以代码等发密码之后再放，真的不想复盘了太恶心了。