原题链接：
归并排序求逆序对。
本题定义两列火柴的距离等于Sigma( (a[i]-b[i])^2 )，其实如果把这个式子按照完全平方公式展开，可以发现，其中的a[i]^2 和 b[i]^2相加的总和其实是一直保持不变的。
如果想要把距离弄成最小，那就应该在后面的-2a[i]*b[i]上下功夫。
自然可以想到，肯定是让对应的差值最小才能让距离最大。
那么如何保证每位的差值最小呢？
排一遍序即可，第1大对第1大，第2大对第2大……依次类推。可以证明，没有其他做法会比这个做法总差值更小。
那跟逆序对有什么关系啊？
实际上，我们定义一个a数组，让a[match_a[i].rank] = match_b[i].rank，得到这么一个a数组，最后的答案是a数组里的逆序对的个数。
有点人造痕迹明显，但这样做的确是对的。。
求出a数组的逆序对个数便是答案，可以使用正常向二路归并排序。
参考代码：
1 #include2 #include 3 #include 4 #include 5 #define maxn 100005 6 #define mo 99999997 7 using namespace std; 8 int n,ans; 9 int a[maxn];10 int b[maxn];11 struct matches{12 int num;13 int rank;14 bool operator<(const matches &rhs)const{15 return num < rhs.num;16 }17 };18 matches match_a[maxn];19 matches match_b[maxn];20 inline int read(){21 int num = 0;22 char c;23 bool flag = false;24 while ((c = getchar()) == ' ' || c == '\n' || c == '\r');25 if (c == '-')26 flag = true;27 else28 num = c - '0';29 while (isdigit(c = getchar()))30 num = num * 10 + c - '0';31 return (flag ? -1 : 1) * num;32 }33 34 void merge_sort(int l,int r){35 if (l >= r)36 return ;37 int mid = (l+r) >> 1;38 merge_sort(l,mid);39 merge_sort(mid+1,r);40 int i = l;41 int j = mid + 1;42 int k = l;43 while (i <= mid && j <=r){44 if (a[i] > a[j]){45 b[k++] = a[j++];46 ans += mid - i + 1;47 ans %= mo;48 }49 else50 b[k++] = a[i++];51 }52 while (i <= mid)53 b[k++] = a[i++];54 while (j <= r)55 b[k++] = a[j++];56 for (register int i=l;i<=r;i++)57 a[i] = b[i];58 }59 int main(){60 n = read();61 for (register int i=1;i<=n;i++){62 match_a[i].num = read();63 match_a[i].rank = i;64 }65 for (register int i=1;i<=n;i++){66 match_b[i].num = read();67 match_b[i].rank = i;68 }69 sort(match_a+1,match_a+n+1);70 sort(match_b+1,match_b+n+1);71 72 for (register int i=1;i<=n;i++)73 a[match_a[i].rank] = match_b[i].rank;74 merge_sort(1,n);75 printf("%d\n",ans);76 return 0;77 }