算法1

(暴力枚举) $O(n^2)$

就是暴力枚举逆序对数量。

算法2

(树状数组) $O(n^2)$

树状数组求逆序对。

C++ 代码

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll N = 5e5+10;
ll a[N],b[N],c[N],n;
void update(ll x){
    for(;x<=n;x+=-x&x) c[x]++;
}
ll sum(ll x){
    ll ans = 0;
    for(;x>0;x-=-x&x)ans+=c[x];
    return ans;
}
int main(){
    while(~scanf("%lld",&n)&&n){
        ll ans = 0; 
        memset(c,0,sizeof(c));
        for(ll i = 1; i <= n; i++) scanf("%lld",&a[i]),b[i]=a[i];
        sort(a+1,a+1+n);
        for(ll i=1;i<=n;i++) b[i]=lower_bound(a+1,a+1+n,b[i])-a;
        for(ll i=n;i;i--){
            update(b[i]);
            ans+=sum(b[i]-1);
        }
        printf("%lld\n",ans);
    }
    return 0;
}