#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 10, MOD = 1e8 - 3;

int n, a[MAXN], b[MAXN], t[MAXN], c[MAXN], d[MAXN];
map<int, int>ma, mb;
long long ans;

void merge_sort(int l, int r){
	if(l == r){
		return;
	}
	int mid = (l + r) / 2;
	merge_sort(l, mid);
	merge_sort(mid + 1, r);
	int j = l, k = mid + 1, now = l;
	while((j <= mid || k <= r) && now <= r){
		if(j <= mid && (k > r || ma[a[j]] < ma[a[k]])){
			t[now] = a[j];
			j++;
		}
		else{
			ans += mid - j + 1;
			t[now] = a[k];
			k++;
		}
		now++;
	}
	for(int i = l; i <= r; i++){
		a[i] = t[i];
	}
}

int main(){
	cin >> n;		
	for(int i = 1; i <= n; i++){
		cin >> a[i];
		c[i] = a[i];
	}				
	for(int i = 1; i <= n; i++){
		cin >> b[i];
		mb[b[i]] = i;
		d[i] = b[i];
	}
	sort(c + 1, c + n + 1);
	sort(d + 1, d + n + 1);
	for(int i = 1; i <= n; i++){
		ma[c[i]] = mb[d[i]];
	}
	merge_sort(1, n);
	cout << ans % MOD;	
	return 0;
}

这是我的代码 排序我也知道 按第k大映射我也知道 但是我看题解的目的是为了知道为什么求一个无序序列交换到有序序列的次数是逆序对个数 求dalao求解

# 懂闭关