CF571D Campus

Oscolcovo 城市有一个校园，包含 $n$ 个学生宿舍、$n$ 所大学和 $n$ 个军事部门。最初，第 $i$ 个宿舍属于第 $i$ 所大学，并分配给第 $i$ 个军事部门。 生活不断变化，校园持续发生以下四种类型的变化： 1. 大学 $a_{j}$ 与大学 $b_{j}$ 合并。合并后，原本属于大学 $b_{j}$ 的所有宿舍都归属到大学 $a_{j}$，大学 $b_{j}$ 消失。 2. 军事部门 $c_{j}$ 与军事部门 $d_{j}$ 合并。合并后，原本分配给军事部门 $d_{j}$ 的所有宿舍都划归到军事部门 $c_{j}$，军事部门 $d_{j}$ 消失。 3. 大学 $x_{j}$ 的学生入住其所属的所有宿舍。设当前属于该大学的宿舍数量为 $k_{xj}$，则属于该大学的每个宿舍的学生人数增加 $k_{xj}$（注意，大学拥有的宿舍越多，每个宿舍入住的学生就越多）。 4. 军事部门 $y_{j}$ 对所有分配给它的宿舍进行突袭，将这些宿舍中的所有学生带走。 因此，在任意时刻，每个宿舍都准确归属于一个大学和一个军事部门。最初，所有宿舍都是空的。 你的任务是依次处理所有变更，并回答宿舍 $q_{j}$ 当前有多少学生。

第一行包含两个整数 $n$ 和 $m$，表示宿舍数和操作数，$1 \leq n, m \leq 5 \cdot 10^{5}$。 接下来的 $m$ 行中每行描述一个操作，格式如下之一： - “U $a_{j}$ $b_{j}$”——大学合并操作； - “M $c_{j}$ $d_{j}$”——军事部门合并操作； - “A $x_{j}$”——大学 $x_{j}$ 的学生入住操作； - “Z $y_{j}$”——军事部门 $y_{j}$ 突袭操作； - “Q $q_{j}$”——查询宿舍 $q_{j}$ 当前的学生人数。 所有操作中的数字均为正整数，且不超过 $n$。保证在出现的时刻，操作所涉及的大学和军事部门均存在。

对于每条宿舍人数查询，依次在一行输出当前的学生人数。

以第一个样例为例： - 第一次操作时，大学 1 只拥有宿舍 1，因此宿舍 1 在操作后有 1 个学生。 - 第三次操作后，大学 1 拥有了宿舍 1 和 2。 - 第四次操作使所有属于大学 1 的宿舍人数增加 2，所以宿舍 1 和宿舍 2 分别增加 2 名学生。此时宿舍 1 有 3 人，宿舍 2 有 2 人。 - 第五次操作，军事部门 1 管辖的宿舍 1 内的学生人数清零。 由 ChatGPT 5 翻译