4163 hzwer与逆序对
时间限制: 10 s
空间限制: 256000 KB
题目等级 : 黄金 Gold
题目描述 Description
hzwer在研究逆序对。
对于数列{a}，如果有序数对(I,j)满足：i<j,a[i]>a[j]，则(i,j)是一对逆序对。
给定一个数列{a}，求逆序对个数。
输入数据较大，请使用scanf代替cin读入。
输入描述 Input Description
第一行一个数n,表示{a}有n个元素。
接下来n个数，描述{a}。
输出描述 Output Description
一个数，表示逆序对个数。
样例输入 Sample Input
5
3 1 5 2 4
样例输出 Sample Output
4
数据范围及提示 Data Size & Hint
对于10%数据，1<=n<=100.
对于20%数据，1<=n<=10000.
对于30%数据，1<=n<=100000.
对于100%数据，1<=n<=1000000,1<=a[i]<=10^8.
#include<cstdio>
#include<iostream>
using namespace std;
#include<algorithm>
#include<cstring>
#define MAXN 1000001
struct node { long long v;
int id;
bool operator<(const node &p) const{return v<p.v;}
};
node a[MAXN+];
long long int c[MAXN+],b[MAXN+];
int n;
inline int lowbit(int x)
{
return x&(-x);
}
long long query(int x)
{
long long ans=;
while(x)
{
ans+=c[x];
x-=lowbit(x);
}
return ans;
}
void change(int x)
{
while(x<=n)
{
c[x]++;
x+=lowbit(x);
}
}
int main()
{
scanf("%d",&n);
memset(a,,sizeof(a));
memset(c,,sizeof(c));
memset(b,,sizeof(b));
for(int i=;i<=n;++i)
{
scanf("%d",&(a[i].v));
a[i].id=i;
}
sort(a+,a+n+);
int pre=-;
int prevalue=;
for(int i=;i<=n;++i)
{
if(pre!=a[i].v)
{
pre=a[i].v;
a[i].v=++prevalue;
}
else a[i].v=prevalue;
}
for(int i=;i<=n;++i)
b[a[i].id]=a[i].v;
long long int s=;
for(int i=n;i>=;--i)
{
change(b[i]);
s+=query(b[i]-);
}
cout<<s<<endl;
return ;
}