省选联考 2025 D1T2 题解

20_200 · 2025-03-04 16:31:10 · 题解

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代码压缩包有密码，所以代码等发密码之后再放，真的不想复盘了太恶心了。