树状数组的运用
具体就是枚举每个裁判，左边比裁判小的个数乘以右边比裁判大的个数，以及左边比裁判大的个数乘以右边小的个数，总和即为结果
/*
ID: sdj22251
PROG: calfflac
LANG: C++
*/
#include <iostream>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <cmath>
#include <ctime>
#define MAX 100000000
#define LOCA
#define PI acos(-1.0)
using namespace std;
int a[100001], b[100001], data[100001];
int lowbit(int x) //返回二进制下最右边的1，用于树状数组存储和查询时的结构
{return x & (-x);
}
void calculate1(int x) //由于所有数据是独一无二，并且在100000以内，所以将所有数据处理，用树状数组a预存,所有能被x影响到的数组均改变
{for(; x < 100001; x += lowbit(x))a[x]++;
}
void calculate2(int x) //枚举每个裁判时，一个一个的存入树状数组b,方便对当前左侧选手的查询
{for(; x < 100001; x += lowbit(x))b[x]++;
}
__int64 sum1(int x) //计算所有数据中比裁判小的个数，从而推出比裁判大的个数
{__int64 sum = 0;for(; x > 0; x -= lowbit(x))sum += a[x];return sum;
}
__int64 sum2(int x) //计算裁判左侧比裁判小的个数，就能推出右侧，从而推出大的个数
{__int64 sum = 0;for(; x > 0; x -= lowbit(x))sum += b[x];return sum;
}
int main()
{
#ifdef LOCALfreopen("ride.in","r",stdin);freopen("ride.out","w",stdout);
#endifint n, i, t;scanf("%d", &t);while(t--){scanf("%d", &n);memset(a, 0, sizeof(a));memset(b, 0, sizeof(b));for(i = 1; i <= n; i++){scanf("%d", &data[i]);calculate1(data[i]);}__int64 ans = 0;calculate2(data[1]);for(i = 2; i < n; i++){calculate2(data[i]);__int64 allsmall = sum1(data[i]);__int64 nowsmall = sum2(data[i]);ans += (nowsmall - 1) * ((n - allsmall) - (i - nowsmall));//左边小的乘以右边大的ans += (i - nowsmall) * (allsmall - nowsmall);//右边小的乘以左边大的}printf("%I64d\n", ans);}return 0;
}