分析

1. arr[i]>arr[j],且i<j
2. 就可以分为左边和右边，左边的元素比右边大
3. 如果左右两边是有序的，直接计数就行，不需要再比较。此时时间复杂度就是排序的时间复杂度
   例如 1 3 5 7 9 | 2 3 4 5 6 7
   5>2，则不要再比较后面的7 9 了
4. 递归：
5. 左边部分是逆序对，右边部分是逆序对
6. 划分为子问题，左右是逆序对
7. 为什么能用归并？
8. 归并排序是递归的，满足2；
9. 左边、右边部分是有序的，这样在确定左边满足的第一个逆序对时，直接算出逆序对数量
10. 注意题目数据范围，n<=100000,全为逆序时，逆序对数量为1e10个量级，故用long long

c++

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long LL;
const int N=100010;
int n;
int arr[N];

LL merge(int l,int r){
    if(l>=r) return 0;
    int mid=(l+r)/2;
    LL res=merge(l,mid)+merge(mid+1,r);
    //归并，若满足逆序对情况，进行统计
    int temp[r-l+1];
    int i=l,j=mid+1,idx=0;
    while(i<=mid && j<=r){
        if(arr[i]>arr[j]){
            res+=mid-i+1;
            temp[idx++]=arr[j++];
        }
        else temp[idx++]=arr[i++];
    }
    while(i<=mid) temp[idx++]=arr[i++];
    while(j<=r) temp[idx++]=arr[j++];
    for(int i=0,j=l;j<=r;i++,j++) arr[j]=temp[i];
    return res;
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",&arr[i]);
    LL res=merge(1,n);
    printf("%ld\n",res);
    return 0;
}

java

import java.util.*;
import java.io.*;
public class Main{
    static long res;
    public static void main(String[] args) throws Exception{
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        PrintWriter pw=new PrintWriter(new OutputStreamWriter(System.out));
        int n=Integer.parseInt(br.readLine());
        int[] arr=new int[n];
        String[] str=br.readLine().split(" ");
        for(int i=0;i<n;i++) arr[i]=Integer.parseInt(str[i]);
        res=0L;
        merge_sort(arr,0,n-1);
        pw.println(res);
        pw.flush();
    }
    public static void merge_sort(int[] arr,int l,int r){
        if(l>=r) return;
        int mid=(l+r)/2;
        merge_sort(arr,l,mid);
        merge_sort(arr,mid+1,r);
        int i=l,j=mid+1,k=0;
        int[] temp=new int[r-l+1];
        while(i<=mid && j<=r){
            if(arr[i]<=arr[j]) temp[k++]=arr[i++];
            else{
                temp[k++]=arr[j++];
                res+=mid-i+1;
            }
        }
        while(i<=mid) temp[k++]=arr[i++];
        while(j<=r) temp[k++]=arr[j++];
        k=0;
        for(int h=l;h<=r;) arr[h++]=temp[k++];
    }
}