什么是逆序对

设 $A$ 为一个有$ n $个数字的有序集$ (n>1)$，其中所有数字各不相同。
如果存在正整数$ i, j$ 使得 $1 ≤ i < j ≤ n$ 而且 $A[i] > A[j]$，则 $<A[i], A[j]>$ 这个有序对称为 $A $的一个逆序对，也称作逆序数。by百度百科

怎么求逆序对

1.暴力求解

最原始的方法，利用两重循环进行枚举。该算法的时间复杂度为$O(n^2)$。

int doit(int *a, int N)
{
    int count = 0;
    int i, j;
    for(i=0; i<N-1; i++)
        for(j=i+1; j<N; j++)
            if(a[i]>a[j])
            count++;
    return count;
}

p党福利

var
  i,j,k,n:longint;
  a:array[1..1000000] of longint;
begin
  readln(n);
  for i:=1 to n do read(a[i]);
  k:=0;
  for i:=1 to n-1 do
  for j:=i+1 to n do
  if a[i]>a[j] then inc(k);
  writeln(k);
end.

2.归并排序

树状数组

如果不会树状数组,请先去学习一下

未完待续

逆序对

原文：https://www.cnblogs.com/pyyyyyy/p/11112289.html