求逆序对（树状数组和归并）
树状数组求逆序对，归并排序求逆序对。
一 树状数组
http://www.cnblogs.com/wdvxdr/p/7300717.html
我看了这篇博客，才逐渐明白的，树状数组求逆序对的一种思路。
①桶排序，把数组a[]的元素放在一个很大的数组b里面，（确保a的元素最大值不超过b的大小）
挨个把a中的元素放到b中去，，就是令b[a[i]]=1，每次求已经放入的元素个数减去a[i]前面的元素个数（包括a[i])
用树状数组的单点修改,区间求和可以很好地完成。（手动写代码ing）
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
using namespace std;
int a[500005],b[500005],n;
int lowbit(int x){
return x&(-x);
}
void add(int x){
while(x<500005){
b[x]++;
x+=lowbit(x);
}
}
int getsum(int x){
long long sum=0;
while(x>0){
sum+=b[x];
x-=lowbit(x);
}
return sum;
}
int main()
{
long long n,i,ans;
while(cin>>n){//n为数的总数.
ans=0;
memset(b,0,sizeof(b));
for(i=1;i<=n;i++){
cin>>a[i];
add(a[i]);
ans+=i-(getsum(a[i]));//当前加入b的元素个数减去a[i]及其前面的元素个数
}
cout<<ans<<endl;
}
}
比如5个数，9 ，1，2，7，5。先把b[9]置为1，此时9前面没有数，再把b[1]置为1，此时1前面没有数（比一小的数），并且已经插入了两个数，那么就说明a[]这个序列在1的前面有一个比一大的数，即有一对逆序数。
再把b[2]置为1，二的前面有一个比自己小的数1，此时已经插入了三个数，那么就说明a[]这个序列中，有一个比2大的数，即有一对逆序数。以此类推，就全部求出来了。
②前面的方法很简单，但是限制实在太多，比如只能求正整数的逆序对（b的下标不能为负数），如果a中的元素最大值很大，就会超时。
那么就需要进行离散化。这玩意实在有点难理解。
首先，需要把a设置为结构体数组，结构体保存的值为元素大小，及下标。
然后将a按照元素大小用sort函数排序，记得写自定义的排序方式，还有就是因为a的下标从1开始，所以sort(a+1,a+n+1,cmp)。
不是sort(a,a+n,cmp)。
这里有两种方法去做，虽然代码差不多，但是我个人认为有很大的不同。
第一种
https://blog.csdn.net/ssimple_y/article/details/53744096我看这博客做的。
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
using namespace std;
int b[500005],n,t[500005];
struct node{
int pos,v;
}a[500005];
bool cmp(node x,node y){
return x.v<y.v;
}
int lowbit(int x){
return x&(-x);
}
void add(int x){
while(x<500005){
b[x]++;
x+=lowbit(x);
}
}
int getsum(int x){
long long sum=0;
while(x>0){
sum+=b[x];
x-=lowbit(x);
}
return sum;
}
int main()
{
long long n,i,ans,cnt;
while(cin>>n){//n为数的总数.
ans=0;
memset(b,0,sizeof(b));
for(i=1;i<=n;i++){
cin>>a[i].v;
a[i].pos=i;
}
sort(a+1,a+n+1,cmp);
cnt=1;
for(i=1;i<=n;i++){
if(i!=1&&a[i].v!=a[i-1].v)
cnt++;
t[a[i].pos]=cnt;
}
for(i=1;i<=n;i++){
add(t[i]);
ans+=(i-getsum(t[i]));
}
cout<<ans<<endl;
}
}
这种方法的思想和前面的是一样的，按照顺序依次插入，并且求前面有多少个数，再用已插入的数的个数减去。
cnt的作用就是避免有大小相同的元素。pos代表的是a中元素插入的顺序，比如还是那五个数9，1，2，7，5。
9的pos是1，1的pos是2，5的pos是5。按照a中元素大小排序之后，9在最后一位，1在第一位，5在第三位。
此时cnt代表的是元素大小关系，9对应的cnt为5，1对应的cnt为1，5对应的cnt为3。那么此时的pos所对应的数的相对大小依然没有变（pos是原来的序列的顺序）比如pos为1的数是9，是这个序列中最大的数。排序后，a的序列v值为1 2 5 7 9；（最重要的是pos没有变，1这个数对应的pos依然是2，因为它是原来的序列的第二个数，9对应的pos依然是1，也就是说，pos为2的数是1，
pos为1的数是9）t[a[i].pos]=cnt;在这个操作后，pos所对应的数的相对大小没有变化。pos为1的cnt为5（9是最大的），pos为2cnt为1（1是最小的）pos为5的cnt为3（5是第三大的）
最后，在调用add（)函数的时候，i为1实际上是a[i].pos为1，也就是说，这样是按照原来的顺序插入的。这是模拟前面所讲的方法。
第二种
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
using namespace std;
int b[500005],n,t[500005];
struct node{
int pos,v;
}a[500005];
bool cmp(node x,node y){
if(x.v==y.v)return x.pos<y.pos;
return x.v<y.v;//当值相等的时候，按照输入先后排序
}
int lowbit(int x){
return x&(-x);
}
void add(int x){
while(x<500005){
b[x]++;
x+=lowbit(x);
}
}
int getsum(int x){
long long sum=0;
while(x>0){
sum+=b[x];
x-=lowbit(x);
}
return sum;
}
int main()
{
long long n,i,ans,cnt;
while(cin>>n){//n为数的总数.
ans=0;
memset(b,0,sizeof(b));
for(i=1;i<=n;i++){
cin>>a[i].v;
a[i].pos=i;
}
sort(a+1,a+n+1,cmp);
/*cnt=1;
for(i=1;i<=n;i++){
if(i!=1&&a[i].v!=a[i-1].v)
cnt++;
t[a[i].pos]=cnt;
} 将这一段删去*/
for(i=1;i<=n;i++){
add(a[i].pos);//直接add排序后的pos。
ans+=(i-getsum(a[i].pos));
}
cout<<ans<<endl;
}
}
这样做的意思是先排序，然后按照从小到大的顺序插入pos。这样的话，每次插入的数一定比之前插入的大，把b[a[i].pos]置为1，a[i].pos之前的数就是原序列中比a[i].v小的数，用已经插入的数的个数减去，就是逆序对的个数。
二 归并排序
归并排序求逆序对需要注意的就是因为两部分已经拍好戏了，每次加的应该是mid-i-1；手动模拟一遍就懂了。
#include<iostream>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<set>
#include<cstdio>
using namespace std;
long long a[100005],cnt;
void merge(int L,int mid,int R){
int temp[100005],i=L,j=mid+1,k=0;
while(i<=mid&&j<=R){
if(a[i]>a[j]){
temp[k]=a[j];
k++;j++;
cnt+=(mid-i+1);//对于左边，因为i后面的数都比i这个位置的数大
}//直到mid肯定都比a[j]大
else{
temp[k]=a[i];
k++;i++;
}
}
while(i<=mid){
temp[k]=a[i];
k++;i++;
}
while(j<=R){
temp[k]=a[j];
k++;j++;
}
for(i=L,k=0;i<=R;i++){
a[i]=temp[k];
k++;
}
}
void mergeup(int L,int R){
if(L==R)return;
int mid=(L+R)/2;
mergeup(L,mid);
mergeup(mid+1,R);
merge(L,mid,R);
}
int main()
{
int n,i;
while(cin>>n){
cnt=0;
for(i=0;i<n;i++){
cin>>a[i];
}
mergeup(0,n-1);
cout<<cnt<<endl;
}
return 0;
}