思路
t[r]数组存的是数字[1, r]出现的次数;
从左到右统计每个i左边比a[i]大的数和比a[i]小的数。
代码
#include<iostream>
#include<cstring>
using namespace std;
const int N = 200010;
int a[N];
int t[N];
int n;
int lowbit(int x)
{
return x & -x;
}
void add(int x, int c)
{
for (int i = x; i <= n; i += lowbit(i)) t[i] += c;
}
int sum(int x)
{
int res = 0;
for (int i = x; i; i -= lowbit(i)) res += t[i];
return res;
}
int main()
{
cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i];
int lower[N], grter[N];
for (int i = 1; i <= n; i++)
{
int y = a[i];
lower[i] = sum(y - 1);
grter[i] = sum(n) - sum(y);
add(y, 1);
}
memset(t, 0, sizeof t);
long long res1 = 0, res2 = 0;
for (int i = n; i >= 1; i--)
{
int y = a[i];
res1 += grter[i] * (long long)(sum(n) - sum(y));
res2 += lower[i] * (long long)sum(y - 1);
add(y, 1);
}
cout << res1 << ' ' << res2;
return 0;
}