题意
思路
- 树状数组,我们通过枚举顺序进行插入,然后对树状数组进行区间查询可以了。
代码
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 200005;
int n, a[N], c[N], great[N], lower[N];
int lowbit(int x)
{
return x & -x;
}
void insert(int x, int y)
{
while (x <= n)
{
c[x] += y;
x += lowbit(x);
}
}
int sum(int x)
{
int all = 0;
while (x > 0)
{
all += c[x];
x -= lowbit(x);
}
return all;
}
int main()
{
scanf("%d", &n);
for (int i = 1; i <= n; i ++) scanf("%d", &a[i]);
for (int i = 1; i <= n; i ++) {
great[i] = sum(n) - sum(a[i]);
lower[i] = sum(a[i] - 1);
insert(a[i], 1);
}
memset(c, 0, sizeof c);
ll res1 = 0, res2 = 0;
for (int i = n; i; i --) {
res1 += 1LL * great[i] * (sum(n) - sum(a[i]));
res2 += 1LL * lower[i] * sum(a[i] - 1);
insert(a[i], 1);
}
printf("%lld %lld\n", res1, res2);
return 0;
}