Qoj4420
下文默认 \(n,q\) 同阶。
记一组询问为 \((x_i,y_i,l_i,r_i)\)。
定义 \(f_{u,i}\) 表示从 \(u\) 出发，只经过 \([l_i,r_i]\) 之间的边，能否到达 \(y_i\)，其中第二维是 bitset。同时为了方便处理边的限制，考虑定义 \(g_{x,i}\) 表示 \([l_i \le x \le r_i]\)。
则对于一条边 \((x,y,id)\) 转移是简单的，有 \(f_x = f_x \operatorname{or} \left(f_y \operatorname{and} g_{id} \right)\)。
考虑怎么求 \(g\)，令 \(g_{l_i,id}=1,g_{r_i+1,id}=1\)，做一遍前缀异或即可。
此时时空均为 \(\mathcal{O}\left(\dfrac{mq}{w}\right)\)。
考虑优化空间，定期重构。即每 \(B\) 个询问分一组处理，时间 \(\mathcal{O}\left(\dfrac{mq}{w}+\dfrac{mq}{B}\right)\)，空间 \(\mathcal{O}\left(\dfrac{mB}{w}\right)\)。
Uoj953
每 \(w\) 个询问分一组，被操作过的点直接暴力，考虑怎么求没被操作过的点。
定义 \(f_{u,i}\) 表示 \(x_i\) 能否到达 \(u\)，压进 ull 中，直接 \(\mathcal{O}\left(m\right)\) 求。定义 \(g_{x,i}\) 表示 \([l_i \le x \le r_i]\)，同上题一样做一遍前缀异或即可。
\(b_i\) 是排列，考虑从大到小考虑每个点 \(u\) 能贡献到的询问。要满足：
- 询问的 \(x\) 能否到达 \(u\)。
- \(l_i \le a_u \le r_i\)。
- 当前集合是否被处理过了。
可以简单用 \(f,g\) 的信息求出。
复杂度 \(\mathcal{O}\left(\dfrac{\left(n+m\right)q}{w}\right)\)。