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=;

struct data

{

    LL x,num;

}a[N];

LL p[N],c[N],i,n,ans;

inline void read(LL &x)

{

    x=; char ch=getchar();

    while (ch<''||ch>'') ch=getchar();

    while (ch>=''&&ch<='') x=x*+ch-'',ch=getchar();

}

inline void write(LL x)

{

    if (x/) write(x/);

    putchar(x%+'');

}

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=;

    while (x)

    {

        res+=c[x];

        x-=lowbit(x);

    }

    return res;

}

inline void add(LL x)

{

    while (x<=n)

    {

        c[x]+=;

        x+=lowbit(x);

    }

}

int main()

{

    for (;;)

    {

        memset(c,,sizeof(c));

        read(n); ans=;

        if (!n) break;

        for (i=;i<=n;++i)

        read(a[i].x),a[i].num=i;

        sort(a+,a+n+,comp);

        for (i=;i<=n;++i)

        p[a[i].num]=i;

        for (i=;i<=n;++i)

        ans+=get(n)-get(p[i]),add(p[i]);

        write(ans); putchar('\n');

    }

    return ;

}

巴特西

POJ 2299

最新文章

热门文章