排序算法题（有关逆序对）

首先，题目如下

我的想法是利用归并，分别将两个数组逆序对存到两个哈希集合中，然后再遍历其中一个求出相同逆序对个数，得到答案。但最终超时。求问是否有更好的思路，或者提供相关资料，感谢！

如果假定一个有序一个无序，是不是就相当于求逆序对个数O(nlogn)
实现这个假定的时间复杂度是O(n)

做成字典
key为当前元素
value为当前元素之后的元素用hash保存
比如
第一个人的是
2:{3,4,1,5}
3:{4,1,5}
4:{1,5}
1:{5}
第二个人是
4:{2,1,3,5}
2:{1,3,5}
1:{3,5}
3:{5}
遍历某一个人的key，比如第一个人
第一个key是2找到对应的value，然后在第二个人字典中找到key为2的value，两个value求一下交集就是{1,3,5}
3的话是{5}，4的话是{1,5}，1的话是{5}

你们真厉害，我连题目都没看懂

根据采纳回答所提供的思路，将个人写得代码分享出来，供大家借鉴，实测可行（未考虑int越界等情况）

public class Main {
    private static int[] arr1;
    private static int count;

    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        int length = input.nextInt();

        arr1 = new int[length + 1];
        int[] arr2 = new int[length];
        for (int i = 0; i < length; ++i) {
            arr1[input.nextInt()] = i;
        }
        for (int i = 0; i < length; ++i) {
            arr2[i] = input.nextInt();
        }

        MergeSort(arr2, 0, length - 1);

        int total = length * (length - 1) / 2;

        System.out.println(count);

    }

    public static void MergeSort(int[] arr, int left, int right) {
        if (left >= right) return;
        int center = (right - left) / 2 + left;
        MergeSort(arr, left, center);
        MergeSort(arr, center + 1, right);
        Merge(arr, left, center, right);
    }

    public static void Merge(int[] arr, int left, int center, int right) {
        if (left >= right) return;

        int[] temp = new int[right - left + 1];
        int i = left;
        int j = center + 1;
        int k = 0;

        while (i <= center && j <= right) {
            if (arr1[arr[i]] > arr1[arr[j]]) {
                temp[k++] = arr[j++];
                ++count;
            } else {
                if (i != center) count += j - center - 1;
                temp[k++] = arr[i++];
            }
        }

        int index = i;

        while (i <= center) {
            if (i != index) count += j - center - 1;
            temp[k++] = arr[i++];
        }
        while (j <= right) {
            temp[k++] = arr[j++];
        }

        for (int x = 0; x < temp.length; ++x) {
            arr[x + left] = temp[x];
        }

    }
}