如果是枚举参加比赛的人，，那么枚举起来就非常的复杂了
如果是枚举裁判，，题目会变得简单很多
假如裁判是第i个人，那么参加比赛的肯定分别在i的左边和i的右边
那么我就可以统计[1,i-1]这个区间内有多个人的rank小于等于i,[i+1,n]这个区间内有多少人的rank大于等于i，两者相乘，就是左边小于等于右边大于等于的情况
在考虑[1,i-1]这个区间内有多个人的rank大于i,[i+1,n]这个区间内有多少人的rank小于i，两者相乘，就是左边大于等于右边小于等于的情况
两种情况相加，就是全部情况了
这题突然就转换成了求逆序对了~
#include<map>
#include<set>
#include<cmath>
#include<queue>
#include<cstdio>
#include<string>
#include<vector>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<functional>using namespace std;
typedef long long LL;
typedef pair<int, int> PII;const int MX = 1e5 + 5;
const int INF = 0x3f3f3f3f;int S[MX], A[MX], Max, n;
int LMIN[MX], LMAX[MX], RMIN[MX], RMAX[MX];int sum(int x) {int ret = 0;for(; x; x -= x & -x) {ret += S[x];}return ret;
}int query(int L, int R) {return sum(R) - sum(L - 1);
}void update(int x, int d) {for(; x <= Max; x += x & -x) {S[x] += d;}
}int main() {//freopen("input.txt", "r", stdin);int T;scanf("%d", &T);while(T--) {Max = 0;scanf("%d", &n);for(int i = 1; i <= n; i++) {scanf("%d", &A[i]);Max = max(Max, A[i]);}memset(S, 0, sizeof(S));update(A[1], 1);for(int i = 2; i <= n - 1; i++) {LMIN[i] = query(1, A[i]);LMAX[i] = A[i] + 1 <= Max ? query(A[i] + 1, Max) : 0;update(A[i], 1);}memset(S, 0, sizeof(S));update(A[n], 1);for(int i = n - 1; i >= 2; i--) {RMIN[i] = 1 <= A[i] - 1 ? query(1, A[i] - 1) : 0;RMAX[i] = query(A[i], Max);update(A[i], 1);}LL ans = 0;for(int i = 2; i <= n - 1; i++) {ans += (LL)LMIN[i] * RMAX[i] + (LL)LMAX[i] * RMIN[i];}printf("%I64d\n", ans);}return 0;
}