原题链接洛谷提高组-火柴排队
分析
这题我是用离散化，数组映射(数据处理办法)，归并排序优化逆序对 写的。
关于（ai-bi）的平方 求和可以理解为 a组火柴和b组火柴 相对位置相等时 这个和最小
竟然有相对位置了就逃不了离散化数组了
对于求相邻交换次数，是不是很像冒泡排序。这时候就要引入逆序对了。
可是这个逆序对的参照是1,2,3,4,5的升序来判断的，我们a转成b的相对位置可不是
1，2，3，4，5来排的所以我们把b数组映射成1,2,3,4,5，然后把a数组也按照相同的映射方法改写一下，再用逆序对写。（不用太在意重复的数据，因为仅大于才交换）
逆序对用常规的暴力方法 时间杂复度过大，所以这里我用了归并排序来优化
总结
1，数据离散化
2，数组映射
3，逆序对
代码
点击查看代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=100009;
struct data//结构体离散化
{
ll val;
ll id;
}olda[N],oldb[N];
ll newa[N],copyy[N],a[N],b[N];
//为了好理解数组开的有点多,写的时候可以省一些
bool cmp(struct data x,struct data y)
{
return x.val<y.val;
}
ll cnt=0,cup[N];
void merge(ll left,ll right)
{
if(left>=right)
{
return;
}
ll mid=(left+right)/2;
merge(left,mid);
merge(mid+1,right);
ll i=left,j=mid+1,k=left;
while(i<=mid && j<=right)
{
if(newa[i]<=newa[j])
{
cup[k++]=newa[i++];
}else
{
cup[k++]=newa[j++];
cnt+=mid-i+1;//与归并排序相比就加了这两条
cnt=cnt%99999997;
}
}
while(i<=mid)
{
cup[k++]=newa[i++];
}
while(j<=right)
{
cup[k++]=newa[j++];
}
for (int v=left;v<=right;v++)
{
newa[v]=cup[v];
}
}
int main()
{
int n;
scanf("%lld",&n);
for(int i=1;i<=n;i++)
{
scanf("%lld",&olda[i].val);
olda[i].id=i;
}
for(int i=1;i<=n;i++)
{
scanf("%lld",&oldb[i].val);
oldb[i].id=i;
}
sort(olda+1,olda+1+n,cmp);
sort(oldb+1,oldb+1+n,cmp);
for(ll i=1;i<=n;i++)
{
a[olda[i].id]=i;
//不用特判相同时id相等，后面逆序对的处理方向可以避免相等时相交换
//直接先出现的小
}
for(ll i=1;i<=n;i++)
{
b[oldb[i].id]=i;
}
//假设以b为参照物
//求逆序对时暴力会超时所以可以进行优化，我用归并优化
//将第2盒火柴映射为升序，相当于把第二盒当成id为1，2，3，4，5然后把第一盒按id去改
for(ll i = 1; i <= n; i ++) copyy[b[i]] = i;//copyy作为按b转化的表,想出这个方法的人真是天才！！
//将第1盒火柴当对应的元素进行映射为第一种表示
for(ll i = 1; i <= n; i ++) newa[i] = copyy[a[i]];
merge(1,n);
printf("%lld\n",cnt%99999997);
return 0;
}