自动搬运

查看原文

来自洛谷，原作者为

	zhiyangfan 诶嘿~

搬运于2025-08-24 22:35:57，当前版本为作者最后更新于2022-02-04 21:44:32，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

给出一张 $n$ 个点的无向图，刚开始所有点的权值都是 $1$，没有边。共有 $q$ 次操作，操作分以下三种：

• R x 将一个点的权值变为 $0$。
• A x y 在两点 $x,y$ 之间连一条边，保证 $x,y$ 的权值均为 $1$。
• D e 删除加入的第 $e$ 条边，边从 $1$ 开始编号。

如果一个点权值为 $1$ 或与权值为 $1$ 的点连通，则定义这个点是「关联的」。对于每个点求最大的 $i(0\le i\le q)$，使得在这次操作后该点是「关联的」。($1\le n\le 10^5,1\le q\le 2\times10^5$)

分析一波这些操作，我们能发现第二个操作似乎并不会改变每个点的关联性。注意到一个连通块内的点关联性都是相同的，而二操作相当于合并两个均为「关联的」的连通块，当然不会改变连通性。所以现在我们要维护的东西就变为了单点修改和删边。显然加边更好处理，所以考虑改成倒序处理。

我们来分析一下倒序的这些操作。

• 将一个点的权值从 $0$ 变为 $1$。此时该点所在的连通块都会变为「关联的」。
• 删除 $x,y$ 之间的边，保证 $x,y$ 的权值均为 $1$。（注意这里依然有这个保证是因为正向做的时候就不会影响 $0,1$）显然不会对关联性造成什么影响，可以忽略。
• 加入第 $e$ 条边。这个操作影响关联性的条件是这条边两边的连通块关联性不同，合并之后就会全变为「关联的」。其他情况就没有影响，直接合并连通块即可。

想一下我们现在的操作，遍历一个连通块，合并两个连通块，而这些一个并查集就可以做到。而倒序操作从非「关联的」变为「关联的」的时间点的上一个时间，就是最终的答案。（注意一个点一旦变为「关联的」就不会再变回去了，因为上面的操作并不会影响到这一点）

实现时不要忘了倒序操作前加入在最后没有删除的边。时间复杂度是均摊的 $\mathcal{O}(n+q)$。

#include <cstdio>
#include <vector>
#include <cstdlib>
const int N = 2e5 + 10; int f[N]; std::vector<int> vec[N];
struct query{ int op, x; }q[N]; int ans[N], vis[N];
struct edge{ int x, y; }e[N]; int tp, del[N];
int getf(int x) { return x == f[x] ? x : f[x] = getf(f[x]); }
inline void link(int u, int v, int now)
{
	u = getf(u), v = getf(v); if (u == v) return ;
	if ((!vis[u]) ^ (!vis[v]))
	{
		if (!vis[u]) for (auto x : vec[u]) vis[x] = now;
		else for (auto x : vec[v]) vis[x] = now;
	}
	if (vec[u].size() > vec[v].size()) { f[v] = u; for (auto x : vec[v]) vec[u].push_back(x); }
	else { f[u] = v; for (auto x : vec[u]) vec[v].push_back(x); }
}
int main()
{
	char op[5]; int x, y, n, Q; scanf("%d%d", &n, &Q);
	for (int i = 1; i <= n; ++i) f[i] = i, vis[i] = Q, vec[i].push_back(i);
	for (int i = 1; i <= Q; ++i)
	{
		scanf("%s", op);
		if (op[0] == 'A') scanf("%d%d", &x, &y), e[++tp].x = x, e[tp].y = y;
		else scanf("%d", &x), q[i].op = op[0] == 'D' ? 1 : 2, q[i].x = x;
	}
	for (int i = 1; i <= Q; ++i) 
		if (q[i].op == 1) vis[q[i].x] = 0;
		else del[q[i].x] = 1;
	for (int i = 1; i <= tp; ++i) if (!del[i]) link(e[i].x, e[i].y, Q);
	for (int i = Q; i >= 1; --i)
	{
		if (!q[i].op) continue;
		if (q[i].op == 1)
		{
			int u = getf(q[i].x);
			if (!vis[u]) for (auto x : vec[u]) vis[x] = i - 1;
		}
		else link(e[q[i].x].x, e[q[i].x].y, i - 1);
	}
	for (int i = 1; i <= n; ++i) printf("%d\n", vis[i]);	
	return 0;
}