You cannot select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
61 lines
1.4 KiB
C++
61 lines
1.4 KiB
C++
#define _CRT_SECURE_NO_WARNINGS
|
|
#define _SILENCE_CXX17_C_HEADER_DEPRECATION_WARNING
|
|
|
|
#include <bits/stdc++.h>
|
|
|
|
using namespace std;
|
|
const int N = 1000500;
|
|
namespace Solution {
|
|
const int N = 100005;
|
|
|
|
struct Node {
|
|
int x, cnt;
|
|
} a[N], b[N];
|
|
|
|
void merge(int st, int ed) {
|
|
int md = (st + ed) >> 1;
|
|
int i = st, j = md + 1, cnt = st;
|
|
while (i <= md && j <= ed)
|
|
if (a[i].x > a[j].x) {
|
|
a[j].cnt += md + 1 - i;
|
|
b[cnt++] = a[j++];
|
|
} else {
|
|
a[i].cnt += j - 1 - md;
|
|
b[cnt++] = a[i++];
|
|
}
|
|
while (j <= ed)b[cnt++] = a[j++];
|
|
while (i <= md) {
|
|
a[i].cnt += ed - md;
|
|
b[cnt++] = a[i++];
|
|
}
|
|
for (i = st; i <= ed; i++)a[i] = b[i];
|
|
}
|
|
|
|
void merge_sort(int st, int ed) {
|
|
if (st == ed) return;
|
|
int md = (st + ed) >> 1;
|
|
merge_sort(st, md);
|
|
merge_sort(md + 1, ed);
|
|
merge(st, ed);
|
|
}
|
|
|
|
|
|
void solve() {
|
|
memset(a, 0, sizeof(a));
|
|
int n;
|
|
scanf("%d", &n);
|
|
for (int i = 0; i < n; i++)
|
|
scanf("%d", &a[i].x);
|
|
long long ans = 0;
|
|
merge_sort(0, n - 1);
|
|
for (int i = 0; i < n; i++)
|
|
ans += (a[i].cnt + 1) * a[i].cnt / 2;
|
|
printf("%lld", ans);
|
|
}
|
|
}
|
|
|
|
int main() {
|
|
Solution::solve();
|
|
return 0;
|
|
}
|