原题链接：https://www.luogu.org/problem/show?pid=1966#sub
归并排序求逆序对。
本题定义两列火柴的距离等于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 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <algorithm> 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 == ' ' || c == ' '); 25 if (c == '-') 26 flag = true; 27 else 28 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 else 50 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 ",ans); 76 return 0; 77 }