#P4371. [IOI2015]sorting排序

    ID: 3574 传统题 2000ms 512MiB 尝试: 135 已通过: 34 难度: 8 上传者: 标签>难度分类提高+/省选-排序与序列处理二分答案线性代数与代数置换循环分解单调判定模拟与实现技巧直接模拟CF2400鸣谢yts1999上传鸣谢mcfx提供SPJ

[IOI2015]sorting排序

[IOI 2015] Sorting 排序

题目描述

Aizhan 有一个由整数 0,1,…,N−10,1,\ldots,N-1 组成的排列 SS,她想把它变成升序。Ermek 也会交换这个排列中的元素,他的交换计划预先给定。

两人按轮次交替操作。在第 ii 轮(从 00 编号),Ermek 首先交换下标 Xi,YiX_i,Y_i 处的元素,然后 Aizhan 选择两个下标进行一次交换。所选下标可以相同,此时序列不变。

如果一整轮开始前序列已经升序,排序过程立即结束。若 Ermek 在某轮中的交换已经使序列升序,Aizhan 可以交换两个相同下标来保持不变。若初始序列已经升序,所需轮数为 00。

已知 Ermek 的前 MM 轮计划,并保证可以在至多 MM 轮内排序。求最少轮数 RR,以及 Aizhan 在这 RR 轮中的一种交换方案。

输入格式

第一行一个整数 NN。第二行 NN 个整数 S0,S1,…,SN−1S_0,S_1,\ldots,S_{N-1},给出初始排列。

第三行一个整数 MM。接下来 MM 行依次给出 Ermek 每轮交换的两个下标 Xi,YiX_i,Y_i。

输出格式

第一行输出最少轮数 RR。

接下来恰好 RR 行。第 i+2i+2 行输出两个下标 Pi,QiP_i,Q_i,表示 Aizhan 在第 ii 轮交换的位置,其中 0≤i<R0\le i<R。下标从 00 开始,任意一种最短的合法方案均可。

样例

样例输入 #1

5
4 3 2 1 0
6
0 1
1 2
2 3
3 4
0 1
1 2

样例输出 #1

3
0 4
1 3
3 4

样例输入 #2

5
3 0 4 2 1
5
1 1
4 0
2 3
1 4
0 4

样例输出 #2

3
1 4
4 2
2 2

样例 1 的交换过程:

轮次 Ermek 交换后 Aizhan 交换后
0 (3,4,2,1,0)(3,4,2,1,0) (0,4,2,1,3)(0,4,2,1,3)
1 (0,2,4,1,3)(0,2,4,1,3) (0,1,4,2,3)(0,1,4,2,3)
2 (0,1,2,4,3)(0,1,2,4,3) (0,1,2,3,4)(0,1,2,3,4)

样例 2 的交换过程:

轮次 Ermek 交换后 Aizhan 交换后
0 (3,0,4,2,1)(3,0,4,2,1) (3,1,4,2,0)(3,1,4,2,0)
1 (0,1,4,2,3)(0,1,4,2,3) (0,1,3,2,4)(0,1,3,2,4)
2 (0,1,2,3,4)(0,1,2,3,4)

数据范围

1≤N≤200 0001\le N\le 200\,000,1≤M≤600 0001\le M\le600\,000。所有交换下标在 [0,N−1][0,N-1] 内。

原赛子任务如下。本地题面统一要求 RR 最小。

子任务 分值 NN 的范围 MM Ermek 的交换 原赛对 RR 的要求
1 8 1≤N≤51\le N\le 5 N2N^2 始终交换 (0,0)(0,0) R≤MR\le M
2 12 1≤N≤1001\le N\le 100 30N30N
3 16 始终交换 (0,1)(0,1)
4 18 1≤N≤5001\le N\le 500 无附加限制
5 20 6≤N≤2 0006\le N\le2\,000 3N3N 最小
6 26 6≤N≤200 0006\le N\le200\,000