arc 043 c
若我们另外弄两个数组\(a'\)和\(b'\),其中\(a'[i]\)表示i在\(a\)中的位置,\(b'[i]\)表示i在b中的位置。
则転倒距離就是有多少对\((i,j)\)满足\((i<j)\)且\(a'[i],a'[j]\)和\(b'[i]\)和\(b'[j]\)的大小关系不一样。这样就可以发现有解的充要条件就是\(A,B\)的転倒距離是偶数。
首先求転倒距離的方法比较简单就是在A里从前往后扫一遍,在B里标记位置。用bit就可以了。
构造方法,我们在B中从前往后扫。若前面存在一些数在A中应该出现在当前数后面的数。若将这个移到前面去仍然小于等于应该交换的次数,就直接移动到这些数的前面。否则就移到一部分数的前面。
这样,我们只需要对于一个数组,执行一系列操作: 将一个数向前移动x位。
我们可以对于第i个数记录一个rank[i]表示第i个数在前i个的排名,从后往前还原即可。
sugim48
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> i_i;
typedef pair<ll, int> ll_i;
typedef pair<double, int> d_i;
typedef pair<ll, ll> ll_ll;
typedef pair<double, double> d_d;
struct edge { int u, v; ll w; };
ll MOD = 1000000007;
ll _MOD = 1000000009;
double EPS = 1e-10;
struct bit {
vector<ll> v;
bit(int n) : v(n + 1) {}
ll sum(int i) {
ll res = 0;
for (; i > 0; i -= i & -i) res += v[i];
return res;
}
void add(int i, ll x) {
for (i++; i < v.size(); i += i & -i) v[i] += x;
}
};
int main() {
int N; cin >> N;
vector<int> A(N);
for (int i = 0; i < N; i++) {
cin >> A[i];
A[i]--;
}
vector<int> B(N);
for (int i = 0; i < N; i++) {
cin >> B[i];
B[i]--;
}
vector<int> a(N);
for (int i = 0; i < N; i++)
a[A[i]] = i;
for (int i = 0; i < N; i++)
B[i] = a[B[i]];
vector<int> hoge(N);
for (int i = 0; i < N; i++)
hoge[B[i]] = i;
ll inv = 0;
bit b(N);
vector<int> unko(N);
for (int i = 0; i < N; i++) {
inv += i - b.sum(hoge[i]);
unko[i] = i - b.sum(hoge[i]);
b.add(hoge[i], 1);
}
if (inv % 2 == 1) {
cout << -1 << endl;
return 0;
}
inv /= 2;
vector<int> ans(N);
bit c(N);
for (int i = N - 1; i >= 0; i--) {
int k = min(inv, (ll)unko[i]);
inv -= k;
int t = i - unko[i] + k;
int lb = 0, ub = N;
while (ub - lb > 1) {
int mid = (lb + ub) / 2;
int x = mid - c.sum(mid);
if (x <= t) lb = mid;
else ub = mid;
}
c.add(lb, 1);
ans[lb] = i;
}
for (int i = 0; i < N; i++)
B[i] = A[ans[i]];
for (int i = 0; i < N; i++)
cout << B[i] + 1 << (i + 1 < N ? ' ' : '\n');
}