2024-06-08 19:14:02
发布于：浙江
翻译
多米尼克设想了一个正整数p1，…，pn的数组。让我们将该数组的排序版本表示为q1，…，qn。
此外，他还设想了一系列允许的换人。如果一对（X，Y）是允许替换集合的成员，Dominik可以交换数组p中X和Y位置的数字。
Marin正在向Dominik Q提供查询，每个查询都属于以下类型之一：
交换A和B位置的数字。
将对（A，B）添加到允许的替换集合中。
马林可以给已经在允许换人范围内的一对（A，B）。
看看是否可以只使用允许的替换对数组进行排序？
替换可以按任意顺序使用，并且每个替换可以进行任意次数。
如果从位置a的数字可以仅使用允许的字幕转移到位置B，那么我们调用一对链接的位置（a，B）。
让我们把链接到位置A的所有位置的集合称为A的云。
如果云中的每个位置j都可以使用一系列允许的替换来实现pj=qj，那么云就是好的。
你必须回答存在多少对不同的位置（A，B），使其保持：
a.位置a和B没有链接。B.a的云不好，B的云也不好。c.如果我们将对（a，B）添加到允许的替换集，则a的云（通过链接a的云和B的云创建）变好。
请注意：对（A，B）和（B，A）被认为是同一对。
输入格式
输入的第一行包含整数N和Q（1≤N，Q≤1000 000）。
第二行输入包含N个整数p1、…、pn（1≤p1、…，pn≤1000 000）。
以下Q行中的每一行都包含以下格式的查询：
● 行中的第一个数字是集合{1,2,3,4}中的查询T的类型。
● 如果查询T的类型是1或2，则后面跟着两个不同的整数A和B（1≤A，B≤N）
其表示取代（A、B）。
输出格式
对于每个类型为3或4的查询，在其单独的行中输出答案。
类型3的查询答案是“DA”（克罗地亚语表示是）或“NE”（克罗地亚文表示否），不带引号，类型4的查询答案为任务中的非负整数。
输入输出样例
输入#1.
复制
3 5
1 3 2
4.
3.
2 2 3
4.
3.
输出#1.
复制
1.
氖
0
DA
输入#2.
复制
5 5
4 2 1 4 4
3.
4.
1 1 3
3.
4.
输出#2.
复制
氖
1.
DA
0
输入#3.
复制
4 10
2 1 4 3
3.
4.
1 1 2
3.
4.
2 2 3
2 1 2
4.
2 3 4
3.
输出#3.
复制
氖
2.
氖
1.
3.
DA
说明/提示
在占总分50%的测试用例中，它将保持N，Q≤1000。
第一个测试用例的说明：
第一个查询的答案是1，因为位置对（2，3）满足所有给定的要求。
第二个查询的答案是NE（否），因为无法将数字2和3转移到
对应的位置，因为所允许的替换的集合是空的。
在第三个查询之后，我们将对（2，3）添加到允许的替换集合中。
第四个查询的答案现在是0，因为2和3已经链接，而第五个查询的回答
查询为DA（是），因为可以通过应用允许的替换（2，3）对数组进行排序。
这里空空如也
有帮助，赞一个