POJ 2299 Ultra-QuickSort 求逆序数 （归并或者数状数组）此题为树状数组入门题！！！...

#include<queue>
#include<set>
#include<cstdio>
#include <iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
#define max_v 500005
int n;
struct node
{
    int v;
    int pos;
} p[max_v];
int c[max_v];
int re[max_v];
int maxx;
int lowbit(int x)
{
    return x&(-x);
}
void update(int x,int d)
{
    while(x<=n)
    {
        c[x]+=d;
        x+=lowbit(x);
    }
}
int getsum(int x)
{
    int res=0;
    while(x>0)
    {
        res+=c[x];
        x-=lowbit(x);
    }
    return res;
}
bool cmp(node a,node b)
{
    return a.v<b.v;
}
int main()
{
    while(~scanf("%d",&n))
    {
        if(n==0)
            break;
        memset(c,0,sizeof(c));
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&p[i].v);
            p[i].pos=i;
        }

        sort(p+1,p+1+n,cmp);
        for(int i=1;i<=n;i++)
        {
            re[p[i].pos]=i;//离散化
        }

        long long ans=0;
        for(int i=1;i<=n;i++)
        {
            update(re[i],1);
            ans+=(i-getsum(re[i]));//当前位置减去前面比它小的数的个数之和就是答案
        }
        printf("%lld\n",ans);
    }
    return 0;
}
/*
题目意思：
对于给定的无序数组
求除经过多少次相邻的元素交换之后，可以使得数组升序
就是求一个数列的逆序数


从头到尾读入这些数，每读入一个数就更新树状数组，
查看它前面比它小的已出现过的有多少个数sum，
然后用当前位置减去该sum，
就可以得到当前数导致的逆序对数了。
把所有的加起来就是总的逆序对数。
*/

#include<stdio.h>
#include<memory>
#define max_v 500005
typedef long long LL;
LL a[max_v];
LL temp[max_v];
LL ans;
void mer(int s,int m,int t)
{
    int i=s;
    int j=m+1;
    int k=s;
    while(i<=m&&j<=t)
    {
        if(a[i]<=a[j])
        {
            temp[k++]=a[i++];
        }else
        {
            ans+=j-k;//求逆序数
            temp[k++]=a[j++];
        }
    }
    while(i<=m)
    {
        temp[k++]=a[i++];
    }
    while(j<=t)
    {
        temp[k++]=a[j++];
    }
}
void cop(int s,int t)
{
    for(int i=s;i<=t;i++)
        a[i]=temp[i];
}
int megsort(int s,int t)
{
    if(s<t)
    {
        int m=(s+t)/2;
        megsort(s,m);
        megsort(m+1,t);
        mer(s,m,t);
        cop(s,t);
    }
}
int main()
{
    int n;
    while(~scanf("%d",&n))
    {
        if(n==0)
            break;
        ans=0;
        for(int i=0;i<n;i++)
            scanf("%lld",&a[i]);
        megsort(0,n-1);
        printf("%lld\n",ans);
    }
    return 0;
}
/*
题目意思：
对于给定的无序数组
求除经过多少次相邻的元素交换之后，可以使得数组升序
就是求一个数列的逆序数


在归并排序的过程中，比较关键的是通过递归，
将两个已经排好序的数组合并，
此时，若a[i] > a[j]，则i到m之间的数都大于a[j]，
合并时a[j]插到了a[i]之前，此时也就产生的m-i+1个逆序数，
而小于等于的情况并不会产生。
*/