CF1423H Virus

在 Bubbleland，有一支特殊的编程部队接到了一项绝密任务：计算可能被一种新型未知病毒感染的人数。该国人口为 $n$，每天都会有关于人员接触的新信息。特殊编程部队的任务是计算给定人员在最近 $k$ 天内的接触人数。 这种新病毒的潜伏期为 $k$ 天，超过该时间后，人们被认为不再具有传染性。由于该病毒极其危险，政府将所有在最近 $k$ 天内有直接或间接接触的人都标记为“可疑”，无论接触的顺序如何。 这种病毒非常奇怪，人们无法获得持久免疫力。 你需要帮助特殊编程部队计算给定人员的可疑人数（即与该人员有接触的人数）。 初始输入有 3 个整数 $n$（人口数）、$q$（查询数）、$k$（病毒潜伏期天数）。每个查询有三种类型： 1. ($x$, $y$)：第 $x$ 个人和第 $y$ 个人在当天相遇（$x \neq y$）。 2. ($z$)：返回与第 $z$ 个人有接触的人数，包括他自己。 3. 表示当天结束，进入下一天。

第一行输入包含三个整数 $n$（$1 \le n \le 10^5$，人口数）、$q$（$1 \le q \le 5 \times 10^5$，查询数）、$k$（$1 \le k \le 10^5$，病毒潜伏期天数）。 接下来的 $q$ 行，每行以一个整数 $t$（$1 \le t \le 3$，查询类型）开头。 若为第一类查询，后跟两个整数 $x$ 和 $y$（$1 \le x, y \le n$，$x \neq y$）。 若为第二类查询，后跟一个整数 $i$（$1 \le i \le n$）。 第三类查询后无其他数字。

对于每个第二类查询，输出一行，表示当前与指定人员有接触的人数。

请注意，如果第 1 天 1 号和 2 号有接触，第 2 天 1 号和 3 号有接触，且 $k > 1$，那么第 3 号的接触人数为 3（包括 1、2、3 号）。 由 ChatGPT 4.1 翻译