统计上升四元组

题目

6340. 统计上升四元组

---

给你一个长度为 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 <= 4000
• 1 <= nums[i] <= nums.length
• nums 中所有数字 互不相同 ，nums 是一个排列。

题解

方法一：

思路

没想到开这么大的数组

令l[i][j]为下标小于等于i且值小于等于j的个数， r[i][j]下标大于等于i且值大于等于j的个数。

显然如果j！=nums[i]，那么l[i][j]相当于下标严格小于i且值严格小于j的个数，r[i][j]相当于下标严格大于i且值严格大于j的个数。

以numns[i]和nums[j]作为中间两个元素的四元组个数为l[i][nums[j]] * r[j][nums[i]]

答案为$\sum \limits_{i=0}^{n-1} \sum \limits_{j=i+1}^{n-1} l[i][nums[j]] * r[j][nums[i]]$

总时间复杂度$O(n^2)$

代码

#define N 4001
int l[N][N], r[N][N]; //l[i][j] 下标<=i且值<=j的个数， r[i][j] 下标>=i且值>=j的个数
class Solution {
public:
    using ll = long long;
    /*
        枚举i和j，i<j，nums[i]>nums[j]
        由于nums[j]!= nums[i]，l[i][nums[j]]是位置小于等于i，值严格小于nums[j]的个数；r[j][nums[i]]是位置大于等于i，值严格大于nums[i]的个数；
        以numns[i]和nums[j]作为中间两个元素的四元组个数为：(l[i][nums[j]]) * (r[j][nums[i]])
    */
    long long countQuadruplets(vector<int>& nums) {
        int n = nums.size();
        memset(l, 0, sizeof(l));
        memset(r, 0, sizeof(r));
        for (int i=0; i<n; i++) {
            l[i][nums[i]]++;
            r[i][nums[i]]++;
        }
        for (int i=0; i<n; i++) {
            for (int j=1; j<=n; j++) {
                if (i-1>=0) l[i][j] += l[i-1][j];
                if (j-1>=1) l[i][j] += l[i][j-1];
                if (i-1>=0 && j-1>=1) l[i][j] -= l[i-1][j-1];
            }
        }
        for (int i=n-1; i>=0; i--) {
            for (int j=n; j>=1; j--) {
                if (i+1<n) r[i][j] += r[i+1][j];
                if (j+1<=n) r[i][j] += r[i][j+1];
                if (i+1<n && j+1<=n) r[i][j] -= r[i+1][j+1];
            }
        }
        ll ans = 0;
        for (int i=0; i<n; i++) {
            for (int j=i+1; j<n; j++) {
                if (nums[i]>nums[j]) {
                    ans += l[i][nums[j]]*r[j][nums[i]];
                }
            }
        }
        return ans;
    }
};