CF1578B Building Forest Trails

有 $n$ 个村庄等距分布在一个圆上，圆被茂密且无法穿越的森林包围。从古至今，村庄之间无法互相通行，但随着技术进步，现在可以在森林中修建可通行的小路。 修建过程包含 $m$ 个事件。每个事件要么是修建一条小路，要么是查询两个村庄是否连通。小路为连接两个村庄的直线。修建好小路后，任何人都可以沿着小路从一个村庄走到另一个村庄。 此外，如果两条小路相交，任何人都可以在交点处转弯；如果到达的村庄还有其他小路，也可以继续沿着小路前进。例如，若村庄按顺时针编号为 $1$ 到 $6$，且已修建小路 $1$ 到 $3$、$2$ 到 $4$ 和 $4$ 到 $6$，那么除了第 $5$ 个村庄外，其他村庄都可以从第 $1$ 个村庄到达。 给定 $m$ 个事件的列表，对于每个查询，判断在当前时刻两个指定村庄是否可以互相到达。

第一行包含两个整数 $n$（$2 \le n \le 2\cdot 10^5$）和 $m$（$1 \le m \le 3\cdot 10^5$），分别表示村庄数量和事件数量。 接下来的 $m$ 行，每行描述一个事件。每个事件包含三个整数 $e$（$e$ 为 $1$ 或 $2$）、$v$（$1 \le v \le n$）、$u$（$1 \le u \le n$，$u \ne v$）。若 $e = 1$，表示在村庄 $v$ 和 $u$ 之间修建一条小路。若 $e = 2$，表示查询村庄 $v$ 和 $u$ 是否连通。保证每条小路最多只修建一次。 村庄按顺时针顺序编号为 $1$ 到 $n$。

对于每个查询，若两个村庄可以互相到达，输出字符 '1'，否则输出字符 '0'。所有查询的答案按顺序输出在一行中，不要有空格。

由 ChatGPT 4.1 翻译