首页 > 代码库 > Inversions
Inversions
There are N integers (1<=N<=65537) A1, A2,.. AN (0<=Ai<=10^9). You need to find amount of such pairs (i, j) that 1<=i<j<=N and A[i]>A[j].
Input
The first line of the input contains the number N. The second line contains N numbers A1...AN.
Output
Write amount of such pairs.
Sample test(s)
Input
5
2 3 1 5 4
2 3 1 5 4
Output
3
#include<cstdio>#include<cstdlib>#include<cstring>#include<cmath>#include<algorithm>#define MAXN 65540using namespace std;struct node{ long long v; int id; bool operator<(const node&p)const {return v<p.v;}};node a[MAXN+10];long long c[MAXN+10];long long b[MAXN+10];int n;long long lowbit(long long a){ return a&(-a);}long long sum(long long a){ long long s=0; while(a>0) { s+=c[a]; a-=lowbit(a); } return s;}void update(long long a){ while(a<=n+1) { c[a]++; a+=lowbit(a); }}int main(void){ while(scanf("%d",&n)==1) { memset(a,0,sizeof(a)); memset(c,0,sizeof(c)); memset(b,0,sizeof(b)); int i; for(i=1;i<=n;i++) { scanf("%lld",&(a[i].v)); a[i].id=i; } sort(a+1,a+n+1); int pre=-1; int prevalue=http://www.mamicode.com/0; for(i=1;i<=n;i++) { if(pre!=a[i].v) { pre=a[i].v; a[i].v=++prevalue; } else { a[i].v=prevalue; } } for(i=1;i<=n;i++) { b[a[i].id]=a[i].v; } long long s=0; for(i=n;i>=1;i--) { update(b[i]); s+=sum(b[i]-1); } printf("%I64d\n",s); } return 0;}
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。