OI - Forced Online Queries Problem | Lucky_Glass's Blog

以心为名，名为爱惜

0%

OI - Forced Online Queries Problem

发表于 分类于 Valine：

本来平时做分块的题就做得少……又听 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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
/*Lucky_Glass*/
#include<bits/stdc++.h>
using namespace std;
 
const int N=2e5;
typedef pair<int,int> pii;
 
set< pii > Gnow,Gpre;
 
int Sfa[N+3],Su[N+3],Sv[N+3],Sdep[N+3],Stop;
 
int n,m,Sper,Vans;
int Itmp[N+3],Iu[N+3],Iv[N+3];
 
struct DSU{
	int Dfa[N+3],Ddep[N+3];
	int FindFa(int u){return Dfa[u]==u? u:FindFa(Dfa[u]);}
	bool Merge(int u,int v,bool Bstk){
		int fu=FindFa(u),fv=FindFa(v);
		if(fu==fv) return false;
		if(Ddep[fu]<Ddep[fv]) swap(fu,fv);
		//v->u
		if(Bstk){
			Stop++;
			Sv[Stop]=fv;
			Su[Stop]=fu;
			Sfa[Stop]=Dfa[fv];
			Sdep[Stop]=Ddep[fu];
		}
		Dfa[fv]=fu;
		Ddep[fu]=max(Ddep[fv]+1,Ddep[fu]);
		return true;
	}
	void Init(int Nn){
		for(int i=1;i<=Nn;i++)
			Dfa[i]=i,Ddep[i]=1;
	}
}Dset;
 
void Remove(int u,int v){ //如果 (u,v) 在这块询问之前存在，但是在这块询问中被修改，就把它移除
	if(u>v) swap(u,v);
	pii pr(u,v);
	if(Gpre.count(pr)){
		Gnow.insert(pr);
		Gpre.erase(pr);
	}
}
void Update(int u,int v){ //更改set中边 (u,v) 的状态
	if(u>v) swap(u,v);
	pii pr(u,v);
	if(Gnow.count(pr)) Gnow.erase(pr);
	else Gnow.insert(pr);
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++) scanf("%d%d%d",&Itmp[i],&Iu[i],&Iv[i]);
	Sper=5000;
	for(int i=1;i<=m;i+=Sper){
		int mxj=min(m,i+Sper-1);
		for(int j=i;j<=mxj;j++)
			if(Itmp[j]==1){
				Remove(Iu[j],Iv[j]);
				Remove(Iu[j]%n+1,Iv[j]%n+1);
			}
		Dset.Init(n);
		for(auto it : Gpre) Dset.Merge(it.first,it.second,false);
		Stop=0;
		for(int j=i;j<=mxj;j++){
			Iu[j]=(Iu[j]+Vans-1)%n+1;
			Iv[j]=(Iv[j]+Vans-1)%n+1;
			if(Iu[j]>Iv[j]) swap(Iu[j],Iv[j]);
			if(Itmp[j]==1) Update(Iu[j],Iv[j]);
			else{
				while(Stop){
					Dset.Ddep[Su[Stop]]=Sdep[Stop];
					Dset.Dfa[Sv[Stop]]=Sfa[Stop];
					Stop--;
				}
				for(auto it : Gnow)
					Dset.Merge(it.first,it.second,true);
				printf("%d",Vans=(Dset.FindFa(Iu[j])==Dset.FindFa(Iv[j])));
			}
		}
		for(auto it : Gnow) Gpre.insert(it);
		Gnow.clear();
	}
	printf("\n");
	return 0;
}

The End

Thanks for reading!

Email: lucky_glass@foxmail.com，欢迎提问