#P8516. 排序

    ID: 8603 传统题 6000ms 512MiB 尝试: 2 已通过: 2 难度: 7 上传者: 标签>CF2300提高+/省选-普通并查集随机赋权检测哈希表贡献法增量维护

排序

题目描述

给定长度为 NN 的正整数数组 PP。将它按非降序排列后得到目标数组 QQ。初始没有可反复使用的交换对,接下来有四类操作。

  1. 1 A B:立即交换当前数组 PP 的第 AA 项和第 BB 项。
  2. 2 A B:把位置 AA 与位置 BB 加入允许交换的集合。这一步不立即交换当前元素。
  3. 3:询问是否可以用允许交换的操作把当前 PP 变成 QQ。每种允许交换均可使用任意次,使用顺序不限。
  4. 4:询问有多少个无序位置对 {A,B}\{A,B\} 满足下面的条件。

把位置作为顶点,将允许交换的位置对视为无向边。每个位置所属的连通分量称为它的群集。若只使用群集内部的允许交换,便能使群集中所有位置 ii 都达到 Pi=QiP_i=Q_i,则称该群集良好。

对于第 4 类询问,AA 和 BB 必须属于不同群集,两个群集当前都不良好,且将 {A,B}\{A,B\} 加入允许交换集合后,合并得到的群集良好。每个无序位置对只计一次。询问本身不修改数组或集合。

原 PDF 题面

输入格式

第一行两个正整数 N,MN,M,分别表示数组长度和操作数。第二行 NN 个正整数表示初始数组 PP。接下来 MM 行给出操作。第 1、2 类操作额外给出两个下标 A,BA,B。

输出格式

对每个第 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

数据范围

1≤N,M,Pi≤1061\le N,M,P_i\le10^6,1≤A,B≤N1\le A,B\le N。对于 50%50\% 的数据,N,M≤1000N,M\le1000。

原 PDF 的一条注释写成了有序对,本站按原样例与评测数据计无序对。