Readme

2552.Count-Increasing-Quadruplets

从数据规模来看，我们可以尝试n^2的时间复杂度。这意味着我们可以遍历两个变量，然后看其他两个变量能否快速得到。

通过尝试，我们可以试图遍历j和k的位置。一旦确定之后，就意味着我们需要在[1:j-1]里找有多少个小于nums[k]的元素，以及在[k+1:n]里找有多少个大于nums[j]的元素。将两者乘起来，就是类似(x,j,k,x)的组合的数目。

接下来考虑如何求[1:j-1]里找有多少个小于nums[k]的元素。这里我们利用到另一个条件，就是nums是一个permutation，即每个元素的大小不超过n。所以我们考虑将数值的大小作为一个维度。令pre[i][v]表示前i个元素里小于v的元素有多少个。我们就有递归的表达式：

if (nums[i] < v)
  pre[i][v] = pre[i-1][v] + 1;  // 多了一个nums[i]满足小于v
else
  pre[i][v] = pre[i-1][v];  // nums[i]>=v，对于小于v的计数没有影响。

同理，我们可以递归算出post[i][v]表示后i个元素里大于v的元素有多少个。

最后，我们遍历j和k，累加结果

for (int j=1; j<=n; j++)
  for (int k=j+1; k<=n; k++)
    ret += pre[j-1][nums[k]] * post[k+1][nums[j]];