C++14(g++5.4) 解法, 执行用时: 46ms, 内存消耗: 3984K, 提交时间: 2020-09-13 19:51:29

#include<bits/stdc++.h>
using namespace std;
const int maxn=2e5+10;
int tr[2][maxn];
void add(int x,int v,int p)
{
	while(x<maxn){
		tr[p][x]+=v;
		x+=x&-x;
	}
}
int query(int x,int p)
{
	int rec=0;
	while(x){
		rec+=tr[p][x];
		x-=x&-x;
	}
	return rec;
}
int a[maxn];
int main()
{
	int n;scanf("%d",&n);
	long long ans=0,ans2=0;
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);add(a[i],1,0);
	}
	for(int i=n;i>=1;i--){
		add(a[i],-1,0);int t1=query(a[i],0),t2=query(a[i],1);
		//cout<<t1<<" "<<t2<<endl;
		ans+=1LL*t1*t2;
		ans2+=1LL*(i-1-t1)*(n-i-t2);
		add(a[i],1,1);
	}
	cout<<ans2<<" "<<ans<<endl;
}

C++(clang++ 11.0.1) 解法, 执行用时: 45ms, 内存消耗: 2684K, 提交时间: 2023-06-26 16:23:21

#include<bits/stdc++.h>
using namespace std;

int n;
int a[200009];

typedef long long ll;
ll tr[200009];
ll lowbit(int x){ return x&-x; }
void add(int u,ll num){ for(int i=u;i<=n;i+=lowbit(i)) tr[i]+=num; }
ll getsum(int u)
{
	ll sum=0;
	for(int i=u;i>0;i-=lowbit(i)) sum+=tr[i];
	return sum;
}

int main()
{
	scanf("%d",&n);
	ll ans1=0,ans2=0;
	for(int i = 1;i <= n;i++)
	{
		scanf("%d",&a[i]);
		ll cnt=getsum(a[i]-1);
		ans1+=cnt*(a[i]-1-cnt);
		
		cnt=i-1-cnt;
		ans2+=cnt*(n-a[i]-cnt);
		
		add(a[i],1);
	}
	
	printf("%lld %lld",ans2,ans1);
	return 0;
}