【注】a[ ]、b[ ]中元素可以不一样,这里只是举个例子,反正离散化后里面元素都一样,毕竟a[ ],b[ ]数组大小一样而且存的都是它们数组值的大小位序
输入 a[ ] = {5,8,10,2,7} b[ ] = {7,5,10,8,2}
离散化后 a[ ] = {2,4, 5,1,3} b[ ] = {3,2,5, 4,1}
可以这么理解
离散化之后,给输入的a[ ]中的元素{5,8,10,2,7}分别起了个“外号”:{2,4,5,1,3}
在b[ ]的元素{7,5,10,8,2}中起了同样的“外号”:{3,2,5, 4,1}
给a[ ]排序,直接给“外号”排序,就是给外号在换个别名{2,4,5,1,3} —> {1,2,3,4,5}
原来的外号“2”别名叫“1”,外号“4”别名叫“2”....
那么为了保持逻辑等价,b[ ]的“外号”也要用同样的别名调整次序 {3,2,5, 4,1} —> {5,1,3,2,4}
【补充】代码里面并没有记录a[ ]外号的别名,而是用c[ ]记录了“外号”与“别名”的关系。因为最终需要的是b[ ]的“别名
#include<bits/stdc++.h>
using namespace std;
const int N = 100010, MOD = 99999997;
int n;
int a[N],b[N],c[N],q[N];
/*
离散化是将原数组中每个数换成它在数组中的大小位序
离散化,调试时候,a[]中数字连续了,感觉不出来
举a[] = {5,8,10,2,7} b[] = {7,5,10,8,2}试试
*/
void work(int a[])
{
for(int i=1;i<=n;i++) q[i] = a[i];
sort(q+1,q+1+n);
for(int i=1;i<=n;i++)
a[i] = lower_bound(q+1,q+1+n,a[i]) - q;
}
int merge_sort(int l,int r)
{
if(l>=r) return 0;
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]) q[k++] = b[i++];
else q[k++] = b[j++], res = (res + mid - i + 1) % MOD;
while (i <= mid) q[k ++ ] = b[i ++ ];
while (j <= r) q[k ++ ] = b[j ++ ];
for (i = l, j = 0; i <= r; i ++, j ++ ) b[i] = q[j];
return res;
}
int main()
{
scanf("%d", &n);
for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
for (int i = 1; i <= n; i++) scanf("%d", &b[i]);
work(a), work(b); // 离散化
for (int i = 1; i <= n; i++) c[a[i]] = i;
for (int i = 1; i <= n; i++) b[i] = c[b[i]];
cout<<merge_sort(1,n);
return 0;
}