LC2552 AC

class Solution {
    using ll = long long;
    using vl = vector<ll>;
    using vvl = vector<vector<ll>>;
public:
    long long countQuadruplets(vector<int>& ns) {
        ll ret = 0;
        int n = ns.size();
        vvl ij(n + 1, vl(n + 1));
        vvl kl(n + 1, vl(n + 1));
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < i; ++j) {
                if (ns[j] < ns[i]) ij[i][ns[j]]++;
            }
            /*
            ll sum = 0;
            for (int j = 0; j <= n; ++j) sum += ij[i][j];
            for (int j = n; j >= 0; --j) {
                ll old = ij[i][j];
                ij[i][j] += sum - old;
                sum -= old;
            }*/
            for (int j = 1; j <= n; ++j) ij[i][j] += ij[i][j-1];
        }
        for (int k = n - 1; k >= 0; --k) {
            int val = 0;
            for (int l = n - 1; l > k; --l) {
                if (ns[k] < ns[l]) ++val;
                kl[k][l] = val;
            }
        }
        for (int k = 0; k + 1 < n; ++k)
            for (int j = 1; j < k; ++j)
                if (ns[k] < ns[j]) {
                    // printf("k:%d j:%d, ij:%lld kl:%lld\n", k, j, ij[j][k-1], kl[j][k]);
                    ret += ij[j][ns[k]-1] * kl[j][k];
                }
        return ret;
    }
};