AdditionalFile4853.zip

P9867 [POI 2021/2022 R2] kon

题目背景

翻译自 POI2021~2022R2 Day2T2。

题目描述

有一个舞会，一开始角色只有 $1$、$2$，他们两个都愿意和彼此跳舞。

然后存在 $q$ 个事件，分别对应下方的操作：

• W x：表示新加入一个人，他和编号 $x$ 的人愿意互相和对方跳舞。
• Z x：表示新加入一个人，初始时他和编号为 $x$ 的人愿意跳舞的对象都互相同意跳舞。
• ? x：表示查询愿意与 $x$ 跳舞的有几个人。

新加入的人的编号是当前人数加一。

输入格式

第一行一个整数 $q\ (1 \leq q \leq 10^6)$。

然后 $q$ 行，每行一个字符和一个整数 $x$，含义如题目描述所述。

输出格式

对应每个 ? 操作，输出一行答案。

输入输出样例 #1

输入 #1

7
? 1
Z 2
? 1
Z 1
W 2
? 2
? 3

输出 #1

1
2
3
2

说明/提示

样例解释：

子任务分配：

子任务编号	特殊性质	分值
$1$	$q \leq 5000$	$20$
$2$	仅包含操作 Z 和 ?	$10$
$3$	? 总是在 $q$ 次操作的末尾部分出现	$35$
$4$	无附加限制

#4853. 「POI 2021/2022 R2」Konkurs tańca towarzyskiego

标签: 传统 | 时间限制: 10000 ms | 内存限制: 256 MiB |

题目描述

题目译自 XXIX Olimpiada Informatyczna – II etap Konkurs tańca towarzyskiego

Bajtazar 被选为字节王国伴舞大赛的组织者。为了让报名更顺畅，他为参赛舞者设计了一份报名表。舞者们需要单独报名，每位新报名的舞者可以看到已注册的舞者名单，然后声明自己愿意与其中哪些人共舞。我们假设，如果舞者 $A$ 表示愿意与舞者 $B$ 共舞，那么舞者 $B$ 也愿意与 $A$ 共舞。

Bajtazar 发现，报名的舞者可以分为两类：挑剔型和嫉妒型。挑剔型的舞者只会从已注册的舞者中选择一人共舞；嫉妒型的舞者则声明，他们愿意与某个已注册舞者所选的相同舞伴共舞。为了简化问题，报名的舞者按自然数顺序编号，从 $1$ 开始。初始时，已有编号为 $1$ 和 $2$ 的两位舞者，他们愿意互相共舞。

Bajtazar 已经编写了一个程序来配对舞伴。为了确保程序正常运行，他需要不时查询某个指定舞者当前能与多少人共舞。请你编写一个程序，帮助他回答这些查询。

输入格式

输入的第一行包含一个整数 $q$ $(1 \leq q \leq 1000000)$，表示需要处理的操作数量。接下来的 $q$ 行，每行属于以下三种形式之一：

• $\texttt{W}\ x$：一名新的挑剔型舞者（按顺序分配下一个编号）加入，表示愿意与编号为 $x$ 的舞者共舞；
• $\texttt{Z}\ x$：一名新的嫉妒型舞者（按顺序分配下一个编号）加入，表示愿意与编号为 $x$ 的舞者所选的相同舞伴共舞；
• $\texttt{?}\ x$：Bajtazar 的程序询问，编号为 $x$ 的舞者当前能与多少人共舞（假设至少会有一次这样的询问）。

输出格式

输出应包含与输入中 ? 查询数量相同的行数，每行包含一个整数，作为对 Bajtazar 程序询问的回答。

样例 1

输入

7
? 1
Z 2
? 1
Z 1
W 2
? 2
? 3

输出

1
2
3
2

以下表格展示了每次操作后各舞者的舞伴情况，以及查询涉及的舞者：

舞者	初始	$\texttt{?}\ 1$	$\texttt{Z}\ 2$	$\texttt{?}\ 1$	$\texttt{Z}\ 1$	$\texttt{W}\ 2$	$\texttt{?}\ 2$	$\texttt{?}\ 3$
$1$	$2$	$\leftarrow$	$2,3$	$\leftarrow$	$2,3$	$2,3$
$2$	$1$		$1$		$1,4$	$1,4,5$	$\leftarrow$
$3$			$1$		$1,4$	$1,4$		$\leftarrow$
$4$					$2,3$	$2,3$
$5$						$2$

样例 2

见附加文件下 [kon1.in](file:kon1.in) 和 [kon1.out](file:kon1.out)。

该样例先有 $8$ 名挑剔型舞者，每人选择前一位共舞；然后 $10$ 名嫉妒型舞者，每人嫉妒前 $10$ 位；最后查询所有舞者；

样例 3

见附加文件下 [kon2.in](file:kon2.in) 和 [kon2.out](file:kon2.out)。

该样例有 $2000$ 名舞者，挑剔型（与第 $1$ 位共舞）和嫉妒型（嫉妒第 $1$ 位）交替出现；半数舞者加入后及最后查询所有舞者；

样例 4

见附加文件下 [kon3.in](file:kon3.in) 和 [kon3.out](file:kon3.out)。

该样例有 $500000$ 名舞者，每人嫉妒前第 $2$ 位；每加入一人后查询该舞者。

数据范围与提示

详细子任务附加限制及分值如下表所示。

子任务编号	附加限制	分值
$1$	$q \leq 5000$	$20$
$2$	所有新加入的舞者均为嫉妒型	$10$
$3$	所有 ? 查询在报名结束后进行	$35$
$4$	无附加限制	$35$