title
给你一个长度为 n 下标从 0 开始的整数数组 nums ，它包含 1 到 n 的所有数字，请你返回上升四元组的数目。
如果一个四元组 (i, j, k, l) 满足以下条件，我们称它是上升的：
0 <= i < j < k < l < n且nums[i] < nums[k] < nums[j] < nums[l]。
示例 1：
输入：nums = [1,3,2,4,5]
输出：2
解释：
- 当 i = 0 ，j = 1 ，k = 2 且 l = 3 时，有 nums[i] < nums[k] < nums[j] < nums[l] 。
- 当 i = 0 ，j = 1 ，k = 2 且 l = 4 时，有 nums[i] < nums[k] < nums[j] < nums[l] 。
没有其他的四元组，所以我们返回 2 。
示例 2：
输入：nums = [1,2,3,4]
输出：0
解释：只存在一个四元组 i = 0 ，j = 1 ，k = 2 ，l = 3 ，但是 nums[j] < nums[k] ，所以我们返回 0 。
提示：
4 <= nums.length <= 40001 <= nums[i] <= nums.lengthnums中所有数字 互不相同 ，nums是一个排列。
solution
统计四元组。
枚举中间的两个数。O(n2)
需要预处理简化时间复杂度。
class Solution:
def countQuadruplets(self, nums: List[int]) -> int:
n = len(nums)
# i,j,k,l. i<k<j<l
# index小于j的值小于nums[k]的数量
cnt_less_k = [[0 for _ in range(n + 1)] for _ in range(n + 1)]
for k in range(n):
cnt = 0
for i in range(k):
cnt_less_k[k][i] = cnt
if nums[i] < nums[k]:
cnt += 1
# print(cnt_less_k)
cnt_greater_j = [[0 for _ in range(n + 1)] for _ in range(n + 1)]
for j in range(n - 1, -1, -1):
cnt = 0
i = n - 1
while i > j:
cnt_greater_j[j][i] = cnt
if nums[i] > nums[j]:
cnt += 1
i -= 1
ans = 0
for j in range(n):
for k in range(j + 1, n):
if nums[j] > nums[k]:
ans += cnt_less_k[k][j] * cnt_greater_j[j][k]
return ans