题意：
一条大街上住着n个乒乓球爱好者，经常组织比赛切磋技术。每个人都有一个能力值a[i]。
每场比赛需要三个人：两名选手，一名裁判。他们有个奇怪的约定，裁判必须住在两名选手之间，而裁判的能力值也必须在两名选手之间。
问一共能组织多少种比赛。
分析：
考虑第i个人，假设a1到ai-1中有ci个比ai小，那么就有(i-1)-ci个比ai大；
同理，如果ai+1到an中有di个比ai小，那么就有(n-i)-di个比ai大。
i当裁判就有：ci * (n-i-di) + (i-1-ci)*di种比赛。
然后问题就转化为了计算数组c和数组d。这样的话就很容易想到使用树状数组去计算前缀和。
#include<iostream>
#include<string>
#include<algorithm>
#include<cstdlib>
#include<cstdio>
#include<set>
#include<map>
#include<vector>
#include<cstring>
#include<stack>
#include<cmath>
#include<queue>
#include <bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
#define ll long long
#define clc(a,b) memset(a,b,sizeof(a))
inline int lowbit(int x)
{
return x&-x;
}
struct bit
{
int n;
vector<int>C;
void resise(int n)
{
this->n=n;
C.resize(n);
}
void clear()
{
fill(C.begin(),C.end(),);
}
int sum(int x)
{
int ret=;
while(x>)
{
ret+=C[x];
x-=lowbit(x);
}
return ret;
}
void add(int x,int d)
{
while(x<=n)
{
C[x]+=d;
x+=lowbit(x);
}
}
};
const int maxn=+;
int n,a[maxn],c[maxn],d[maxn];
bit f;
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
int maxa=;
for(int i=; i<=n; i++)
{
scanf("%d",&a[i]);
maxa=max(maxa,a[i]);
}
f.resise(maxa);
f.clear();
for(int i=; i<=n; i++)
{
f.add(a[i],);
c[i]=f.sum(a[i]-);
}
f.clear();
for(int i=n; i>=; i--)
{
f.add(a[i],);
d[i]=f.sum(a[i]-);
}
ll ans=;
for(int i=; i<=n; i++)
ans+=(ll)c[i]*(n-i-d[i])+(ll)d[i]*(i-c[i]-);
printf("%lld\n",ans);
}
return ;
}