树状数组统计一个数前面有几个数比它小，有几个数比它大

很重要的算法，蓝桥杯遇到n次了

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m;
int a[1000010],c[1000010],b[1000010];
int lowbit(int x)
{
	return x&(-x);
}
int sum(int x)//前缀和 
{
	int res=0;
	while(x>0)
	{
		res+=c[x];
		x-=lowbit(x);
	}
	return res;
}
void add(int x,int k)
{
	while(x<=m)
	{
		c[x]+=k;
		x+=lowbit(x);
	}
}
signed main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		scanf("%lld",&a[i]);
		a[i]++;
		m=max(m,a[i]);
	}
	for(int i=1;i<=n;i++)
	{
		b[i]+=sum(m)-sum(a[i]);
		add(a[i],1); 
	}
	memset(c,0,sizeof(c));
	for(int i=n;i>=1;i--)
	{
		b[i]+=sum(a[i]-1);
		add(a[i],1);
	}
	int ans=0;
	for(int i=1;i<=n;i++)
	{
		ans+=b[i]*(b[i]+1)/2;
	}
	cout<<ans;
	return 0;
}