Bubble XOR Sort#12413

Bubble XOR Sort (Editorial)

Problem Author:	turneja
Prepared by:	turneja
Edited by:	turneja

Solution

Let us first discuss on how to solve an easier problem: given a permutation $p$ find the minimum cost to sort it using the given operation.

Let the number of inversions in the permutation be $\sum_{i < j} [p_{i} > p_{j}]$ \sum_{i<j} \left[p_i > p_j\right]. From the fact that the sorted permutation has $0$ inversions and that we can fix at most one inversion in one operation, it is clear that the answer is $\sum_{i < j, p_{i} > p_{j}} (p_{i} \oplus p_{j})$ \sum_{i<j,\; p_i > p_j} \left(p_i \oplus p_j\right).

This can be calculated by one of the standard inversion counting approaches such as using divide and conquer or Fenwick tree, but on each bit separately.

To extend this to the actual problem, notice that the answer becomes the sum of $(a_{i} \oplus a_{j})$ (a_i \oplus a_j) over all pairs of elements whose relative order is different between $a$ and $b$ . To solve the problem of duplicates, simply match the first occurrence of any element in $a$ to the first occurrence in $b$ , and so on. With this, we can produce a permutation $p$ and calculate the answer as $\sum_{i < j, p_{i} > p_{j}} (a_{i} \oplus a_{j})$ \sum_{i<j,\; p_i > p_j} \left(a_i \oplus a_j\right).

The time complexity is $O (n lo g^{2} n)$ \mathcal{O}(n \log^2 n).

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;

#define endl "\n"
#define ll long long
#define IOS ios_base::sync_with_stdio(false); cin.tie(nullptr);

const int N = 2e5 + 5;

int a[N], b[N];
pair<int, int> ord[N];
vector<int> pos[N];
int ptr[N];

ll ans = 0;

vector<pair<int, int>> calc(int l, int r) {
    if (l == r) {
        return {ord[l]};
    }
    int mid = (l + r) / 2;
    vector<pair<int, int>> L = calc(l, mid), R = calc(mid + 1, r), cur;
    vector<vector<int>> ct(20, vector<int>(2, 0));
    int i = 0, j = 0;
    while (i < L.size() && j < R.size()) {
        if (L[i].first < R[j].first) {
            cur.push_back(L[i]);
            for (int k = 0; k < 20; k++) {
                int c = L[i].second & (1 << k);
                c = min(c, 1);
                ans += (ll)(1 << k) * ct[k][c ^ 1];
            }
            i++;
        } else {
            cur.push_back(R[j]);
            for (int k = 0; k < 20; k++) {
                int c = R[j].second & (1 << k);
                c = min(c, 1);
                ct[k][c]++;
            }
            j++;
        }
    }
    while (i < L.size()) {
        cur.push_back(L[i]);
        for (int k = 0; k < 20; k++) {
            int c = L[i].second & (1 << k);
            c = min(c, 1);
            ans += (ll)(1 << k) * ct[k][c ^ 1];
        }
        i++;
    }
    while (j < R.size()) {
        cur.push_back(R[j]);
        for (int k = 0; k < 20; k++) {
            int c = R[j].second & (1 << k);
            c = min(c, 1);
            ct[k][c]++;
        }
        j++;
    }
    return cur;
}

int main() {
    IOS;
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        for (int i = 0; i < n; i++) {
            cin >> a[i];
        }
        for (int i = 0; i < n; i++) {
            cin >> b[i];
            pos[b[i]].push_back(i);
        }
        for (int i = 0; i < n; i++) {
            ord[i] = {pos[a[i]][ptr[a[i]]++], a[i]};
        }
        calc(0, n - 1);
        cout << ans << endl;
        ans = 0;
        for (int i = 0; i <= n; i++) {
            pos[i].clear();
            ptr[i] = 0;
        }
    }

    return 0;
}

C++