本文共 862 字，大约阅读时间需要 2 分钟。

求逆序数  ----》 离散化

#include
   
    #include
    
     #include
     
      #include
      
       using namespace std;#define M 1000005typedef __int64 LL;LL a[M];int n;struct node{    LL x,y;}s[M];bool cmp(node p,node q){    return p.x < q.x;}LL lowbit(LL x){    return x&(-x);}void add(LL pos,LL num){    while(pos <= n)    {        a[pos]+=num;        pos += lowbit(pos);    }}LL getsum(LL pos){    LL res = 0;    while(pos > 0)    {        res += a[pos];        pos -= lowbit(pos);    }    return res;}int main(){   while(scanf("%d",&n)!=EOF)   {       memset(a,0,sizeof(a));       for(LL i = 1;i <= n;i++)       {           scanf("%I64d",&s[i].x);           s[i].y = i;       }       sort(s+1,s+n+1,cmp);       LL ret = 0;       for(LL i = 1;i <= n;i++)       {           add(s[i].y,1);           ret += i - getsum(s[i].y);       }       printf("%I64d\n",ret);   }}
      
     
    
   

转载地址：http://qysgi.baihongyu.com/