题目描述
给定一个序列a1,a2,…,an，如果存在i<j并且ai>aj，那么我们称之为逆序对，求逆序对的数目。
输入
第一行，一个数 n，表示序列中有 n个数。
第二行 n 个数，表示给定的序列。序列中每个数字不超过 109。
输出
输出序列中逆序对的数目。
样例输入
4
3 2 3 2样例输出
3/*
lowbit函数求解
lowbit这个函数的功能就是求某一个数的二进制表示中最低的一位1，举个例子，x = 6，它的二进制为110，那么lowbit(x)就返回2，因为最后一位1表示2
lowbit函数求解有以下两种方式。
方式一：先消掉最后一位1，然后再用原数减去消掉最后一位1后的数，答案就是lowbit(x)的结果；
方法二：原数与原数的相反数进行相与操作。（解释的话如果学过计算机组成原理之类的很容易明白，）负数在计算机中以补码的形式存储。
*/
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=5e6+10;
int tr[N*2],maxn;
int lowbit(int x){return x&(-x);
}void add(int x,int v) {while (x<=maxn){tr[x]+=v;x+=lowbit(x);}
}int sum(int x){int ans=0;while(x){ans+=tr[x];x-=lowbit(x);}return ans;
}signed main(){int ans=0;cin>>maxn;for(int i=1;i<=maxn;i++){int v;cin>>v;add(v,1);ans+=i-sum(v);}cout<<ans;
}
