题目大意
给定一个 $n$ 个点的图和 $m$ 个操作。图一开始是空的，每次操作可以在图中加上一条边，删去一条边或者询问两个点是否连通。你要对于所有询问求出答案。
数据范围：$n \le 5 \times 10^3, m \le 5 \times 10^5$。
思路分析
不知道这个 $n \le 5 \times 10^3$ 有什么用 \kel。
如果只有加边的话，我们可以直接使用并查集来做。如果带上删边，我们就可以使用按时间分治的技巧。具体地，我们将每条边出现的时间和被删除的时间处理出来，然后在时间的线段树上插入对应的区间。最后，我们 DFS 一遍线段树就可以求出所有答案了。
那么我们需要支持的操作就是连边和撤销上一次连边。发现并不需要可持久化，我们只需要可回退的并查集就行了。对于一次 merge 操作，我们将它的信息记录下来，撤销的时候再还原即可。注意我们不能路径压缩，所以需要启发式合并来优化。时间复杂度 $O(m \log^2 m)$，具体见代码。
代码实现
1 | |
2 | |
3 | |
4 | |
5 | using namespace std; |
6 | |
7 | const int maxn = 5e5, maxm = 1 << 20; |
8 | int n, m, o[maxn + 3], u[maxn + 3], v[maxn + 3], fa[maxn + 3], sz[maxn + 3]; |
9 | int top, st_u[maxn + 3], st_v[maxn + 3], st_o[maxn + 3], st_s[maxn + 3]; |
10 | bool ans[maxn + 3]; |
11 | vector<int> S[maxm + 3]; |
12 | map<pair<int, int>, int> mp; |
13 | |
14 | void modify(int rt, int l, int r, int lx, int rx, int x) { |
15 | if (l >= lx && r <= rx) { |
16 | S[rt].push_back(x); |
17 | return; |
18 | } |
19 | if (lx <= mid) { |
20 | modify(ls, l, mid, lx, rx, x); |
21 | } |
22 | if (rx > mid) { |
23 | modify(rs, mid + 1, r, lx, rx, x); |
24 | } |
25 | } |
26 | |
27 | int find(int x) { |
28 | return fa[x] == x ? x : find(fa[x]); |
29 | } |
30 | |
31 | void merge(int u, int v) { |
32 | u = find(u), v = find(v); |
33 | if (sz[u] > sz[v]) { |
34 | swap(u, v); |
35 | } |
36 | ++top, st_u[top] = u, st_v[top] = v, st_o[top] = fa[u], st_s[top] = sz[u]; |
37 | if (u != v) { |
38 | fa[u] = v, sz[v] += sz[u], sz[u] = 0; |
39 | } |
40 | } |
41 | |
42 | void split() { |
43 | int u = st_u[top], v = st_v[top], o = st_o[top], s = st_s[top]; |
44 | if (u != v) { |
45 | fa[u] = o, sz[v] -= s, sz[u] = s; |
46 | } |
47 | top--; |
48 | } |
49 | |
50 | void insert(int x) { |
51 | for (int i = 0; i < S[x].size(); i++) { |
52 | merge(u[S[x][i]], v[S[x][i]]); |
53 | } |
54 | } |
55 | |
56 | void erase(int x) { |
57 | for (int i = S[x].size() - 1; i >= 0; i--) { |
58 | split(); |
59 | } |
60 | } |
61 | |
62 | void solve(int rt, int l, int r) { |
63 | insert(rt); |
64 | if (l == r) { |
65 | if (o[l] == 2) { |
66 | ans[l] = find(u[l]) == find(v[l]); |
67 | } |
68 | erase(rt); |
69 | return; |
70 | } |
71 | solve(ls, l, mid); |
72 | solve(rs, mid + 1, r); |
73 | erase(rt); |
74 | } |
75 | |
76 | int main() { |
77 | scanf("%d %d", &n, &m); |
78 | for (int i = 1; i <= m; i++) { |
79 | scanf("%d %d %d", &o[i], &u[i], &v[i]); |
80 | if (u[i] > v[i]) { |
81 | swap(u[i], v[i]); |
82 | } |
83 | if (!o[i]) { |
84 | mp[make_pair(u[i], v[i])] = i; |
85 | } else if (o[i] == 1) { |
86 | modify(1, 1, m, mp[make_pair(u[i], v[i])], i - 1, i); |
87 | mp[make_pair(u[i], v[i])] = 0; |
88 | } |
89 | } |
90 | for (map<pair<int, int>, int>::iterator it = mp.begin(); it != mp.end(); it++) { |
91 | if (it -> second) { |
92 | modify(1, 1, m, it -> second, m, it -> second); |
93 | } |
94 | } |
95 | for (int i = 1; i <= n; i++) { |
96 | fa[i] = i, sz[i] = 1; |
97 | } |
98 | solve(1, 1, m); |
99 | for (int i = 1; i <= m; i++) { |
100 | if (o[i] == 2) { |
101 | puts(ans[i] ? "Y" : "N"); |
102 | } |
103 | } |
104 | return 0; |
105 | } |