树状数组 + 离散化
逆序对
#include <map>
#include <set>
#include <queue>
#include <cmath>
#include <cstdio>
#include <vector>
#include <cstring>
#include <sstream>
#include <iostream>
#include <algorithm>
#define x first
#define y second
#define int long long
using namespace std;
const int N = 1e6 + 10;
typedef unsigned long long ULL;
typedef long long LL;
typedef pair<int, int> PII;
int n, q;
int m;
int tr[N], a[N];
map<int, int> mp;
int lowbit(int x) {
return x & -x;
}
void add(int x, int v) {
for (int i = x; i <= m; i += lowbit(i))
tr[i] += v;
}
int query(int r) {
int ans = 0;
for (int i = r; i; i -= lowbit(i)) {
ans += tr[i];
}
return ans;
}
signed main() {
while (cin >> n) {
if (n == 0) break;
mp.clear();
vector<int> v;
for (int i = 0; i < n; i ++ ) {
cin >> a[i];
a[i] += 1;
v.push_back(a[i]);
}
sort(v.begin(), v.end());
int idx = 1;
for (int i = 0; i < v.size(); i ++ ) {
mp[v[i]] = idx ++ ;
}
m = mp.size() + 10;
for (int i = 0; i <= m; i ++ ) {
tr[i] = 0;
}
int ans = 0;
for (int i = 0; i < n; i ++ ) {
ans += query(m) - query(mp[a[i]]);
add(mp[a[i]], 1);
}
cout << ans << endl;
}
return 0;
}