滿驚訝竟然沒人分享 Merge Sort 法
使用 Merge Sort 的好處是陣列值不一定要在 $[1,n]$ 之間。

這題可以化約成 find inversion counts of an array
先對每個位置找到「在它之後有多少元素比它小」，然後將相同值的部分相減

以範例測資為例（其中 ans 記錄每個位置後比他小的元素數量）：
a     = [3, 1, 2, 1, 3, 2]
ans  = [4, 0, 1, 0, 1, 0]

則最後答案為 (0-0) + (1-0) + (4-1) = 4
0-0 為 兩個 1 中間的答案，1-0 為兩個 2 之間，4-1 為兩個 3 之間。

code:

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define MOD 1000000007
#define MOD2 998244353

vector<int> tmp;
vector<int> ans;

void merge(vector<int>& a, vector<int>& pos, int start, int mid, int end) {
    int p1 = start, p2 = mid+1;
    int offset = start;
    while (p1 <= mid && p2 <= end) {
        if (a[pos[p1]] <= a[pos[p2]]) {
            ans[pos[p1]] += p2 - (mid+1);
            tmp[offset++] = pos[p1++];
        } else {
            tmp[offset++] = pos[p2++];
        }
    }
    while (p1 <= mid) {
        ans[pos[p1]] += p2 - (mid+1);
        tmp[offset++] = pos[p1++];
    }
    while (p2 <= end) {
        tmp[offset++] = pos[p2++];
    }
    for (int i = start; i <= end; i++) {
        pos[i] = tmp[i];
    }
}

void mergeSort(vector<int>& a, vector<int>& pos, int start, int end) {
    if (start == end) {
        return;
    }

    int mid = start + (end - start) / 2;
    mergeSort(a, pos, start, mid);
    mergeSort(a, pos, mid+1, end);
    merge(a, pos, start, mid, end);
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    // merge sort
    int n; cin >> n;
    tmp.resize(2 * n);
    ans.resize(2 * n);

    vector<int> a(2 * n);
    vector<int> pos(2 * n);
    for (int i = 0; i < 2*n; i++) {
        cin >> a[i];
        pos[i] = i;
    }

    mergeSort(a, pos, 0, 2*n-1);

    ll finalAns = 0;
    unordered_set<int> occ;
    for (int i = 0; i < 2*n; i++) {
        if (occ.count(a[i])) {
            finalAns -= ans[i];
        } else {
            finalAns += ans[i];
            occ.insert(a[i]);
        }
    }
    cout << finalAns << '\n';


    return 0;
}