涵涵有两盒火柴，每盒装有 nn 根火柴，每根火柴都有一个高度。

现在将每盒中的火柴各自排成一列，同一列火柴的高度互不相同，两列火柴之间的距离定义为：

∑i=1n(ai−bi)2∑i=1n(ai−bi)2

其中 aiai 表示第一列火柴中第 ii 个火柴的高度，bibi 表示第二列火柴中第 ii 个火柴的高度。 

每列火柴中相邻两根火柴的位置都可以交换，请你通过交换使得两列火柴之间的距离最小。

请问得到这个最小的距离，最少需要交换多少次？

如果这个数字太大，请输出这个最小交换次数对 99,999,99799,999,997 取模的结果。

输入格式

共三行，第一行包含一个整数 nn，表示每盒中火柴的数目。 

第二行有 nn 个整数，每两个整数之间用一个空格隔开，表示第一列火柴的高度。

第三行有 nn 个整数，每两个整数之间用一个空格隔开，表示第二列火柴的高度。

输出格式

输出共一行，包含一个整数，表示最少交换次数对 99,999,99799,999,997 取模的结果。

数据范围

1≤n≤1051≤n≤105,
0≤火柴高度≤231−10≤火柴高度≤231−1

输入样例：

4
2 3 1 4
3 2 1 4

输出样例：

1

 

#include <bits/stdc++.h> // 包含所有标准库头文件using namespace std; // 使用标准命名空间// 定义常量：数组的最大长度为1e5 + 10，模数为99999997
const int N = 1e5 + 10, MOD = 99999997;int n; // 数组的大小
int a[N], b[N], c[N], p[N]; // 定义四个数组，分别用于存储原始数据和中间结果// 函数work对数组进行排序，并通过辅助数组p完成a和b的第一步操作
void work(int a[]) {//  for(int i=0; i<n;i++)// {//     cout<<a[i]<<' ';// }// cout<<endl;// 初始化辅助数组p，存储每个元素的原始索引for (int i = 0; i < n; i++) p[i] = i;// 根据数组a的值对p中的索引进行排序sort(p, p + n, [&](int x, int y) {return a[x] < a[y]; // 按照a数组中对应位置的值从小到大排序});// for(int i=0; i<n;i++)// {//     cout<<p[i]<<' ';// }// cout<<endl;// 根据排序后的p重新调整a数组的值，使得a数组变为从0到n-1的排列for (int i = 0; i < n; i++) a[p[i]] = i;//  for(int i=0; i<n;i++)// {//     cout<<a[i]<<' ';// }// cout<<endl;
}// 归并排序函数，用于计算逆序对数量并对数组b进行排序
int merge_sort(int l, int r) {if (l >= r) return 0; // 如果区间长度小于等于1，直接返回0// 计算中间点mid，将区间[l, r]分为左右两部分int mid = l + r >> 1;// 递归地对左右两部分进行归并排序，并累加逆序对数量int res = (merge_sort(l, mid) + merge_sort(mid + 1, r)) % MOD;// 合并左右两部分时计算跨区间的逆序对数量int i = l, j = mid + 1, k = 0;while (i <= mid && j <= r) { // 当左右两部分都有未处理的元素时if (b[i] <= b[j]) { // 如果左边的元素小于等于右边的元素p[k++] = b[i++]; // 将左边的元素加入临时数组p} else { // 如果右边的元素小于左边的元素p[k++] = b[j++]; // 将右边的元素加入临时数组p// 计算以当前右边元素为结尾的逆序对数量res = (res + mid - i + 1) % MOD;}}// 处理剩余的左半部分while (i <= mid) p[k++] = b[i++];// 处理剩余的右半部分while (j <= r) p[k++] = b[j++];// 将临时数组p中的结果拷贝回数组bfor (int i = l, j = 0; i <= r; i++, j++) b[i] = p[j];return res; // 返回逆序对总数
}int main() {// 输入数组大小ncin >> n;// 输入数组afor (int i = 0; i < n; i++) cin >> a[i];// 输入数组bfor (int i = 0; i < n; i++) cin >> b[i];// 对数组a和b分别进行排序操作（调用work函数）work(a), work(b);// 通过a数组生成c数组，c[a[i]] = i 表示a数组中值为a[i]的元素在排序后的位置是ifor (int i = 0; i < n; i++) c[a[i]] = i;// 通过c数组更新b数组，b[i] = c[b[i]] 表示将b数组中的每个值映射为它在排序后的a数组中的相对位置for (int i = 0; i < n; i++) b[i] = c[b[i]];// 调用merge_sort函数计算b数组中的逆序对数量，并输出结果cout << merge_sort(0, n - 1) << endl;return 0; // 程序结束
}