首页 > 代码库 > 逆序对
逆序对
什么是逆序对？？
我们在这里给出一个定义：如果i<j&&a[i]>a[j]的一对数称为逆序对。
为什么？？！！
背过！！（都说了是定义了！）（其实我也不知道为什么 orz (*^__^*) ……）
但是知道逆序对有什么用处呢？
- 具体用处我也不是很清楚，但是目前我们可以用逆序对的个数求将一列数排成有序的一列数交换的次数
怎样求逆序对呢？？
我们在这里给出两种算法：归并排序求逆序对；树状数组求逆序对。
§归并排序求逆序对
归并排序的核心思想是二分。
我们将一个序列a1,a2,a3,a4,a5,a6.........an;进行归并排序
对于归并排序还有童鞋不明白吗？
我们在这里就简单提一下归并排序吧。
说起排序来了，有人肯定又要说，要归并排序干嘛？sort不就挺好的吗？又快有省时。所以有些人就不重视归并排序。但是试问，你的sort可以求逆序对吗？
显然是不能的！所以我们还是要好好学归并排序的（算了，扯多了）
下面我们来说说归并排序吧！
所谓归并排序就是将一组数进行无数次分割，将它划分成一个个有序的区间，然后再将这一个个有序的区间一个个合并成有序的区间。
怎么划分？
那这就是一个二分的过程了。我们每次将一段数进行分开，我们在这里引入一个mid为中间位置，一直将l到mid进行分，知道mid=l，这说明他已经将一个个连续的区间划分成一个个独立的区间了。这样我们在在一个个进行合并的时候由于我们划分成两个区间（即两个两个区间进行合并），并且每一个区间都是有序的。
实际上归并排序的交换次数就是这个数组的逆序对个数，为什么呢？
我们可以这样考虑：
归并排序是将数列a[l,h]分成两半a[l,mid]和a[mid+1,h]分别进行归并排序，然后再将这两半合并起来。
在合并的过程中（设l<=i<=mid，mid+1<=j<=h），当a[i]<=a[j]时，并不产生逆序数；当a[i]>a[j]时，在
前半部分中比a[i]大的数都比a[j]大，将a[j]放在a[i]前面的话，逆序数要加上mid+1-i。因此，可以在归并
排序中的合并过程中计算逆序数.
这样对于归并排序求逆序对其实就是在归并排序的基础上加上了一个统计逆序对的过程。
那样如果我们在进行合并的时候找到前一个区间的值比后一个区间的值大，那样是不是就说明从这个数往后的所有数都比这个数小，那样的话就说明从这个数往后的所有数多会与下一个区间的数形成逆序对，那样的话我们在统计逆序对个数的时候就直接将这个区间的之后比这个数大的数的个数。以此类推。。。
下面附上代码：
#include<cstdio>#include<iostream>#include<algorithm>#define N 100001using namespace std;int n,a[N];long long ans;void gsort(int l,int r){ if(l==r) return ; int mid=(l+r)/2;int tmp[N]; gsort(l,mid),gsort(mid+1,r); int i=l,j=mid+1,k=l; while(i<=mid&&j<=r) { if(a[i]<=a[j]) tmp[k++]=a[i++]; else { ans+=mid-i+1; tmp[k++]=a[j++]; } } while(i<=mid) tmp[k++]=a[i++]; while(j<=r) tmp[k++]=a[j++]; for(int i=l;i<=r;i++) a[i]=tmp[i];}int main(){ scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&a[i]); gsort(1,n); cout<<ans; return 0;}
§树状数组求逆序对
（这种做法我就没打算用）
从大佬博客里粘了个代码，就凑活着看看吧。。。
#include <algorithm>#include <cstdio>#define lowbit(x) (x&(-x))using namespace std;const int N(40000+15);int n,x,c[N],ans;struct Node{ int num,mark;}a[N];bool cmp(Node a,Node b){ return a.num>b.num;}inline void up(int x){ for(;x<=N;x+=lowbit(x)) c[x]++;}inline int query(int x){ int ret=0; for(;x;x-=lowbit(x)) ret+=c[x]; return ret;}int main(){ scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&a[i].num),a[i].mark=i; sort(a+1,a+n+1,cmp); for(int i=1;i<=n;i++) { ans+=query(a[i].mark); up(a[i].mark); } printf("%d",ans); return 0;
}
大佬博客http://www.cnblogs.com/Shy-key/p/6930563.html
逆序对