poj 2299 逆序数

http://poj.org/problem?id=2299

坑：答案是long long 输出……！！！！！

题意是：求一个数组进行冒泡排序交换的次数

题解：求逆序数

题解Ⅰ：

归并排序求逆序数

归并排序求逆序数之前写过

1.归并排序是把两个有序的数组合并成为一个有序的数组，利用分治的思想就可以进行排序

　　逆序数可以利用这个思想求

　　求出第一个数组的逆序数，和第二个数组的逆序数，再将两个数组整体的逆序数求出来

　　f(x,y) = f(x,mid) + f(mid,y) + 之后数组的逆序数

#include <iostream>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <cstdlib>
#include <vector>
#include <map>
#include <queue>
#include <stack>
const int MAXN =  500000 + 10;
const int INF = 0x7fffffff;
const int MOD = 1000007;
const double ESP = 10e-8;
const double Pi = acos(-1.0);
typedef long long LL;
using namespace std;
LL a[MAXN];
LL b[MAXN];
LL h(int s,int e){
    if(e-s <= 1){
        return 0;
    }
    int mid = s + (e-s)/2;
    LL x = h(s,mid);
    LL y = h(mid,e);
    int p1 = s;
    int p2 = mid;
    int p3 = s;
    LL cnt = 0;
    while(p1 < mid || p2 < e){
        if(p2 >= e || (p1 < mid && a[p1] < a[p2])){
            b[p3++] = a[p1++];
        }
        else{
            b[p3++] = a[p2++];
            cnt += (mid-p1); /*第二个数组当前元素比第一个数组当前元素小，所以第一个数组从当前元素到最后的元素都比第二个数组的大（数组一，二都已经有序了），所以第一个数组结尾下标，减去第一个数组的当前元素就是两个数组的逆序数*/
        }
    }
    for(int i = s;i < e;i++){
        a[i] = b[i];
    }
    return x+y+cnt;
}
int main(){
    //freopen("input.txt","r",stdin);
    int n;
    while(~scanf("%d",&n) && n){
        for(int i = 0;i < n;i++){
            scanf("%d",&a[i]);
        }
        LL ans = h(0,n);
        printf("%lld
",ans);
    }
    return 0;
}

题解Ⅱ：

http://www.cnblogs.com/shenshuyang/archive/2012/07/14/2591859.html

这个童鞋写得已经很棒了
1.数组元素太大，而n 的个数又很少，所以需要离散化

离散化：

用struct Node{

　　int v;

　　int order;

};

将元素读入，并且将元素的次序读入

将元素排序之后，下标的标号一定程度上是代表元素的大小

所以用下标的标号就可以表示元素

这样范围就减少了

2.

树状数组是求 前 i 个 元素的和

先 add(a[i],1)

再 i - sum(a[i]) 

前面已经有 i 个元素了，sum(a[i]) 表示 1 - a[i] 的和 ，而 i - sum(a[i])  表示有多少个数字比 a[i] 大 但是 次序却在 i 位置的前面  就是 a[i] 元素的逆序数

#include <iostream>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <cstdlib>
#include <vector>
#include <map>
#include <queue>
#include <stack>
const int MAXN =  500000 + 10;
const int INF = 0x7fffffff;
const int MOD = 1000007;
const double ESP = 10e-8;
const double Pi = acos(-1.0);
typedef long long LL;
using namespace std;
int a[MAXN];
int bit[MAXN+1];
int n;
struct Node{
    int v;
    int order;
    bool operator < (const Node x)const{
        return v < x.v;
    }
};
Node in[MAXN];
int sum(int i){
    int s = 0;
    while(i>0){
        s += bit[i];
        i -= (i & -i);
    }
    return s;
}
void add(int i,int x){
    while(i <= n){
        bit[i] += x;
        i += (i&-i);
    }
}
int main(){
//    freopen("input.txt","r",stdin);
    while(~scanf("%d",&n) && n){
        memset(bit,0,sizeof(bit));
        for(int i = 1;i <= n;i++){
            scanf("%d",&in[i].v);
            in[i].order = i;
        }
        sort(in+1,in+1+n);
        for(int i = 1;i <= n;i++){
            a[in[i].order] = i;
        }
        LL ans = 0;
        for(int i = 1;i <= n;i++){
            add(a[i],1);
            ans += i-sum(a[i]);
        }
        printf("%lld
",ans);
    }
    return 0;
}