hdu 3743 树状数组

思路：我们只需坚守一个原则，本来就在左边的坚决不把它换到右边。也就是相邻的两个数，左边小，右边大，那么就不调换。这样对每个数，只要统计左边比它大的数的个数。可以从后面开始用树状数组统计比它小的数的个数是一样的。

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cstring>

#define Maxn 1000010

#define lowbit(x) (x&(-x))

using namespace std;

int C[Maxn],num[Maxn],n,r[Maxn];

void init()

{

    memset(C,,sizeof(C));

}

int cmp(int a,int b)

{

    return num[a]<num[b];

}

int Sum(int pos)

{

    int sum=;

    while(pos>)

    {

        sum+=C[pos];

        pos-=lowbit(pos);

    }

    return sum;

}

void update(int pos)

{

    while(pos<=n)

    {

        C[pos]++;

        pos+=lowbit(pos);

    }

}

int main()

{

    int i,j;

    while(scanf("%d",&n)!=EOF)

    {

        init();

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

             scanf("%d",num+i);

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

            r[i]=i;

        sort(r+,r+n+,cmp);

        int cnt=;

        int temp=num[r[]];

        num[r[]]=++cnt;

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

        {

            if(num[r[i]]!=temp) temp=num[r[i]],num[r[i]]=++cnt;

            else num[r[i]]=temp;

        }

        __int64 ans=;

        for(i=n;i>=;i--)

        {

            ans+=(__int64)Sum(num[i]);

            update(num[i]);

        }

        printf("%I64d\n",ans);

    }

    return ;

}

巴特西

hdu 3743 树状数组

最新文章

热门文章