/
F.cpp
50 lines (41 loc) · 836 Bytes
/
F.cpp
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<iostream>
#include<queue>
#include<algorithm>
using namespace std;
pair<int, int> arr[100001];
int idx[100001];
long long tree[100001];
int n;
inline long long get(int i) {
long long ans = 0;
for (; i; i -= i & -i) {
ans += tree[i];
}
return ans;
}
inline void up(int i) {
for (; i <= n; i += i & -i) {
++tree[i];
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cin >> n;
for (int i = 1; i <= n; ++i) {
cin >> arr[i].first, arr[i].second = i;
}
sort(arr + 1, arr + 1 + n, greater<pair<int, int>>());
for (int i = 1; i <= n; ++i) {
idx[arr[i].second] = i;
}
long long ans = 0;
long long temp;
for (int i = 1; i <= n; ++i) {
temp = get(idx[i]);
ans += temp * (n - i - idx[i] + temp + 1);
up(idx[i]);
}
cout << ans;
}