P11381

给定一个 DAG，每个点有 $a$ 和 $b$ 两个权值，保证 $a$ 互补相同，$b$ 互不相同，有 $q$ 次操作为以下三种：

考虑 $l=r$ 且只有 $3$ 操作的情况是 DAG 可达性判断，所以不会低于 $O(\frac{nm}\omega)$，时空限制也体现了这一点；带修求区间内的最大值也无法和 $\omega$ 数据结构很好的结合，所以考虑定期重构，考虑每 $B\approx O(\sqrt n)$ 次操作重构。现在问题变成两个部分：会修改的 $t$ 和不会修改的 $t$。

会修改的 $t$ 只有 $O(B)$ 个，那么维护每个点能到的这类点的 bitset，可以做到 $O(\frac{q}{B}\frac{mB}{\omega})=O(\frac{qm}{\omega})$。修改显然可以 $O(1)$ 处理，每次询问的时候枚举这些点判断是否可行，可以做到 $O(qB)$。

对于不会修改的 $t$，维护每个点的答案有点困难，所以考虑只计算被询问到的点，这样的点也有 $O(B)$ 个。使用 bitset 求出每个点是否能被这些点到达的复杂度也是 $O(\frac{qm}{\omega})$ 的。为了解决 $a$ 在一个区间内的限制，从小往大枚举 $a$ 时动态维护当前的 $a$ 满足了哪些询问的限制的 bitset，这可以做到 $O(\frac{q}{B}n)$。最后枚举 $v:n\to 1$，维护答案 $\geq v$ 的询问，每次当 bitset 改变时更新，这是 $O(\frac{q}{B}(\frac{nB}{\omega}+B^2))=O(\frac{qn}{\omega}+qB)$ 的。

最终总复杂度为 $O(\frac{qm+qn}{\omega}+qB+\frac{q}{B}n)$ 的，理论上来说 $B$ 取 $O(\sqrt n)$ 时最快，但是我们发现 $O(q\sqrt n)$ 的速度远比 $O(\frac{qm}{\omega})$ 快，而 bitset 在大小更大时相对较快（有更小的常数）且 $O(\frac{q}{B}n)$ 常数较大，所以可以把 $B$ 开到很大。我的考场代码开了 $B=10^{\color{red}4}$。