题意：在一个排列中，如果一对数的前后位置与大小顺序相反，即前面的数大于后面的数，那么它们就称为一个逆序。一个排列中逆序的总数就称为这个排列的逆序数。

如2 4 3 1中，2 1，4 3，4 1，3 1是逆序，逆序数是4。给出一个整数序列，求该序列的逆序数。

思路：

https://www.nowcoder.com/live/153/11/1 53min开始

举个栗子：

有5个数，分别为5 3 4 2 1，

当读入数据a=5时，d为：0 0 0 0 0，前缀和为0，4-0=4，ans+=4然后d变成：0 0 0 0 1；

当读入数据a=3时，d为：0 0 0 0 1，前缀和为0，2-0=2，ans+=2，然后d变成：0 0 1 0 1；

当读入数据a=4时，d为：0 0 1 0 1，前缀和为1，3-1=2，ans+=2，然后d变成：0 0 1 1 1；

当读入数据a=2时，d为：0 0 1 1 1，前缀和为0，1-0=1，ans+=1，然后d变成：0 1 1 1 1；

当读入数据a=1时，d为：0 1 1 1 1，前缀和为0，0-0=0，然后d变成：1 1 1 1 1。

当数据a过大时，数组可能装不下，这时候就需要离散化，用sort+unique+二分离散即可。

代码：

int n;
int a[50010];
int b[50010];
int d[50010];
int lowbit(int x)
{
    return x&(-x);
}
int query(int x)//查询前缀和
{
    int res=0;
    while(x)
    {
        res+=d[x];
        x-=lowbit(x);
    }
    return res;
}
void add(int x,int v)//单点修改
{
    while(x<=n)
    {
        d[x]+=v;
        x+=lowbit(x);
    }
}
int main()
{
    scanf("%d",&n);
    memset(d,0,sizeof(d));
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]),b[i]=a[i];
    sort(b+1,b+n+1);
    int len=unique(b+1,b+n+1)-b;
    int ans=0;
    for(int i=1;i<=n;i++)
    {
        int pos=lower_bound(b+1,b+len,a[i])-b;
        ans+=pos-1-query(pos);
        add(pos,1);
    }
    printf("%d\n",ans);
    return 0;
}