#P8516. 排序
排序
题目描述
给定长度为 的正整数数组 。将它按非降序排列后得到目标数组 。初始没有可反复使用的交换对,接下来有四类操作。
1 A B:立即交换当前数组 的第 项和第 项。2 A B:把位置 与位置 加入允许交换的集合。这一步不立即交换当前元素。3:询问是否可以用允许交换的操作把当前 变成 。每种允许交换均可使用任意次,使用顺序不限。4:询问有多少个无序位置对 满足下面的条件。
把位置作为顶点,将允许交换的位置对视为无向边。每个位置所属的连通分量称为它的群集。若只使用群集内部的允许交换,便能使群集中所有位置 都达到 ,则称该群集良好。
对于第 4 类询问, 和 必须属于不同群集,两个群集当前都不良好,且将 加入允许交换集合后,合并得到的群集良好。每个无序位置对只计一次。询问本身不修改数组或集合。
输入格式
第一行两个正整数 ,分别表示数组长度和操作数。第二行 个正整数表示初始数组 。接下来 行给出操作。第 1、2 类操作额外给出两个下标 。
输出格式
对每个第 3 类询问输出 YES 或 NO,对每个第 4 类询问输出一个非负整数。每个答案占一行。
样例
3 5
1 3 2
4
3
2 2 3
4
3
1
NO
0
YES
5 5
4 2 1 4 4
3
4
1 1 3
3
4
NO
1
YES
0
4 10
2 1 4 3
3
4
1 1 2
3
4
2 2 3
2 1 2
4
2 3 4
3
NO
2
NO
1
3
YES
数据范围
,。对于 的数据,。
原 PDF 的一条注释写成了有序对,本站按原样例与评测数据计无序对。