P8097 [USACO22JAN] Farm Updates G

题目描述

Farmer John 经营着总共 $N$ 个农场（$1\le N\le 10^5$），编号为 $1\dots N$。最初，这些农场之间没有道路连接，并且每个农场都在活跃地生产牛奶。

由于经济的动态性，Farmer John 需要根据 $Q$ 次更新操作（$0\le Q\le 2\cdot 10^5$）对他的农场进行改造。更新操作有三种可能的形式：

• (D x) 停用一个活跃的农场 $x$，使其不再生产牛奶。

• (A x y) 在两个活跃的农场 $x$ 和 $y$ 之间添加一条道路。

• (R e) 删除之前添加的第 $e$ 条道路（$e=1$ 是添加的第一条道路）。

一个农场 $x$ 如果正在活跃地生产牛奶，或者可以通过一系列道路到达另一个活跃的农场，则称之为一个「有关的」农场。对于每个农场 $x$，计算最大的 $i$（$0\le i\le Q$），使得农场 $x$ 在第 $i$ 次更新后是有关的。

输入格式

输入的第一行包含 $N$ 和 $Q$。以下 $Q$ 行每行包含如下格式之一的一次更新操作：

D x
A x y
R e

输入保证对于 R 类更新，$e$ 不超过已经添加的道路的数量，并且没有两次 R 类更新具有相等的 $e$ 值。

输出格式

输出 $N$ 行，每行包含一个 $0\dots Q$ 范围内的整数。

输入输出样例 #1

输入 #1

5 9
A 1 2
A 2 3
D 1
D 3
A 2 4
D 2
R 2
R 1
R 3

输出 #1

7
8
6
9
9

说明/提示

【样例解释】

在这个例子中，道路以顺序 $(2,3),(1,2),(2,4)$ 被删除。

• 农场 $1$ 在道路 $(1,2)$ 被删除之前是有关的。

• 农场 $2$ 在道路 $(2,4)$ 被删除之前是有关的。

• 农场 $3$ 在道路 $(2,3)$ 被删除之前是有关的。

• 农场 $4$ 和 $5$ 在所有更新结束后仍然是活跃的。所以它们一直保持为有关的，两者的输出均应为 $Q$。

【数据范围】

• 测试点 2-5 满足 $N\le 10^3$，$Q\le 2\cdot 10^3$。

• 测试点 6-20 没有额外限制。

C++实现

#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;
}

后续

接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容