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…n。则 dis(A,B) 等于 B 的逆序对数,设为 s。
现在我们要构造一个 C 使得 B 中一半的逆序对变成正序对。设 p 为最早满足 [1,p] 中逆序对数大于 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;
}