本来平时做分块的题就做得少……又听 tly dalao 说这是比较少见的询问分块的题;
于是决定写一篇博客 awa
Part1. 题面
有一个 $n$ 个点的无向图,一开始,连通图上没有边。你要对图进行 $m$ 次操作或回答询问:
1 x y
:如果图上存在边 $(x,y)$,就断开 $(x,y)$;否则连接 $(x,y)$;2 x y
:询问 $x$,$y$ 两点是否连通,是则答案为 $1$,否则为 $0$;
数据加密:记 $last$ 为上一次 2 x y
操作的答案(一开始设为 $0$),真实的 $x’,y’$ 应为 $x’=(x+last-1)\bmod n+1;y’=(y-last-1)\bmod n +1$。
[数据规模]
- $1\le n,m\le2\times10^5$;
Part2. 解析
考虑将询问按 $\sqrt m$ 的大小分成 $\sqrt m$ 块,对于每一块询问:
先将 处理这一块询问之前已经存在 且 这一块询问中不会被修改 的边放入图中,并用 并查集 维护连通块。虽然数据加密,无法知道具体修改哪条边,但是我们知道如果输入的是 1 x y
,被修改的边一定是 $((x-1)\bmod n+1,(y-1)\bmod n+1$ 和 $(x\bmod n+1,y\bmod n+1)$ 之一(毕竟 $last$ 只有 $0$ 或 $1$ 的取值嘛)。不妨把这两条边都看作“在这一块询问中被修改过”。
剩下的 在这一块询问中被修改 的边用 set 维护,因为 set 可以快速地插入/删除元素。因此,可以用 set 维护“在这一块询问中被修改、且当前存在的边”。
接下来依次处理这一块询问中的每个询问:
如果是 1 x y
,则修改 set 中,边 $(x,y)$ 的存在状态;
如果是 2 x y
,先把 “在这块询问中被修改、当前存在” 的边(也就是 set 中的边)插入并查集,然后询问 $x$,$y$ 的连通性;询问完后,将 刚才插入的所有边在并查集中撤回(不包括处理这块询问之前插入并查集中的边),所以我们需要的是 可回退化并查集 ;另外,为了降低并查集的常数,还需要启发式合并。
可回退化并查集
每次合并时,会修改一个点的父亲,以及一个点的深度(启发式合并);所以只要存储在合并时,被修改的变量原来的值,就可以回退了。
Part3. 时间复杂度
在处理每块询问之前,要把之前在这一块询问之前就已经存在的、且在这块询问中没有修改的边插入并查集,时间复杂度为 $O(m)$,又因为有 $\sqrt m$ 个询问,这些操作的复杂度为 $O(m\sqrt m)$;
对于每个(单个)询问,要把 set 中的所有边都插入并查集,因为 set 中只有这块询问中修改的边(大概是 $\sqrt m$ 个,有大概为 $2$ 的常数),所以 $m$ 次操作的总复杂度为 $O(m\sqrt m)$;
总复杂度为 $O(m\sqrt m)$ 。(分块嘛)
Part4. 源代码
set<>
真好用……
1 | /*Lucky_Glass*/ |
The End
Thanks for reading!
Email: lucky_glass@foxmail.com,欢迎提问