#PU1186. USACO 2022 January Contest, Gold — Problem 2. Farm Updates

    ID: 1492 传统题 2000ms 256MiB 尝试: 0 已通过: 0 难度: 提高+/省选- 上传者: 标签>USACO赛事:jan22来源:usaco.orgscoring:equal_test_cases并查集树状数组

USACO 2022 January Contest, Gold — Problem 2. Farm Updates

USACO 2022 January Contest, Gold — Problem 2. Farm Updates

题目描述

Farmer John operates a collection of NN farms (1≤N≤1051\le N\le 10^5), conveniently numbered 1…N1\ldots N. Initially, there are no roads connecting these farms to each-other, and each farm is actively producing milk. Due to the dynamic nature of the economy, Farmer John needs to make changes to his farms according to a series of QQ update operations (0≤Q≤2⋅1050\le Q\le 2\cdot 10^5). Update operations come in three possible forms: (D x) Deactivate an active farm xx, so it no longer produces milk. (A x y) Add a road between two active farms xx and yy. (R e) Remove the eeth road that was previously added (e=1e = 1 is the first road that was added). A farm xx that is actively producing milk, or that can reach another active farm via a series of roads, is called a "relevant" farm. For each farm xx, please calculate the maximum ii (0≤i≤Q0\le i\le Q) such that xx is relevant after the ii-th update.

输入格式

The first line of input contains NN and QQ. The next QQ lines each contain an update of one of the following forms: D x A x y R e It is guaranteed that for updates of type R, ee is at most the number of roads that have been added so far, and no two updates of type R have the same value of ee.

输出格式

Please output NN lines, each containing an integer in the range 0…Q0\ldots Q.

数据范围

Tests 2 through 5 satisfy N≤103N\le 10^3, Q≤2⋅103Q\le 2\cdot 10^3 Test cases 6 through 20 satisfy no additional constraints. Problem credits: Benjamin Qi

样例

样例 1

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
In this example, roads are removed in the order $(2,3), (1,2), (2,4)$.
Farm $1$ is relevant just before $(1,2)$ is removed.
Farm $2$ is relevant just before $(2,4)$ is removed.
Farm $3$ is relevant just before $(2,3)$ is removed.
Farms $4$ and $5$ are still active after all queries. Therefore they both
stay relevant, and the output for both should be $Q$.