记录编号	601359	评测结果	AAAAAAAAAA
题目名称	1975.奶牛排序	最终得分	100
用户昵称	xxz	是否通过	通过
代码语言	C++	运行时间	0.322 s
提交时间	2025-06-16 21:04:57	内存使用	6.04 MiB

#include <bits/stdc++.h>
#define ll long long
#define lowbit(x) x&-x
#define akarin 123456
using namespace std;
ll n,maxx = -1,ans,a[akarin], l[akarin], r[akarin],f[akarin];
void add(ll x, ll y) {
	for (; x <= maxx; x += lowbit(x)) f[x] += y;
} 

ll ask(ll x) {
	ll res = 0;
	for (; x; x -= lowbit(x)) res += f[x];
	return res;
}

int main() {
	freopen("cow.in", "r", stdin);freopen("cow.out", "w", stdout);
	cin>>n;
	for (ll i = 1; i <= n; ++i) {
		cin>>a[i];
		maxx = max(maxx, a[i]);
	}
	for (ll i = 1; i <= n; ++i) {
		l[i] = ask(maxx) - ask(a[i]);
		add(a[i], 1);
	}
	memset(f, 0, sizeof f);
	for (ll i = n; i >= 1; --i) {
		r[i] = ask(a[i] - 1);
		add(a[i], 1);
	}
	for (ll i = 1; i <= n; ++i) {
		ans+=(l[i] + r[i]) * a[i];
	}
	printf("%lld",ans);
	return 0;
}