自动搬运

查看原文

来自洛谷，原作者为

	Kinandra :D

搬运于2025-08-24 22:15:03，当前版本为作者最后更新于2020-05-12 15:06:15，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

标签: 构造

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

$E_1E_2E_3E_4\cdots A'_1A'_2A'_3A'_4\cdots$ 很容易构造, 我们只需要二分答案, 然后让 E 先把操作走完, 求一下此时使排列有序的操作次数( $n-\text{置换环个数}$ ) 并随便构造一下 $A'$ 序列即可.

考虑从 $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)$ .

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