首先可以证明，当 $A$ 数组和 $B$ 数组均为升序排列时，$\sum\limits_{i=1}^n (a_i-b_i)^2$ 最小。

（upd：现在学到了，这个结论的原理是排序不等式）

但在这道题中，我们只需要让在升序排列中，两数组中下标相同的数对应即可。

以样例中 $A,B$ 数组为例，将它们分别离散后列出：

$A: 2 \ \ 3 \ \ 1 \ \ 4$

$B: 3 \ \ 2 \ \ 1 \ \ 4$

根据上述结论，当 $A_i = x$ 时，$B_i$ 也应该等于 $x$。

也就是说，如果建立一个数组 $C$，令 $C_{A_i}=B_i$ 的话，应该满足 $C_i=i$。

但在样例中，可以列出 $C$ 数组：

$C: 1 \ \ 3 \ \ 2 \ \ 4$

我们的目标是让 $C$ 数组升序排列，而每次交换最多消除一个逆序对。

故题目的答案就是 $C$ 数组的逆序对数。

求逆序对可以用树状数组或归并排序，代码中使用的是归并排序。

时间复杂度 $O(N\log N)$

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 1e5 + 5;
struct node {
	int x,id;
	node() {
		x = id = 0;
	}
	node(int x,int id):x(x),id(id){}
	bool operator < (const node& p)const {
		return x < p.x;
	}
}a[maxn],b[maxn];
int n,c[maxn],d[maxn];
typedef long long ll;
const ll mod = 1e8 - 3;
ll ans = 0;
void MergeSort(int l,int r) {
	if(l >= r)return ;
	int mid = l + r >> 1;
	MergeSort(l , mid);
	MergeSort(mid + 1 , r);
	for(int k = l,i = l,j = mid + 1;k <= r;++ k) {
		if(j > r||(i <= mid&&d[i] < d[j])) {
			c[k] = d[i ++];
		}
		else c[k] = d[j ++],(ans += mid - i + 1) %= mod;
	}
	for(int k = l;k <= r;++ k)d[k] = c[k];
	return ;
}
int main() {
	scanf("%d",&n);
	for(int i = 1;i <= n;++ i)scanf("%d",&a[i].x),a[i].id = i;
	for(int i = 1;i <= n;++ i)scanf("%d",&b[i].x),b[i].id = i;
	sort(a + 1 , a + 1 + n);
	sort(b + 1 , b + 1 + n);
	for(int i = 1;i <= n;++ i)d[a[i].id] = b[i].id;
	MergeSort(1 , n);
	printf("%lld",ans);
	return 0;
}