- 给定一个长度为 n 的整数数列，请你计算数列中的逆序对的数量。每个数字不超过1e9。
int n, m;
int a[N];
int tr[N];
vector<int>lan;
int lowbit(int x){
return x&(-x);
}
void discrete()
{
sort(lan.begin(), lan.end()); //排序
lan.erase(unique(lan.begin(), lan.end()), lan.end()); //去重
}
//查询
int find(int x)
{
return lower_bound(lan.begin(), lan.end(), x)-lan.begin()+1; //返回所查询的数据的下标
}
void add(int x,int c){
for(int i=x;i<=n;i+=lowbit(i))tr[i]+=c;
}
int query(int x){
int res=0;
for(int i=x;i;i-=lowbit(i))res+=tr[i];
return res;
}
void solve(){
cin>>n;
for(int i=1;i<=n;i++)cin>>a[i];
for(int i=1;i<=n;i++)lan.push_back(a[i]);
discrete();
int mx=lan.size();
ll cnt=0;
for(int i=1;i<=n;i++){
cnt+=query(mx)-query(find(a[i]));
add(find(a[i]),1);
}
cout<<cnt<<endl;
}