两日一题,这题我写了两天,关键是搞清楚离散化,看不懂离散化很苦恼,推荐去洛谷看第一个题解。
其实就是把a按照1234…排序,(这里我是0123…,是一样的)。a和b都按此排序所以排好序后a,b相对位置不变,因为每行火柴的长度是唯一的,不用担心重复,直接按照1234…表示就行了,这就是我代码中的ai和bi数组,此时ai和bi就记录的是a和b中的大小关系了。(比如ai的第一个元素是3,那第一个元素就是a数组中第三小的)可我们为什么要这样做呢,这就是为什么要建立c数组的原因,我们建立c数组按照c[ai] = bi填充c,ai其实就是a的大小的映射,填充完c数组就会发现此时c的下标就是ai,ai已经排好序了,而数组的每个下标对应的元素就是它对应的bi。(如果我们直接将a,b排序然后让c来映射a,b的数据量一大,一方面时间复杂度上升,另一方面c可能会炸掉)
最后,ai数组都排好序了,我们用归并排序求bi数组的逆序对就是最后的答案。
import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;
public class Main {
static long ans;
static int mod = (int) (1e8 - 3);
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[] a = new int[n], b = new int[n];
for (int i = 0; i < n; i++)
a[i] = sc.nextInt();
for (int i = 0; i < n; i++)
b[i] = sc.nextInt();
Integer[] ai = new Integer[n], bi = new Integer[n];
//前面均为初始化步骤
//将ai,bi初始化为1234...的序列(我这里是0123...下面也按照1234来讲)
work(ai);
work(bi);
//按照1234...排序
Arrays.sort(ai, (o1, o2) -> Integer.compare(a[o1], a[o2]));
Arrays.sort(bi, (o1, o2) -> Integer.compare(b[o1], b[o2]));
//排好序后ai,bi可能是 1 3 4 2也可能是 4 3 1 2...但是不重要最终我们都会映射到c上
Integer[] c = new Integer[n];
//映射到c上
for (int i = 0; i < n; i++) c[ai[i]] = bi[i];
//对c求逆序对
msort(0,n-1,c);
System.out.println(ans);
}
static void work(Integer[] arr) {
for (int i = 0; i < arr.length; i++)
arr[i] = i;
}
static void msort(int l, int r, Integer[] a) {
if(l==r) return;
int mid = l + ((r - l) >> 1);
msort(l, mid,a);
msort(mid + 1, r,a);
int i = l, j = mid+1, k = 0;
int[] b = new int[r-l+1];
while (i <= mid && j <= r) {
if(a[i]>a[j]) {
ans = (ans + mid - i + 1)%mod;
b[k++] = a[j++];
}else {
b[k++] = a[i++];
}
}
while(i<=mid)b[k++] = a[i++];
while(j<=r)b[k++] = a[j++];
for(int m = l,n = 0;l<=r&&n<b.length;m++,n++) a[m] = b[n];
}
}