Farm Updates

题目描述

Farmer John 经营着 $N$ 个农场（$1\le N\le 10^5$），方便起见编号为 $1\ldots 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$，若其正在生产牛奶，或者可以通过若干条道路到达另一个仍在生产牛奶的农场，则称为“相关（relevant）”农场。对于每个农场 $x$，请计算最大的 $i$（$0\le i\le Q$），使得在第 $i$ 次更新之后，$x$ 仍是相关农场。

输入格式

第一行输入包含 $N$ 和 $Q$。接下来的 $Q$ 行每行包含一种如下形式的更新： D x A x y R e 保证对于类型为 R 的更新，$e$ 至多为目前为止已添加的道路数量，且任意两次类型为 R 的更新不会有相同的 $e$。

输出格式

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

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

7
8
6
9
9

提示

在该示例中，道路按顺序移除：$(2,3), (1,2), (2,4)$。 农场 $1$ 在 $(1,2)$ 被移除之前仍是相关农场。 农场 $2$ 在 $(2,4)$ 被移除之前仍是相关农场。 农场 $3$ 在 $(2,3)$ 被移除之前仍是相关农场。 农场 $4$ 和 $5$ 在所有查询之后仍然处于激活状态。因此它们都会一直保持相关，其输出都应为 $Q$。 SCORING: 测试点 2 到 5 满足 $N\le 10^3$, $Q\le 2\cdot 10^3$ 测试点 6 到 20 没有额外限制。 题目出题人：Benjamin Qi

标签: USACO|2022|Gold

来源

USACO|2022|Gold