P11381
hxhhxh
·
·
个人记录
题意
给定一个 DAG，每个点有 a 和 b 两个权值，保证 a 互补相同，b 互不相同，有 q 次操作为以下三种：
- 交换 a_x,a_y；
- 交换 b_x,b_y；
- 给定 x,l,r，求所有 y 满足 x 可以到达 t 且 a_t\in[l,r] 的 t 中 b_t 的最小值。没有 t 满足条件则输出 0。
n,q\leq 10^5,a_i,b_i\leq n,m\leq 2\times 10^5
\color{red}6\text{s},2\text{G}
思路
考虑 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}。