POJ 2299 Ultra-QuickSort（求逆序对）

题目链接：http://poj.org/problem?id=2299

题目大意：给定一个数组，按冒泡排序规则，问需要交换多少次，才能成为有序序列

题目思路：就是求逆序对的数量就是交换次数，因为每一前面大的数都会和后面小的交换一次

求逆序对有三种方法：归并排序，树状数组，线段树

可参见：https://blog.csdn.net/baodream/article/details/80355881

第一种：归并排序求逆序对

#include<cstdio>
#include<cmath>
#include<cstring>
#include<string>
#include<cstdlib>
#include<algorithm>
#include<iostream>
#include<queue>
#include<stack>
#include<map>

using namespace std;

#define FOU(i,x,y) for(int i=x;i<=y;i++)
#define FOD(i,x,y) for(int i=x;i>=y;i--)
#define MEM(a,val) memset(a,val,sizeof(a))
#define PI acos(-1.0)

const double EXP = 1e-9;
typedef long long ll;
typedef unsigned long long ull;
const int INF = 0x3f3f3f3f;
const ll MINF = 0x3f3f3f3f3f3f3f3f;
const double DINF = 0xffffffffffff;
const int mod = 1e9+7;
const int N = 1e6+5;

int a[N];     //需要排序的数组
int temp[N];   //中间合并用数组
ll g_nCount;  //逆序对数量

void MergeArray(int l,int r,int mid) //合并两序列
{
    int i=l,n=mid;    //左子序列指针
    int j=mid+1,m=r;  //右子序列指针
    int k=0;          //temp数组指针
    while(i<=n&&j<=m)
    {
        if(a[i]<=a[j])
            temp[k++] = a[i++];
        else
        {
            temp[k++] = a[j++];
            //a[j]和前面每一个数都能组成逆序数对
            g_nCount+=n-i+1;
        }
    }
    while(i<=n)
        temp[k++] = a[i++];
    while(j<=m)
        temp[k++] = a[j++];
    for(int t=0;t<k;t++)   //拷贝回去
        a[l+t] = temp[t];
}

void Merge_sort(int l,int r) //归并排序,0~n-1的数组，则l=0,r=n-1
{
    if(l<r)
    {
        int mid = (l+r)>>1;
        Merge_sort(l,mid);   //左子序列排序
        Merge_sort(mid+1,r); //右子序列有序
        MergeArray(l,r,mid); //两边合并
    }
}


int main()
{
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    std::ios::sync_with_stdio(false);
    int n;
    while(cin>>n)
    {
        if(n==0)
            break;
        g_nCount=0;
        for(int i=0;i<n;i++)
            cin>>a[i];
        Merge_sort(0,n-1);
        cout<<g_nCount<<endl;
    }
    return 0;
}

第二种：树状数组求逆序对

#include<cstdio>
#include<cmath>
#include<cstring>
#include<string>
#include<cstdlib>
#include<algorithm>
#include<iostream>
#include<queue>
#include<stack>
#include<map>

using namespace std;

#define FOU(i,x,y) for(int i=x;i<=y;i++)
#define FOD(i,x,y) for(int i=x;i>=y;i--)
#define MEM(a,val) memset(a,val,sizeof(a))
#define PI acos(-1.0)

const double EXP = 1e-9;
typedef long long ll;
typedef unsigned long long ull;
const int INF = 0x3f3f3f3f;
const ll MINF = 0x3f3f3f3f3f3f3f3f;
const double DINF = 0xffffffffffff;
const int mod = 1e9+7;
const int N = 1e6+5;

int tree[N];
int n;
struct node
{
    int val;  //输入数据的值
    int id;   //输入数据的位置
}a[N];

int b[N];     //离散化数组

bool cmp(node A,node B)
{
    if(A.val==B.val)
        return A.id<B.id;
    return A.val<B.val;
}

int lowbit(int x)
{
    return x & (-x);
}

int getsum(int x)
{
    int res = 0;
    while(x)
    {
        res+=tree[x];
        x-=lowbit(x);
    }
    return res;
}

void add(int x,int val)
{
    while(x<=n)
    {
        tree[x]+=val;
        x+=lowbit(x);
    }
}

void init()
{
    for(int i=1;i<=n;i++)
        tree[i]=0;
}

ll get_Reverse_pair_count()
{
    init();  //初始化树状数组
    sort(a+1,a+1+n,cmp);
    for(int i=1;i<=n;i++)  //离散化操作
        b[a[i].id]=i;      //将a[i]数组映射成更小的值
    ll ans=0;
    for(int i=1;i<=n;i++)  //更新树状数组
    {
        add(b[i],1);       //意思是b[i]的值加1
        ans+=(i-getsum(b[i])); //求得比b[i]小的个数,则i减getsum(b[i])就是前面能够和b[i]构成逆序对的数量
    }
    return ans;
}

int main()
{
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    std::ios::sync_with_stdio(false);
    while(cin>>n)
    {
        if(n==0)
            break;
        for(int i=1;i<=n;i++)
        {
            cin>>a[i].val;
            a[i].id=i;
        }
        cout<<get_Reverse_pair_count()<<endl;
    }
    return 0;
}

第一种：线段树求逆序对

待补。