题解 P5862 【[IOI2015]sorting 排序】
Kinandra
·
·
题解
标签: 构造
Part 1
设 E 的一次操作为 E , A 的一次操作为 A , 那么最终的操作序列应该为 E_1A_1E_2A_2E_3A_3E_4A_4\cdots .
发现一组 AE 操作必定可以转化为一组 EA' , 意思是存在一个 E 先操作一步, A 再操作一步的效果与 A 先操作一步, E 再操作一步的效果相同, 并且对于确定的 E , A 和 A' 是一一对应的.
于是我们不妨把所有 A 移动到 E 的后面, 构造一个这样的操作序列 E_1E_2E_3E_4\cdots A'_1A'_2A'_3A'_4\cdots , 并通过这个序列还原出原序列.
Part 2
考虑从 $A'$ 如何还原为 $A$ , 对于已知的 $A, E,$ 考虑使 $AE=EA'$ 的 $A'$ , 有如下几种情况:
- $A=(a,b),E=(c,d)$ , 则 $A'=(a,b)$ .
- $A=(a,b),E=(a,c)$ , 则 $A'=(b,c)$ .
- $A=(a,b),E=(a,b)$ , 则 $A'=(a,b)$ .
不难发现: $A'$ 还原到 $A$ , 如果 $A'$ 与 $E$ 中有相同的位置, 那么就把这个位置变成 $E$ 中的另一个位置.
#### Part 3
暴力还原原操作序列是 $\mathcal O(n^2)$ 的(一个 $A'$ 需要与 $\mathcal O(n)$ 个 $E$ 交换), 不能承受, 考虑优化.
发现 $A'$ 与 $E=(a,b)$ 交换等价于把 $a$ 映射到 $b$ , $b$ 映射到 $a$ , 并且这个映射是可以合并的. 于是的到这样一个算法: 从后向前扫 $E$ 序列, 边维护当前 $E$ 后缀对应的映射, 边计算出插在当前 $E$ 前面的 $A$ (详见代码). 这个部分的复杂度是 $\mathcal O(n)$ .
时间复杂度 $\mathcal O(n\log n)$ .
```cpp
#include <bits/stdc++.h>
using namespace std;
int read();
int n, flg, a[200005];
int m, x[200005], y[200005];
int b[200005];
bool vis[200005];
void get(int t) {
for (int i = 0; i < n; ++i) b[i] = a[i];
for (int i = 1; i <= t; ++i) swap(b[x[i]], b[y[i]]);
}
bool check(int x) {
get(x), memset(vis, 0, n);
int res = n;
for (int i = 0; i < n; ++i) {
if (!vis[i]) {
--res;
for (int j = i; !vis[j]; j = b[j]) vis[j] = 1;
}
}
return res <= x;
}
vector<int> res;
void solve(int x) {
get(x), memset(vis, 0, n);
for (int i = 0; i < n; ++i)
if (!vis[i] && b[i] != i)
for (int j = i; !vis[b[j]]; j = b[j]) vis[j] = 1, res.push_back(j);
while (res.size() < x) res.push_back(n);
}
int p[200005], fp[200005], rx[200005], ry[200005];
int main() {
n = read();
for (int i = 0; i < n; ++i)
a[i] = read(), flg |= (a[i] != (p[i] = fp[i] = i));
if (!flg) return puts("0"), 0;
m = min(read(), n - 1);
for (int i = 1; i <= m; ++i)
x[i] = read(), y[i] = read(), x[i] > y[i] ? swap(x[i], y[i]) : void();
int l = 1, r = m - 1, rs = r + 1, mid;
while (l <= r) check(mid = l + r >> 1) ? r = (rs = mid) - 1 : l = mid + 1;
printf("%d\n", rs), solve(rs);
for (int i = 0; i < rs; ++i) {
res[i] < n ? rx[i] = p[res[i]], ry[i] = p[b[res[i]]] : 0;
swap(p[fp[x[rs - i]]], p[fp[y[rs - i]]]);
swap(fp[x[rs - i]], fp[y[rs - i]]);
}
for (int i = 1; i <= rs; ++i) printf("%d %d\n", rx[rs - i], ry[rs - i]);
return 0;
}
int read() {
int x = 0, f = 1;
char c = getchar();
while (c < '0' || c > '9') f = (c == '-') ? -1 : f, c = getchar();
while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
return x * f;
}
```