111
2025-10-08 18:07:00
发布于：北京
39阅读
0回复
0点赞
#include <bits/stdc++.h>
using namespace std;
struct node {
int x, idx;
} s[100005];
bool cmp(node a, node b) {
if (a.x != b.x) {
return a.x < b.x;
}
return a.idx > b.idx;
}
int n;
int c[100005];
int l[100005];//左边有多少个数比他小
int r[100005];//右边有多少个数比他大
int lowbit(int x) {
return x & -x;
}
void update(int x) {
while (x <= n) {
c[x]++;
x += lowbit(x);
}
}
int sum(int x) {
int ans = 0;
while (x) {
ans += c[x];
x -= lowbit(x);
}
return ans;
}
int main() {
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> s[i].x;
s[i].idx = i;
}
sort(s + 1, s + n + 1, cmp);
for (int i = 1; i <= n; i++) {
//cnt 数组中 [1,s[i]-1] 的和
l[i] = sum(s[i].idx - 1);
//cnt[s[i]]++
update(s[i].idx);
}
memset(c, 0, sizeof(c));
for (int i = n; i >= 1; i--) {
//遍历过了 n-i 个数 - 小于等于 s[i] 的数的个数
r[i] = n - i - sum(s[i].idx);
update(s[i].idx);
}
long long cnt = 0;
for (int i = 1; i <= n; i++) {
cnt = cnt + l[i] * r[i];
}
cout << cnt;
return 0;
}
有帮助，赞一个