Aizhan 有一个由 $N$ 个互不相同的整数组成的序列 $S[0], S[1], \ldots, S[N - 1]$，其中 $S[i]$ 取值范围是 $[0, N - 1]$。Aizhan 试图通过交换某些元素对的方法将这个序列按照升序排序。Aizhan 的朋友 Ermek 也想交换某些元素对，Ermek 的交换未必有助于 Aizhan 的排序。
Ermek 和 Aizhan 打算通过若干轮次来修改这个序列。在每一轮，Ermek 首先做一次交换，然后 Aizhan 做另一次交换。更确切地说，做交换的人选择两个有效的下标并交换这两个下标的元素。请注意这两个下标可能相同。如果它们相等，则对这个元素自身做交换，并不改变这个序列。
Aizhan 知道 Ermek 并不关心对序列 $S$ 排序的事情。Aizhan 还知道 Ermek 将会选择哪些下标。Ermek 打算参加 $M$ 轮交换，将这些轮次从 $0$ 到 $M - 1$ 编号。对于 $0$ 到 $M - 1$ 之间的每个 $i$，Ermek 在第 $i$ 轮将选择下标 $X[i]$ 和 $Y[i]$ 的元素进行交换。
Aizhan 要对序列 $S$ 按升序进行排序。在每一轮之前，如果 Aizhan 看到当前的序列已经按升序排列，她将结束这个排序过程。给定初始序列 $S$ 以及 Ermek 要选择的下标，请你找出一个交换的序列，使得 Aizhan 能完成对序列 $S$ 的排序。此外，在有些子任务中，你还要找出尽可能短的交换序列来完成排序任务。题目保证通过 $M$ 或更少的轮次能够将序列 $S$ 排好序。
请注意如果 Aizhan 发现在 Ermek 的交换之后，序列 $S$ 已经排好序，则 Aizhan 可以选择交换两个相同下标 (例如 $0$ 和 $0$) 的元素。这样，序列 $S$ 在这一轮次之后也完成排序，于是也达到了 Aizhan 的目标。另外，如果初始序列 $S$ 就已经排好序，那么所需的最少排序轮数就是 $0$。
给定序列 $S$、$M$ 和下标序列 $X$ 和 $Y$，请找出 Aizhan 对序列 $S$ 完成排序所需的交换的序列。在子任务 5-6 中，你找出的交换序列必须是最短的。
你需要实现函数 findSwapPairs：
findSwapPairs(N, S, M, X, Y, P, Q) —— grader 调用这个函数刚好一次。
注意到答案函数的单调性 ($R$ 步内可以完成 $\Rightarrow$ $R + 1$ 步内也能完成)，于是我们首先二分答案 $R$，将问题转化为能否在 $R$ 步内完成排序。
我们可以将每个元素看作一个 std::pair <int, int>，于是整个排列可以看作一个数组 std::pair <int, int> c[N]，其中 c[i].first 依次为 $0 \sim N - 1$，c[i].second 就为待排列的数组。比如，样例 2 对应的排列就是 (写成置换的形式)
$$ \dbinom {0 \quad 1 \quad 2 \quad 3 \quad 4} {3 \quad 0 \quad 4 \quad 2 \quad 1} $$ (其中第一行为 first，第二行为 second)
现在考虑 Ermek 的每一次交换，设它交换的下标为 $x, y$，则我们在 first 行中找到元素 $x$ 和 $y$ 并交换。比如，上面的置换中，依次交换下标为 $2, 3$ 和下标为 $3, 4$ 的元素后，置换的变化如下：
$$ \dbinom {0 \quad 1 \quad 2 \quad 3 \quad 4} {3 \quad 0 \quad 4 \quad 2 \quad 1} \to \dbinom {0 \quad 1 \quad 3 \quad 2 \quad 4} {3 \quad 0 \quad 4 \quad 2 \quad 1} \to \dbinom {0 \quad 1 \quad 4 \quad 2 \quad 3} {3 \quad 0 \quad 4 \quad 2 \quad 1} $$ (注意 second 行不动)
再考虑 Aizhan 的每一次交换，设它交换的值为 $p, q$，则在 second 行中找到元素 $p$ 和 $q$ 并交换。比如，在上面的置换中，再交换值为 $2, 3$ 和值为 $3, 4$ 的元素后，置换的变化如下：
$$ \dbinom {0 \quad 1 \quad 4 \quad 2 \quad 3} {3 \quad 0 \quad 4 \quad 2 \quad 1} \to \dbinom {0 \quad 1 \quad 4 \quad 2 \quad 3} {2 \quad 0 \quad 4 \quad 3 \quad 1} \to \dbinom {0 \quad 1 \quad 4 \quad 2 \quad 3} {2 \quad 0 \quad 3 \quad 4 \quad 1} $$
这样做有什么性质呢？可以发现，不管是哪一种交换，只要将交换好的序列的第一行进行排序 (由于是置换，第二行的顺序也会变化)，那么第二行的结果就是当前状态下的数组 (排列)。
进一步，可以发现，通过这样转化后，Ermek 的交换和 Aizhan 的交换就彼此独立了，因为 Ermek 只管第一行，Aizhan 只管第二行。
因此对二分的 $R$，我们可以首先将 Ermek 的 $R$ 次操作全部做完，接下来，就只有 Aizhan 在排序 (没人来捣乱) 了。
于是问题就转化为，给定一个排列，问至少交换多少对元素 (可以不相邻)，才能将其 (升序) 排序？
这是一个非常经典的问题，结论是，将这个排列写成置换的形式，设该置换有 $k$ 个循环，则需要交换 $N - k$ 次。
证明：容易发现，每次交换一对元素，至多增加或减少一个循环，而最终的排列有 $N$ 个循环，故至少交换 $N - k$ 次。
因此，我们对这个剩下的排列，$O(N)$ 求循环个数 $k$，判断 $N - k$ 是否小于等于 $R$，如果是，则说明可行。
至于输出方案，我们在求循环个数的时候，可以顺便维护需要交换哪些元素 (注意存储值而不是下标)，最后输出的时候模拟这个置换改变的过程即可 (即维护当前置换和它的逆置换)。
时间复杂度 $O \left( N \log N \right)$。
#include "sorting.h"
#include <bits/stdc++.h>
#define N 200010
using std::swap;
int n, m, *s, *x, *y, *p, *q;
int L, R, M;
int stamp = 0, a[N], tag[N];
inline void Swap(int u, int v) {swap(a[s[u]], a[s[v]]), swap(s[u], s[v]);}
int work(int X) {
int i, j, cur = 0; ++stamp;
memcpy(a, s, n << 2);
for (i = 0; i < X; ++i) swap(a[x[i]], a[y[i]]);
for (i = 0; i < n; ++i)
if (tag[i] != stamp) {
for (j = i; tag[j] != stamp; j = a[j])
tag[j] = stamp, p[cur] = j, q[cur++] = a[j];
--cur;
}
return cur;
}
int findSwapPairs(int _n, int *_s, int _m, int *_x, int *_y, int *_p, int *_q) {
int i, fy; n = _n; s = _s; m = _m; x = _x; y = _y; p = _p; q = _q;
for (L = 0, R = n; L < R; )
M = (L + R) / 2, work(M) <= M ? R = M : (L = M + 1);
fy = work(L);
for (i = 0; i < n; ++i) a[s[i]] = i;
for (i = 0; i < fy; ++i) Swap(x[i], y[i]), Swap(p[i] = a[p[i]], q[i] = a[q[i]]);
for (; i < L; ++i) p[i] = q[i] = 0;
return L;
}
坑1：注意到 $N - 1$ 次内一定有解 (且 $M \geq N$)，因此二分上界可以写成 $N - 1$ 而不是 $M$。