1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
| #include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn = 1000010;
int bit[maxn], n;
int a[maxn], r[maxn];
bool cmp(int i,int j) {
return a[i] < a[j];
}
int sum(int i) {
int s=0;
while(i > 0) {
s += bit[i];
i -= i & -i;
}
return s;
}
void add(int i, int x) {
while(i <= n) {
bit[i] += x;
i += i & -i;
}
return;
}
int main(){
while(~scanf("%d", &n) && n) {
memset(bit, 0, sizeof bit);
long long ans = 0;
for(int i = 0;i < n; ++i) {
scanf("%d", &a[i]);
r[i] = i;
}
sort(r, r + n, cmp);
for(int i = 0; i < n; ++i) {
a[r[i]] = i + 1;
}
for(int i = 0; i < n; ++i) {
ans += i - sum(a[i]);
add(a[i], 1);
}
printf("%lld\n", ans);
}
return 0;
}
|