心如止水
Je n'ai pas le temps
posts - 400,comments - 130,trackbacks - 0
树状数组求逆序对的简单应用。
以下是我的代码:
#include<iostream>
#include
<algorithm>
#include
<cstdio>
#include
<cstring>
#define lowbit(x) ((x)&(-(x)))
using namespace std;
const int kMaxn(1000007);

struct Type
{
    
int value,num,weight;
};

bool cmp1(const Type &a,const Type &b)
{
    
return (a.value<b.value);
}

bool cmp2(const Type &a,const Type &b)
{
    
return (a.num<b.num);
}

int n,bit[kMaxn];
Type r[kMaxn];
long long ans;

void Add(int pos,int delta)
{
    
for(int i=pos;i<=n;i+=lowbit(i))
        bit[i]
+=delta;
}

int Sum(int pos)
{
    
int re(0);
    
for(int i=pos;i>0;i-=lowbit(i))
        re
+=bit[i];
    
return re;
}

int main()
{
    
//freopen("data.in","r",stdin);

    
while(scanf("%d",&n)==1)
    {
        
for(int i=1;i<=n;i++)
        {
            r[i].num
=i;
            scanf(
"%d",&r[i].value);
        }
        sort(r
+1,r+n+1,cmp1);
        
for(int i=1;i<=n;i++)
            r[i].weight
=i;
        sort(r
+1,r+n+1,cmp2);

        ans
=0ll;
        memset(bit,
0,sizeof(bit));
        
for(int i=1;i<=n;i++)
        {
            ans
+=i-Sum(r[i].weight-1)-1;
            Add(r[i].weight,
1);
        }

        cout
<<ans<<endl;
    }

    
return 0;
}
posted on 2011-08-01 09:55 lee1r 阅读(558) 评论(0)  编辑 收藏 引用 所属分类: 题目分类:数据结构

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理