樹狀數組求逆序對的簡單應用。
以下是我的代碼：
#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 閱讀(577)
評論(0) 編輯 收藏 引用 所屬分類:
題目分類：數據結構