POJ 2299

　　上课讲了下数据结构，因为暂时没找到分块的板子题，所以做一下这道题加深一下对树状数组的理解。

　　题意就是求逆序对，从逆序对的定义就可以看出，方法有两种：归并 or 树状数组。

　　感觉树状数组更高级一点，写起来也比较容易（其实是不会归并）

　　在这里由于a[i]太大（0~999999999），因此离散化一下，也就是开个结构体排序后看一下它在第几个。

　　一个数产生的逆序对数就是它前面的比它大的个数。

　　因此对于x，先查询sum(x+1,n)的值，再add(x)即可。

　　CODE

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
typedef long long LL;
const LL N=500005;
struct data
{
    LL x,num;
}a[N];
LL p[N],c[N],i,n,ans;
inline void read(LL &x)
{
    x=0; char ch=getchar();
    while (ch<'0'||ch>'9') ch=getchar();
    while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
}
inline void write(LL x)
{
    if (x/10) write(x/10);
    putchar(x%10+'0');
}
inline LL comp(data a,data b)
{
    return a.x<b.x;
}
inline LL lowbit(LL x)
{
    return x&(-x);
}
inline LL get(LL x)
{
    LL res=0;
    while (x)
    {
        res+=c[x];
        x-=lowbit(x);
    }
    return res;
}
inline void add(LL x)
{
    while (x<=n)
    {
        c[x]+=1;
        x+=lowbit(x);
    }
}
int main()
{
    for (;;)
    {
        memset(c,0,sizeof(c));
        read(n); ans=0;
        if (!n) break;
        for (i=1;i<=n;++i)
        read(a[i].x),a[i].num=i;
        sort(a+1,a+n+1,comp);
        for (i=1;i<=n;++i)
        p[a[i].num]=i;
        for (i=1;i<=n;++i)
        ans+=get(n)-get(p[i]),add(p[i]);
        write(ans); putchar('
');
    }
    return 0;
}