ARC043C 転倒距離

定义两个排列 $A, B$ 的距离为满足 $(i, j)$ 在 $A, B$ 中顺序相反的无序对数。现在给定排列 $A$ 和 $B$，构造一个排列 $C$ 使得 $dis(A, C) = dis(B, C)$。

若 $(i, j)$ 在 $A,B$ 中的相对位置相同，则对 $dis(A, C)$ 和 $dis(B, C)$ 有相同的贡献。若不同，则对其中一个有 $1$ 的贡献。容易发现有解当且仅当 $dis(A, B)$ 为偶数。将 $A$ 映射为 $1, 2\dots n$。则 $dis(A, B)$ 等于 $B$ 的逆序对数，设为 $s$。

现在我们要构造一个 $C$ 使得 $B$ 中一半的逆序对变成正序对。设 $p$ 为最早满足 $[1, p]$ 中逆序对数大于 $\frac s2$ 的位置。将 $1$ 到 $p – 1$ 排序，再将 $p$ 插入到中间即可。

看代码应该好懂一些吧。

#include <bits/stdc++.h>

const int N = 1e5 + 10;


template<typename T = int> inline T read()
{
    T x = 0, f = 0; char ch = getchar();
    while (!isdigit(ch)) f |= ch == '-', ch = getchar();
    while ( isdigit(ch)) x = x * 10 + ch - '0', ch = getchar();
    return f ? -x : x;
}

struct BIT
{
    int f[N];
    #define lowbit(x) (x & -x)

    inline void Add(int x, int dat = 1)
    {
        for (; x < N; x += lowbit(x)) f[x] += dat;
    }

    inline int Ask(int x)
    {
        int res = 0;
        for (; x; x -= lowbit(x)) res += f[x];
        return res;
    }
}T;

int a[N], A[N], b[N], s[N];

int main()
{
    int n = read(), p = 0; int64_t sum = 0;
    for (int i = 1; i <= n; ++i) a[A[i] = read()] = i;
    for (int i = 1; i <= n; ++i) b[i] = a[read()];
    for (int i = 1; i <= n; ++i) s[i] = T.Ask(N - 1) - T.Ask(b[i]), T.Add(b[i]);
    for (int i = 1; i <= n; ++i) sum += s[i];
    if (sum & 1) return puts("-1"), 0; sum >>= 1;
    for (int i = 1; i <= n; ++i)
    {
        if (sum < s[i]) {p = i; break;}
        sum -= s[i];
    }
    std::sort(b + 1, b + p);
    for (int i = 1; i <= sum; ++i) std::swap(b[p], b[p - 1]), --p;
    for (int i = 1; i <= n; ++i) printf("%d ", A[b[i]]); puts("");
    return 0;
}