P6498 [COCI 2016/2017 #2] Zamjene

**警告：滥用本题评测将被封号。**

Dominik 构造了一个含有 $n$ 个元素的数组 $p_1,p_2,\dots,p_n$，和对其排序得到的数组 $q_1,q_2,\dots,q_n$。 此外，他还定义了「可交换集」。若无序数对 $(a,b)$ 属于「可交换集」，则他可以交换 $p_a,p_b$ 的位置。『通过「可交换集」』，即为**通过若干次这样的交换**。 现有四种操作： - 操作 $1$： 格式：`1 a b`。 交换 $p_a,p_b$ 的位置（不受「可交换集」限制）。 - 操作 $2$： 格式：`2 a b`。 将无序数对 $(a,b)$ 加入「可交换集」。 - 操作 $3$： 格式：`3`。 判断能否通过「可交换集」完成对数组 $p$ 的排序。 - 操作 $4$： 格式：`4`。 若数组 $p$ 中的第 $x$ 个元素能通过「可交换集」移至第 $y$ 位，则称 $x,y$ 是相连的。其中 $x$ 可能等于 $y$。 将所有与 $x$ 相连的 $y$ 构成的集合称作 $x$ 的「云」。若一朵「云」能通过「可交换集」使得「云」中任意的 $i$ 满足 $p_i=q_i$，则称这朵「云」是「祥云」。 计算有多少组无序数对 $(a,b)$ 满足： - $1\le a,b\le n$ 且 $a\not=b$。 - $a,b$ 不是相连的。 - $a$ 的「云」与 $b$ 的「云」均不是「祥云」。 - 将无序数对 $(a,b)$ 加入「可交换集」后，$a$ 的「云」变为「祥云」。 请你帮助 Dominik 完成这些操作。

无

无

#### 样例 1 解释 - 第一次操作：仅有无序数对 $(2,3)$ 满足要求。 - 第二次操作：不能通过「可交换集」完成对数组 $p$ 的排序。 - 第三次操作：将无序数对 $(2,3)$ 加入「可交换集」。 - 第四次操作：不存在满足要求的无序数对。 - 第五次操作：交换 $p_2,p_3$，即可通过「可交换集」完成对数组 $p$ 的排序。 ------------ #### 数据规模与约定 对于 $100\%$ 的数据，$1\le n,q\le 10^6$，$1\le p_i\le 10^6$，$1\le t\le 4$，$1\le a,b\le n$ 且 $a\not=b$。 ------------ #### 说明 **题目译自 [COCI2016-2017](https://hsin.hr/coci/archive/2016_2017/) [CONTEST #2](https://hsin.hr/coci/archive/2016_2017/contest2_tasks.pdf) _T5 Zamjene_**。