UOJ233 【IOI2015】Sorting 题解

题目链接：#233. 【IOI2015】Sorting

题意：

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 调用这个函数刚好一次。

$N$ : 序列 $S$ 的长度.

$S$ : 一个整数数组，表示初始序列 $S$。

$M$ : Ermek 打算做交换的次数。

$X,Y$ : 长度为 $M$ 的整数数组. 对于 $0\le i \le M - 1$, 在第 $i$ 轮 Ermek 打算交换下标为 $X[i]$ 和 $Y[i]$ 的数组。

$P,Q$ : 整数数组。利用这两个数组报告 Aizhan 完成对序列 $S$ 排序的一种可能的交换序列，假设这个交换序列的长度为 $R$，对于 $0$ 到 $R$ 之间的每个 $R$，Aizhan 在轮次 $i$ 选择的下标将被存入 $P[i]$ 和 $Q[i]$。你可以假设数组 $P$ 和 $Q$ 均已分别被分配了 $M$ 个元素。

这个函数应返回 $R$ 的值 (定义如上)。

数据范围：

$1\le N \le 2\times 10^5, M=3N$

数据保证存在一个仅需 $M$ 或更少轮次的交换序列来完成排序。

~~回来的感觉真好。又可以发题解啦！！~~

这题~~一眼博弈论~~，结果不是博弈论 QAQ

注意到答案的单调性，即第 $k$ 步能完成，则第 $k+1$ 步也可以。于是考虑二分最小的交换次数 $R$ 。

考虑将原数组写成置换的形式（上面是下标，下面是数组对应的数）

$\begin{pmatrix} 0&1&2&3&4 \\3&0&4&2&1 \end{pmatrix}$

根据置换的性质可知，对于每次交换，交换上面的两个元素或交换下面的两个元素是等价的

例如交换 $1,3$ ，可以发现这两种交换都不会变

$\begin{pmatrix} 0&1&2&3&4 \\3&0&4&2&1 \end{pmatrix} \rightarrow \begin{cases} \begin{pmatrix} 0&\boldsymbol{3}&2&\boldsymbol{1}&4 \\3&0&4&2&1 \end{pmatrix} \\\\ \begin{pmatrix} 0&1&2&3&4 \\3&\boldsymbol{2}&4&\boldsymbol{0}&1 \end{pmatrix} \end{cases}$

然后就有趣了，我们可以直接把 Ermek 和 Aizhan 的操作独立出来

也就是 Ermek 先做完他的前 $R$ 个操作，然后再让 Aizhan 去交换。

接下来就转化为了一个经典的问题：长度为 $n$ 的排列，交换最少次数使得数组有序

答案就是 $n-p$ ，其中 $p$ 就是环的个数，详见无序数组交换任意两个元素最少交换次数

不过这个题目要输出方案，因此我们还要顺便维护一下需要交换哪些元素

时间复杂度 $\mathcal{O}(n \log n)$

代码：

#include "sorting.h"
#include <bits/stdc++.h>
using namespace std;
// #define int long long
// #define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(2e5+15))

int n,m,*s,*x,*y,*p,*q,tim,a[N],tag[N];
void c(int u,int v) { swap(a[s[u]], a[s[v]]); swap(s[u], s[v]); }
int work(int t)
{
    int cur=0; ++tim;
    memcpy(a, s, (n+5) * sizeof(int)); 
    for(int i=0; i<t; i++) swap(a[x[i]], a[y[i]]);
    for(int i=0; i<n; i++)
        if(tag[i] != tim)
        {
            for(int j=i; tag[j] != tim; j=a[j])
            { tag[j] = tim, 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)
{
    n = _n; s = _s; m = _m; x = _x; y = _y; p = _p; q = _q;
    int l=0, r=n; 
    while(l < r)
    {
        int mid = (l+r) >> 1;
        work(mid) <= mid ? r=mid : l=mid+1;
    }
    int t=work(l);
    for(int i=0; i<n; i++) a[s[i]] = i;
    for(int i=0; i<t; i++) c(x[i], y[i]), c(p[i]=a[p[i]], q[i]=a[q[i]]);
    for(int i=t; i<l; i++) p[i] = q[i] = 0;
    return l;
}