题解

求四元组满足下标 (a<b<c<d)，且 (p_a < p_c,\ p_b > p_d)。
总四元组总数 = 全部合法下标四元组数量 - 不满足条件的四元组数量。公式推导
先算所有满足 (a<b<c<d) 的四元组总数：(C(n,4))
不合法分为两类：

(S_1)：(a<b<c<d,\ p_a \ge p_c)（不管 (p_b,p_d)）
(S_2)：(a<b<c<d,\ p_b \le p_d)（不管 (p_a,p_c)）

两者交集 (S_{12})：(a<b<c<d,\ p_a\ge p_c \land p_b \le p_d)
根据容斥：

(\text{答案} = C(n,4) - S_1 - S_2 + S_{12})分别求三块1. (C(n,4))组合数公式：(C(n,4)=\dfrac{n(n-1)(n-2)(n-3)}{24})2. 求 (S_1)：(a<b<c<d,\ p_a \ge p_c)只关心 (a<c)，中间夹任意 (b(a<b<c))，后面任意 (d>c)。
对每一对 ((a,c),a<c)：
若 (p_a \ge p_c)，贡献数量 = b 的可选数 × d 的可选数
(cnt_b = c-a-1)，(cnt_d = n-c)
(S_1 = \sum_{a<c,\ p_a\ge p_c} (c-a-1) \cdot (n-c))3. 求 (S_2)：(a<b<c<d,\ p_b \le p_d)只关心 (b<d)，前面任意 (a<b)，中间任意 (c(b<c<d))。
对每一对 ((b,d),b<d)：
若 (p_b \le p_d)，贡献 = (cnt_a \cdot cnt_c)
(cnt_a = b-1)，(cnt_c = d-b-1)
(S_2 = \sum_{b<d,\ p_b\le p_d} (b-1)\cdot (d-b-1))4. 求 (S_{12})：(a<b<c<d,\ p_a\ge p_c \land p_b \le p_d)固定中间两个分界点 (b,c)（(b<c)）：
左边选 (a \in [1,b-1])，满足 (p_a \ge p_c)，记数量为 L
右边选 (d \in [c+1,n])，满足 (p_b \le p_d)，记数量为 R
每组 ((b,c)) 贡献 (L\times R)

(S_{12} = \sum_{1\le b<c\le n} L(b,c) \times R(b,c))复杂度分析所有 n 总和 (\le 5000)：
(S_1,S_2)：(O(n^2))
(S_{12})：(O(n^2))
总复杂度 (O(\sum n^2))，(n=5000) 时 (5000^2=25\times106)可是原代码计算 (S_{12}) 时是三层循环：(O(n^3))，当 (n=5000) 时 (5000^3) 直接超时，1s 完全跑不动。
我们把 (S_{12}) 的 (L,R) 用预处理数组降到 (O(n^2))，整体总复杂度 (O(n^2))，总和 (\sum n^2 \le 5000^2=25\times106)，稳过 1s。预处理思路
pre[b][c]：(a<b) 且 (p[a]\ge p[c]) 的数量（原 L）
枚举 c，从小到大扫 b 维护值域计数，(O(n^2)) 预处理。
suf[b][c]：(d>c) 且 (p[b]\le p[d]) 的数量（原 R）
枚举 b，从后往前扫 c 维护值域计数，(O(n^2)) 预处理。

#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
typedef long long ll;

ll C4(ll n) {
    if (n < 4) return 0;
    return n * (n - 1) * (n - 2) * (n - 3) / 24;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        vector<int> p(n + 1);
        for (int i = 1; i <= n; ++i) cin >> p[i];

        ll total = C4(n);

        // ========== S1 O(n^2) ==========
        ll S1 = 0;
        for (int a = 1; a <= n; ++a) {
            for (int c = a + 1; c <= n; ++c) {
                if (p[a] >= p[c]) {
                    ll b_cnt = c - a - 1;
                    ll d_cnt = n - c;
                    S1 += b_cnt * d_cnt;
                }
            }
        }

        // ========== S2 O(n^2) ==========
        ll S2 = 0;
        for (int b = 1; b <= n; ++b) {
            for (int d = b + 1; d <= n; ++d) {
                if (p[b] <= p[d]) {
                    ll a_cnt = b - 1;
                    ll c_cnt = d - b - 1;
                    S2 += a_cnt * c_cnt;
                }
            }
        }

        // ========== 预处理 pre[b][c] = L(a<b, p[a]>=p[c]) ==========
        vector<vector<ll>> pre(n + 2, vector<ll>(n + 2, 0));
        for (int c = 1; c <= n; ++c) {
            vector<int> cnt(n + 2, 0);
            ll sum_ge = 0;
            for (int b = 1; b <= n; ++b) {
                pre[b][c] = sum_ge;
                // 加入 p[b]，后面b更大时a可以取当前b
                cnt[p[b]]++;
                if (p[b] >= p[c]) sum_ge++;
            }
        }

        // ========== 预处理 suf[b][c] = R(d>c, p[b]<=p[d]) ==========
        vector<vector<ll>> suf(n + 2, vector<ll>(n + 2, 0));
        for (int b = 1; b <= n; ++b) {
            vector<int> cnt(n + 2, 0);
            ll sum_le = 0;
            for (int c = n; c >= 1; --c) {
                suf[b][c] = sum_le;
                // d取c，往后c更小的时候d可以取当前c
                cnt[p[c]]++;
                if (p[b] <= p[c]) sum_le++;
            }
        }

        // ========== S12 O(n^2) ==========
        ll S12 = 0;
        for (int b = 1; b <= n; ++b) {
            for (int c = b + 1; c <= n; ++c) {
                ll L = pre[b][c];
                ll R = suf[b][c];
                S12 += L * R;
            }
        }

        ll ans = total - S1 - S2 + S12;
        cout << ans << '\n';
    }
    return 0;
}

复杂度总结
(S_1,S_2)：(O(n^2))
预处理 pre,suf：(O(n^2))
(S_{12})：(O(n^2))
单组 (n=5000) 总操作量约 7500 万，C++ 1s 可轻松跑完。