树状数组+离散化 求逆序对
#include<bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10 ;
int n ;
int b[N] ;
vector<int> alls ;
vector<int> a ;
int tr[N] ;
#define pb push_back
int find(int x)
{
int l = 0 , r = alls.size() - 1 ;
while(l < r)
{
int mid = r + l >> 1 ;
if(alls[mid] >= x) r = mid ;
else l = mid + 1;
}
return r + 1;
}
int lowbit(int x)
{
return x & -x ;
}
int sum(int x)
{
long long res = 0 ;
for(int i = x ; i ; i -= lowbit(i)) res += tr[i] ;
return res;
}
void add(int x , int c)
{
for(int i = x ; i <= n ; i += lowbit(i)) tr[i] += c ;
}
int main()
{
cin >> n ;
for(int i = 1 ; i <= n ; i ++)
{
int x ;
cin >> x ;
alls.pb(x);
a.pb(x);
}
sort(alls.begin(),alls.end()); // 去重
alls.erase(unique(alls.begin(),alls.end()),alls.end());
long long res = 0 ;
for(int i = 0 ; i < n ; i ++)
{
int y = find(a[i]) ;
res += sum(n) - sum(y) ;
add(y,1);
}
cout << res << endl;
return 0;
}