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