学步园

树状数组+离散化

话说真的是越来越爱树状数组了，求逆序数真的是神器。

正题，题意就是一串数字进行排序，问若对该串数字进行排序的时候，总共需要多少次交换。

就是求逆序数啊，但是数据最大是999,999,999，所以要离散化的说。

离散化就是建两个数组啦，一个记录数值，一个记录位置，然后将数值的函数排序，然后将数值的数组根据位置赋值。

具体见代码吧。。。。语言过于无力。

#include <cstdio>
#include <string.h>
#include <algorithm>
using namespace std;

const int maxn=500010;
struct node//用来记录数值和位置
{
    int val;
    int pos;
}st[maxn];
int c[maxn];int re[maxn];int n;
bool cmp(const node&a,const node&b)
{
    return a.val<b.val;
}
int lowbit(int i)
{
    return i&(-i);
}
int sum(int i)
{
    int ans=0;
    while(i>0)
    {
        ans+=c[i];
        i-=lowbit(i);
    }
    return ans;
}
void update(int i,int val)
{
    while(i<=n)
    {
        c[i]+=val;
        i+=lowbit(i);
    }
}
int main()
{
    while(scanf("%d",&n),n)
    {
        long long ans=0;
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&st[i].val);
            st[i].pos=i;
        }
        sort(st+1,st+n+1,cmp);
        for(int i=1;i<=n;i++)//离散化
        {
            re[st[i].pos]=i;
        }
        memset(c,0,sizeof(c));
        for(int i=1;i<=n;i++)
        {
            update(re[i],1);
            ans+=i-sum(re[i]);
        }
        printf("%lld\n",ans);
    }
}