题目描述：
给你一个长度为 n 下标从 0 开始的整数数组 nums ，它包含 1 到 n 的所有数字，请你返回上升四元组的数目。
如果一个四元组 (i, j, k, l) 满足以下条件，我们称它是上升的：
0 <= i < j < k < l < n 且nums[i] < nums[k] < nums[j] < nums[l] 。
数据范围：
$4\le nums.len \le 4000$
题解：
数据范围暗示是一个 $n^2$ 的做法，需要枚举两个位置。
可以考虑枚举中间的 $j,k$ ，那么问题就转化为求 $j$ 左侧比 $nums[k]$ 小的元素个数，求 $k$ 右侧比 $nums[j]$ 大的元素个数，然后两个相乘。
可以使用 $great[i][x]$ 表示下标 $j > i$ ，且 $nums[j] > x$ 的元素个数，那么可以递推 $great[i][x] = great[i + 1][x] + (nums[i] > x)$ 。可以从后面一个递推过来，最后加上当前的贡献；同理 $less[i][x] = less[i - 1][x] + (nums[i] < x)$ 。
最后的答案就是枚举所有的 $j,k$ 然后计算 $great[k][nums[j]] \times less[j][nums[k]]$ 。
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
| auto optimize_cpp_stdio = []()
{
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
return 0;
}();
class Solution
{
public:
const static int maxn = 1e5 + 10;
const static int maxm = 1e5 + 10;
const int INF = 0x3f3f3f3f;
long long countQuadruplets(vector<int> &nums)
{
int n = nums.size();
vector<vector<int>> great(n + 2, vector<int>(n + 2));
vector<vector<int>> less(n + 2, vector<int>(n + 2));
for (int i = n; i >= 1; --i)
{
for (int j = 1; j <= n; ++j)
{
great[i][j] = great[i + 1][j] + (nums[i - 1] > j);
}
}
for (int i = 1; i <= n; ++i)
{
for (int j = 1; j <= n; ++j)
{
less[i][j] = less[i - 1][j] + (nums[i - 1] < j);
}
}
long long ans = 0;
for (int j = 1; j < n - 2; ++j)
{
for (int k = j + 1; k < n - 1; ++k)
{
if (nums[j] > nums[k])
ans += 1ll * great[k + 1][nums[j]] * less[j + 1][nums[k]];
}
}
return ans;
}
};
|