OI - Forced Online Queries Problem

本来平时做分块的题就做得少……又听 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,欢迎提问

0%