首先介绍一下逆序数。对于一个序列，它的逆序数就是指这个序列的其中两个数前后位置和大小顺序相反。例如序列14532,其中5、 3是一对逆序数，5、 2也是一对逆序数。等等
解法
1. n^2复杂度的暴力
直接暴力枚举即可
int s[inf],sum=0;for(int i=0;i<n;i++)for(int j=i+1;j<n;j++)if(s[i]>s[j])sum++;
2. 树状数组( nlog(n) )
树状数组是先确定每个值在所有序有序情况下的序列中所在的位置（离散化）。
列如序列：5 1 4 3 。
离散化后的值为：4 1 3 2。
从最左端开始建立树状数组，每创建一个就执行一次 i - query( x ) (x 为离散化的 值) 类加到ans上。最后的 ans即为所求的答案。
离散化的实质就是把所有的数都变成从1到n-1的连续的数。
思想实质：其实就是没针对当下一个序列最后的位置n，维护一个树状数组，这个数组记录值值的个数，然后求出这个序列最后一个数的前面有几个数和这个数组成逆序数，然后一次递推。由于可能每个数出现的次数可能不止一次，或者不连续，此时用离散化预处一下。( 初学者可以从连续的无重复的序列理清一下思路 )
#include <iostream>#include <algorithm>using namespace std;const int inf = 1e5;struct node{int val,i;bool operator<(node x)const {return val<x.val;}}sn[inf];int tree[inf],b[inf],n;void add(int i,int x){while(i<=n){tree[i]+=x;i+=i&-i;}}int query(int i){int sum=0;while(i>=1){sum+=tree[i];i-=i&-i;}return sum;}int main(){cin>>n;for(int i=1;i<=n;i++){cin>>sn[i].val;sn[i].i=i;}sort(sn+1,sn+n+1);int cnt=1;for(int i=1;i<=n;i++){if(i>1&&sn[i].val>sn[i-1].val)cnt++;b[sn[i].i]=cnt;}int ans=0;for(int i=1;i<=n;i++){add(b[i],1);ans+=i-query(b[i]);}cout<<ans<<endl;return 0;}
3. 归并排序法( nlog(n) )
这种方法是利用了归并排序的过程，在排序中进行计数。
#include<iostream>#define endl 'n'using namespace std;const int inf = 1e5;int sn[inf],sum;int temp[inf];void Merge_sqrt(int l,int m,int r){int h=l,g=m+1,f=l;while(h<=m&&g<=r){if(sn[h]<=sn[g]){temp[f++]=sn[h++];}else{temp[f++]=sn[g++];sum+=m+1-h;}}while(h<=m){temp[f++]=sn[h++];}while(g<=r)temp[f++]=sn[g++];for(int i=l;i<=r;i++)sn[i]=temp[i];}void Merge(int l,int r){if(l<r){int mid=(l+r)>>1;Merge(l,mid);Merge(mid+1,r);//cout<<l<<" "<<mid<<" "<<r<<endl;Merge_sqrt(l,mid,r);//cout<<sum<<endl;}}int main(){int n;cin>>n;for(int i=0;i<n;i++)cin>>sn[i];Merge(0,n-1);cout<<sum<<endl;return 0;}
欢迎大家的观看哈O(∩_∩)O哈哈~，如果有喜欢的可以关注一下_