CF566D Restructuring Company

即使是最成功的公司也可能会经历危机时期，这时你需要做出艰难的决定——重组、裁撤和合并部门、裁员以及其他一些不愉快的事情。我们来考虑如下公司的模型。 有 $n$ 个人在大型软件公司工作。每个人属于某个部门。最开始时，每个人都在自己的部门独立负责一个项目（因此公司最初有 $n$ 个部门，每个部门仅有一人）。 然而，困境来临，公司不得不雇佣一位危机管理者来重建工作流程，提升效率。我们用 $team(person)$ 表示员工 $person$ 所在的部门。危机管理者可以进行如下两类操作： 1. 合并 $team(x)$ 和 $team(y)$ 两个部门，将 $team(x)$ 和 $team(y)$ 中的所有员工合并到一个新的大部门中，这里 $x$ 和 $y$（$1 \leq x, y \leq n$）为公司中两位员工的编号。如果 $team(x)$ 与 $team(y)$ 相同，则不发生任何变化。 2. 合并 $team(x), team(x+1), ..., team(y)$ 这连续的一段部门，即把第 $x$ 位到第 $y$ 位员工各自所在的部门全部合并成一个部门，其中 $1 \leq x \leq y \leq n$。 除此之外，危机管理者有时会想知道，第 $x$ 个和第 $y$ 个员工（$1 \leq x, y \leq n$）是否在同一个部门。 请帮助危机管理者，回答他所有的提问。

输入的第一行包含两个整数 $n$ 和 $q$（$1 \leq n \leq 200000$，$1 \leq q \leq 500000$），代表公司员工人数和危机管理者的询问数。 接下来的 $q$ 行，每行给出一个危机管理者的操作，格式为 $type\ x\ y$，其中 。如果 $type=1$ 或 $type=2$，则该行表示危机管理者对于合并部门的第一种或第二种类型的决策。如果 $type=3$，你的任务是判断编号为 $x$ 和 $y$ 的两位员工是否在同一部门。注意，任何类型的操作中 $x$ 可以等于 $y$。

对于每个 $type=3$ 的询问，如果这两位员工在同一个部门，则输出 "YES"；否则输出 "NO"（均不包含引号）。

由 ChatGPT 5 翻译