qoj4420. Range Reachability Query

给定 \(n\) 个点，\(m\) 条边的有向无环图，有 \(q\) 次询问，第 \(i\) 次询问以下内容：

• 是否存在一条 \(x_i\) 到 \(y_i\) 的路径满足路径上所有边的编号都在 \([l_i,r_i]\) 的范围内？

\(n,m,q\le10^5\)

---

triiiiiiiiiiiiiiiiiiiiiiiiiick

---

我们根据这个题面，结合这个数据范围，考虑 bitset。

令 \(f_{i,j}\) 表示是否存在一条 \(i\) 到 \(y_j\) 的路径满足路径上所有边的编号都在 \([l_j,r_j]\) 的范围内。

那么转移：\(f_u=f_v\ \&\ S_k\)，其中 \(S_k\) 表示所有 \(l_j\le k\le r_j\) 的询问的编号的集合，其中 \(k\) 是当前边的编号。

于是离线扫一遍，再做一下拓扑排序就好了。