逆序对是交换最少相邻元素交换次数

逆序数

 

在一个排列中，如果一对数的前后位置与大小顺序相反，即前面的数大于后面的数，那么它们就称为一个逆序。一个排列中逆序的总数就称为这个排列的逆序数。

 

如2 4 3 1中，2 1，4 3，4 1，3 1是逆序，逆序数是4。给出一个整数序列，求该序列的逆序数。

Input第1行：N，N为序列的长度（n <= 50000) 

第2 - N + 1行：序列中的元素（0 <= Aii <= 10^9）Output输出逆序数Sample Input

42431

Sample Output

4

---

归并排序

#include 
     
      #include 
      
       using namespace std;const int N=100005;int w[N],sum[N],n;struct T{    int x,num;} a[N],T[N];void la(int l,int r){    if(r-l==1)return;    int m=l+r>>1,tm=l+r>>1,tl=l,i=l;    la(l,m),la(m,r);    while(tl
       
        
         =r||(tl
         
          <=a[tm].x))            T[i++]=a[tl++],T[i-1].num+=tm-m;        else            T[i++]=a[tm++];    }    for(int i=l; i
         
        
       
      
     

sort+查找的

#include 
     
      #include 
      
       using namespace std;const int N=100005;int w[N],n;long long la(int l,int r){    if(r-l==1)return 0;    int m=l+r>>1,s=la(l,m)+la(m,r),t;    for(int i=l; i
      
     

树状数组

#include 
     
      #include 
      
       using namespace std;const int N = 500005;struct Node{    int val;    int pos;    friend bool operator <(Node a,Node b)    {        return a.val < b.val;    }};Node node[N];int c[N], hash[N], n;int lowbit(int x){    return x & (-x);}void update(int x){    while (x <= n)    {        c[x] += 1;        x += lowbit(x);    }}int getsum(int x){    int sum = 0;    while (x > 0)    {        sum += c[x];        x -= lowbit(x);    }    return sum;}int main(){    scanf("%d", &n);    for (int i = 1; i <= n; ++i)    {        scanf("%d", &node[i].val);        node[i].pos = i;    }    sort(node + 1, node + n + 1);    for (int i = 1; i <= n; ++i)         hash[node[i].pos] = i;    int  ans = 0;    for (int i = 1; i <= n; ++i)    {        update(hash[i]);        ans += i - getsum(hash[i]);    }    printf("%d\n", ans);    return 0;}