bzoj 2049 洞穴勘测

Posted on | Views:

线段树分治 + 并查集.

这本来是个 $LCT$ 的模板题,但离线下来也可以用线段树分治 + 并查集来做.

每条边可以看做在一个时间区间内生效,每个线段树节点维护一个 $vector$ ,存储在该区间内都有效的边.

一条边只会被加入 $O(\log m)$ 个线段树节点,空间复杂度为 $O(m\log m)$ .

最后 $dfs$ 整个线段树,进入一个节点时,就让它的 $vector$ 中的边都生效,退出时撤销这些边.

因为有撤销,所以不能路径压缩,可以用按秩合并的并查集来维护.

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
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline int read()
{
	int out=0,fh=1;
	char jp=getchar();
	while ((jp>'9'||jp<'0')&&jp!='-')
		jp=getchar();
	if (jp=='-')
		fh=-1,jp=getchar();
	while (jp>='0'&&jp<='9')
		out=out*10+jp-'0',jp=getchar();
	return out*fh;
}
typedef pair<int,int> pii;
#define mp make_pair
const int MAXM=2e5+10;
map<pii,int> Eid;
struct Edge
{
	int u,v;
	int l,r;
	Edge(){r=-1;}
} E[MAXM];
struct query
{
	int u,v,id;
};
int n,m,ans[MAXM],qcnt=0,ecnt=0;
vector<query> qry[MAXM];
vector<pii> opt[MAXM<<2];
int fa[MAXM],siz[MAXM];
void init()
{
	for(int i=1; i<=n; ++i)
		fa[i]=i,siz[i]=1;
}
int Find(int x)
{
	if(x==fa[x])
		return x;
	return Find(fa[x]);
}
void Union(int &x,int &y)
{
	if(siz[x]<siz[y])
		swap(x,y);
	siz[x]+=siz[y];
	fa[y]=x;
}
struct SegTree
{
	vector<int> s[MAXM<<2];
#define root s[o]
	void upd(int o,int l,int r,int L,int R,int c)
	{
		if(L<=l && r<=R)
		{
			root.push_back(c);
			return;
		}
		int mid=(l+r)>>1;
		if(L<=mid)
			upd(o<<1,l,mid,L,R,c);
		if(R>mid)
			upd(o<<1|1,mid+1,r,L,R,c);
	}
	void add(int o)
	{
		int tot=root.size();
		for(int i=0;i<tot;++i)
		{
			int x=root[i];
			int u=Find(E[x].u),v=Find(E[x].v);
			if(u==v)
				continue;
			Union(u,v);
			opt[o].push_back(mp(u,v));
		}
	}
	void del(int o)
	{
		int tot=opt[o].size();
		for(int i=0;i<tot;++i)
		{
			pii t=opt[o][i];
			int u=t.first,v=t.second;
			fa[v]=v;
			siz[u]-=siz[v];
		}
	}
	void solve(int o,int p)
	{
		int tot=qry[p].size();
		for(int i=0;i<tot;++i)
		{
			query q=qry[p][i];
			int u=Find(q.u),v=Find(q.v);
			if(u==v)
				ans[q.id]=1;
			else
				ans[q.id]=0;
		}
	}
	void dfs(int o,int l,int r)
	{
		add(o);
		if(l==r)
		{
			solve(o,l);
			del(o);
			return;
		}
		int mid=(l+r)>>1;
		dfs(o<<1,l,mid);
		dfs(o<<1|1,mid+1,r);
		del(o);
	}
} T;
int main()
{
	n=read(),m=read();
	init();
	for(int i=1; i<=m; ++i)
	{
		char op[10];
		scanf("%s",op);
		int u=read(),v=read();
		if(op[0]=='C')
		{
			Eid[mp(u,v)]=Eid[mp(v,u)]=++ecnt;
			E[ecnt].u=u,E[ecnt].v=v;
			E[ecnt].l=i;
		}
		else if(op[0]=='D')
			E[Eid[mp(u,v)]].r=i;
		else
			qry[i].push_back((query){u,v,++qcnt});
	}
	for(int i=1; i<=ecnt; ++i)
	{
		if(E[i].r==-1)
			E[i].r=m;
		T.upd(1,1,m,E[i].l,E[i].r,i);
	}
	T.dfs(1,1,m);
	for(int i=1; i<=qcnt; ++i)
		puts(ans[i]?"Yes":"No");
	return 0;
}