poj-2299

版权声明：转载请注明出处。 https://blog.csdn.net/u014427196/article/details/40748047

树状数组求逆序数
看了这位大牛的题解才茅塞顿开：http://www.cnblogs.com/shenshuyang/archive/2012/07/14/2591859.html

首先离散化，再求逆序数.

#include<stdio.h>
#include<iostream>
#include<math.h>
#include<stdlib.h>
#include<algorithm>
#include<vector>
#include<string.h>
#include<queue>
#include<stack>
#include<set>
#include<map>
#include <malloc.h>

using namespace std;

struct qq
{
    int x;
    int pos;
}a[500005];

int c[500005];
int b[500005];
int n;

bool cmp(qq a ,qq b)
{
    return a.x < b.x;
}

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

int sum (int i)
{
    int ans = 0;
    while (i>0)
    {
        ans += b[i];
        i-=lowbit(i);
    }
    return ans;
}

void updown(int i)
{
    while (i<=n)
    {
        b[i] += 1;
        i+=lowbit(i);
    }
}

int main ()
{
    while (scanf ("%d",&n)!=EOF && n!=0)
    {

        for (int i=1 ;i<=n;i++)
           {
               scanf ("%d",&a[i].x);
               a[i].pos=i;
           }

         sort (a+1,a+1+n,cmp);

         for (int i=1 ;i<=n;i++)
            c[a[i].pos]=i;

        memset (b,0,sizeof (b));

        long long  ans = 0;
        for (int i =1 ;i<=n;i++)
        {
            updown(c[i]);
            ans += i-sum(c[i]);
        }

        printf("%I64d\n",ans);
    }
    return 0;
}