首页 > 代码库 > Inversions

Inversions

2024-07-12 08:39:50   211人阅读

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
 
 

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;}

 


联系
我们