逆序对

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

逆序对解法

方法一：冒泡排序

对原序列进行冒泡排序，统计交换次数，得到的交换次数=逆序对数。
时间复杂度高，不推荐。

方法二：归并排序

题目链接

典型例题

讲解

归并讲解
递归这东西，难者不会会者不难，理解之后再写会好写点，但是小细节上还会有点小错。
这不是我主要想讲的内容，所以直接挂链接了。

AC代码

//#include<bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cstring>
#define ll long long
using namespace std;
const int N=5e5+10;
ll ans=0;
int a[N],b[N];
void merge_sort(int l,int r){
    int mid=(l+r)/2;
    int p=l,q=mid+1;//p，q分别是被分割成两段序列中左边序列的头指针和右边序列的头指针
    int lb=l;//lb表示b数组的头指针
    if(r-l>0){    
        merge_sort(l,mid);
        merge_sort(mid+1,r);
    }
    while(p<=mid || q<=r){
        if(q>r || (p<=mid && a[p]<a[q]))//这两种情况下左指针右移//大佬写的真简洁！ 
            b[lb++]=a[p++];
        else 
            b[lb++]=a[q++],ans+=mid-p+1;
    }
    for(int i=l;i<=r;i++)    
        a[i]=b[i];    

}
int main(){
    int n;
    while(cin>>n&&n){
        for(int i=1;i<=n;i++){
            cin>>a[i];
        }
        ans=0;
        merge_sort(1,n);
        cout<<ans<<endl;            
    }
}

方法三：离散化+树状数组

题目链接

典型例题 （同上）

讲解

看了好多树状数组求逆序对的博客，讲的是真的** ，所以决定写个博客。（如果我讲的也很** ，请喷我，改正！）
离散化实现：
构建一个结构体，id表示输入是默认的序号，v表示数值大小，pos表示离散化后的序号，也就是按照v的大小排完序后的序号（或索引，或位置）

struct node{
    int id,v,pos;
}a[N];

id和v的赋值可以在输入的时候实现

for(int i=1;i<=n;i++){
    cin>>a[i].v;
    a[i].id=i;//输入时的顺序对应的序号
}

再按照数值从小到大排序，对pos的进行赋值。
离散化的核心，数列中每个数的新值就是排完序的序号（或索引）

sort(a+1,a+n+1,cmp);
for(int i=1;i<=n;i++){
    a[i].pos=i;
}

“假的”求逆序对：
我们先不讲如何用树状数组实现，先通过一种方法来理解。
例如：
5 3 4 1 2
建立一个数组a[6]，向数组a中依次插入样例，
第一次插入5，那么就令a[5]=1，代表5插入数组a中了。
为了求逆序对，要计算有没有比5大的数已经插入数组a了，那么我们就要看看a[i],i>5的部分有没有1，有几个1就代表对5而言有多少个比5大的数在5之前，也就是关于5的逆序对；很显然，i>5的部分并没有1。
继续进行，第二次插入3，a[3]=1，还是一样，看看a[i],i>3的部分有没有1，发现a[5]=1，说明5在3之前插入了，因此，关于3的逆序对数为1。
第三次插入4，a[4]=1，a[i],i>4的部分中只有a[5]=1，所以关于4的逆序对数为1。
第四次插入1，a[1]=1，a[i],i>1的部分中a[3]=a[4]=a[5]=1，所以关于1的逆序对数为3。
第五次插入2，a[2]=1，a[i],i>2的部分中a[3]=a[4]=a[5]=1，所以关于2的逆序对数为3。
综上，累加一下，序列的逆序对数为8。
概括一下过程，无非就是：
顺序插入，每插入一个数，累加一下已经插入且比它大的数的个数，就是逆序对数。简单的一批吧！
“真的”求逆序对：
还是上面例子，经过离散化得到：
id: 1 2 3 4 5
v: 5 3 4 1 2
pos:5 3 4 1 2

sort(a+1,a+n+1,cmp1);
for(int i=1;i<=n;i++){
    update(a[i].pos,1);
    sum+=i-getsum(a[i].pos);
}

sort的目的是要让序列排回原来的默认顺序（刚刚咱不是为了对pos赋值，改变了默认顺序了嘛）
每插入一个数我们就让树状数组update一下，意义与“假的”求逆序对中a[插入数的序号]=1有点类似，只不过在树状数组中，改变一个点，就要把与其有关的点的值都改变（“有关”俩字自行理解，不理解说明不明白树状数组是什么，建议看看 树状数组讲解 ）
i-getsum(a[i].pos)：
getsum(a[i].pos)的目的是求前缀和，意义与“假的”求逆序对中求比当前插入数小且已经插入的数的个数。i表示已经插入的个数，那么 i-getsum(a[i].pos)表示的不就是已插入数中比当前插入数大的个数嘛。这样一来，我们每次都进行累加就ok了。
同时，我们还应当注意，getsum与update函数的参数均为pos。类比“假的”求逆序对中a数组体现某个数是否已经插入，是通过以某个数在序列中的排完序后的位置作为索引，赋值为1实现的；同样的，c树状数组体现某个数是否已经插入，也是要通过排完序后的位置作为索引，去更改和统计，而排完序后的位置不正是pos嘛！这就是我们为什么用pos作为参数的原因。

AC代码

//#include<bits/stdc++.h>//poj这个用不了
#include<iostream>
#include<algorithm>
#include<cstring>
#define ll long long
using namespace std;
const int N=5e5+10;
int n,c[N];
struct node{
    int id,v,pos;
}a[N];
bool cmp(node a,node b){
    return a.v<b.v;
}
bool cmp1(node a,node b){
    return a.id<b.id;
}
int lowbit(int x){
    return x&(-x);
}
void update(int x,int add){
    while(x<=n){
        c[x]+=add;
        x+=lowbit(x);
    }
}
ll getsum(int x){
    ll ans=0;
    while(x>0){
        ans+=c[x];
        x-=lowbit(x);
    }
    return ans;
}
int main(){

    while(cin>>n&&n){
        //init
        ll sum=0;//最大数据：5e5*5e5/2>2147483647=int，所以开ll
        memset(c,0,sizeof c);
        //输入，并对id，v赋值
        for(int i=1;i<=n;i++){
            cin>>a[i].v;
            a[i].id=i;
        }
        //离散化，本质是对pos赋值
        sort(a+1,a+n+1,cmp);
        for(int i=1;i<=n;i++){
            a[i].pos=i;
        }

        sort(a+1,a+n+1,cmp1);//恢复默认排序，为以此插入做准备
        for(int i=1;i<=n;i++){//依次插入，并统计
            update(a[i].pos,1);
            sum+=i-getsum(a[i].pos);
        }
        cout<<sum<<endl;
    }
}