$a$ $c$ 上升， $b$ $d$ 下降， 于是可以枚举 $a$ $c$, 对于$b$ 和 $d$ 就很好构造出来了， 每一个位于 $a$ ~ $c$ 之间的 $b$ 都可以和 $c$ 之后比 $a[b]$ 小的数 构成一组 $abcd$。有多少个比 $b$ 小的就可以构成多少组。于是可以预处理一个数组， $s(i, j)$

• $s(i, j)$ 的含义是在下标 $j$ 后面比 $a[i]$ 小的元素的个数

于是在枚举 $ac$ 之后， 只需要累加 $s(k, c + 1), a < k < c $

显然， $n^{3}$ 复杂度接受不了，怎么优化?

• 然后发现最后一层 是求 $a + 1$ ~ $c - 1$ 之间的和，于是可以用前缀和优化， 降到 $n^{2}$, 可以过掉

AC代码

#include <cstring>
#include <iostream>
#include <algorithm>

#define x first
#define y second

using namespace std;

typedef long long ll;
typedef pair<int, int> PII;

const int N = 5010;

int n;
int a[N];
int s[N][N];

template <typename T = int> inline T read()
{
    T x = 0; bool f = false; char ch = getchar();
    while (ch < 48 || ch > 57) {f |= (ch == 45); ch = getchar();}
    while (ch > 47 && ch < 58) x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();
    return f ? ~x + 1 : x;
}

void solve()
{

    n = read();
    for (int i = 1; i <= n; i ++ ) s[i][n + 1] = 0;
    for (int i = 1; i <= n; i ++ ) a[i] = read();

    for (int i = 1; i <= n; i ++ )
        for (int j = n; j > i; j -- )
            s[i][j] = s[i][j + 1] + (a[j] < a[i]);

    for (int i = 1; i <= n; i ++ )
        for (int j = i + 1; j <= n; j ++ )
            s[i][j] = s[i - 1][j] + s[i][j];

    ll res = 0;
    for (int i = 1; i <= n; i ++ )
        for (int j = i + 2; j < n; j ++ )
            if (a[i] < a[j]) res += s[j - 1][j + 1] - s[i][j + 1];

    printf("%lld\n", res);

}

int main()
{
    int T = read();

    while (T -- ) solve();

    return 0;
}