题目描述
blablabla
样例
blablabla
算法
离散化+归并排序
时间复杂度
$O(nlogn)$
参考文献
java 代码
import java.util.Scanner;
import java.util.*;
// 1:无需package
// 2: 类名必须Main, 不可修改
public class Main {
static int MOD=99999997;
static int N=100010;
static int[] a=new int[N];
static int[] b=new int[N];
static int[] c=new int[N];
static int[] p=new int[N];
static int n;
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
n=scan.nextInt();
for(int i=1;i<=n;i++)a[i]=scan.nextInt();
for(int i=1;i<=n;i++)b[i]=scan.nextInt();
work(a);
work(b);
for(int i=1;i<=n;i++)c[a[i]]=i;//离散化后对a数组进行映射
for(int i=1;i<=n;i++)b[i]=c[b[i]];//数字x的映射在c[x]当中
System.out.print(mergeSort(1,n));
scan.close();
}
public static int mergeSort(int l,int r){//归并排序
if(l>=r)return 0;
int mid=l+r>>1;
int res=(mergeSort(l,mid)+mergeSort(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++];
else {
p[k++]=b[j++];
res=(res+mid-i+1)%MOD;//统计逆序对数量
}
}
while(i<=mid)p[k++]=b[i++];
while(j<=r)p[k++]=b[j++];
for( i=l,j=0;j<k;i++,j++){
b[i]=p[j];
}
return res;
}
public static int find(int x){
int l=1,r=n;
while(l<r){
int mid=l+r>>1;
if(p[mid]>=x)r=mid;
else l=mid+1;
}
return r;
}
public static void work(int[] a){//离散化
for(int i=1;i<=n;i++)p[i]=a[i];
Arrays.sort(p,1,n+1);
for(int i=1;i<=n;i++)a[i]=find(a[i]);
}
}