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;
}