排序题目的巅峰。

首先，由于距离是两数之差的平方，有一个显然的贪心：把两个数组从小到大排序，同一位置的数互相对应，此时距离最小。交换两数后，由于平方的影响，绝对值之差会较大，导致距离也较大，证明了贪心的正确性。

然后，将 $a$ 数组的每个数与 $b$ 数组建立映射关系，同时进行离散化。可以记录下数组 $a$ 中每个数字排序前的位置，再以排序后其对应的 $b$ 数组的元素的位置作为关键字进行离散化。这样相当于数组中记录的是在不改变 $b$ 数组的情况下，每个数组元素在距离最小情况下的排名。

由于数组记录的是排名，那么最小情况必然是一个单升不降的序列。此时的序列是一个乱序序列，要求最小化将这个序列排好序的相邻两数交换次数。这点就很像例题 $8$ ，实质就是求一个数组的逆序对数，树状数组求解即可，推导过程可以看 零碎知识点整理 杂项部分 $3.2$ 的证明部分。

由于每次交换，逆序对数量要么 $+1$ ，要么 $-1$ ，两个序列地位相同，可以只变换一个序列，最终最优解不受影响，再次保证了算法的正确性。

#include <bits/stdc++.h>
const int MOD=100000000-3;
using namespace std;
struct node
{
	int x,v;
}a[200000],b[200000];
long long n,m=1,ans,c[200000],d[200000]; 
bool cmp(struct node a,struct node b)
{
	return a.v<b.v;
}

long long lowbit(long long x)
{
	return (x&(-x));
}

void add(long long x,long long k)
{
	while(x<=m)c[x]+=k,x+=lowbit(x);
}

long long getsum(long long x)
{
	long long ans=0;
	while(x>0)ans+=c[x],x-=lowbit(x);
	return ans;
}

int main()
{
	scanf("%lld",&n);
	for(int i=1;i<=n;i++)
	    {
	    scanf("%lld",&a[i].v);
	    a[i].x=i;
	    }
	for(int i=1;i<=n;i++)
	    {
	    scanf("%lld",&b[i].v);
	    b[i].x=i;
	    }
	sort(a+1,a+n+1,cmp);
	sort(b+1,b+n+1,cmp);
	for(int i=1;i<=n;i++)
	    {
	    if(i!=1&&a[i].v!=a[i-1].v)m++;
	    d[a[i].x]=b[i].x;
	    }
	for(int i=1;i<=n;i++)
	    {
	    	add(d[i],1);
	    	ans+=((getsum(m)%MOD-getsum(d[i])%MOD)+MOD)%MOD;
	    	ans%=MOD;
		}
	printf("%lld\n",ans%MOD);
	return 0;
}