39 lines
941 B
C++
39 lines
941 B
C++
#include <bits/stdc++.h>
|
||
using namespace std;
|
||
|
||
typedef long long LL;
|
||
const int N = 500010;
|
||
int n;
|
||
LL q[N], t[N];
|
||
LL ans; // 结果
|
||
|
||
void merge_sort(LL q[], int l, int r) {
|
||
if (l >= r) return;
|
||
int mid = (l + r) >> 1;
|
||
merge_sort(q, l, mid), merge_sort(q, mid + 1, r);
|
||
|
||
int i = l, j = mid + 1, k = 0;
|
||
while (i <= mid && j <= r)
|
||
if (q[i] <= q[j])
|
||
t[k++] = q[i++];
|
||
else {
|
||
ans += mid - i + 1; // 如果q[i]>q[j],那么 i~mid之间所有数字，都>q[j]
|
||
t[k++] = q[j++];
|
||
}
|
||
// 清理剩余
|
||
while (i <= mid) t[k++] = q[i++];
|
||
while (j <= r) t[k++] = q[j++];
|
||
// 抄回来
|
||
for (i = l, j = 0; i <= r; i++, j++) q[i] = t[j];
|
||
}
|
||
|
||
int main() {
|
||
while (cin >> n, n) {
|
||
for (int i = 1; i <= n; i++) cin >> q[i];
|
||
ans = 0;
|
||
merge_sort(q, 1, n);
|
||
printf("%lld\n", ans);
|
||
}
|
||
return 0;
|
||
}
|