c++ 给定一个序列 (a_1, a_2, ..., a_n), 定义序列中的一个递增三元组是指三个下标 i, j, k 对应的三个元素 a_i, a_j, a_k，这三个元素满足 a_i < a_j < a_k。 　　例如序列 (1, 1, 4, 3, 2, 4) 有以下 4 个递增三元组： 　　1. 下标 1, 4, 6 对应的 1, 3, 4； 　　2. 下标 1, 5, 6 对应的 1, 2, 4； 　　3. 下标 2, 4, 6 对应的 1, 3, 4； 　　4. 下标 2, 5, 6 对应的 1, 2, 4。 　　注意，可能有下标不同但对应数值相同的三元组，他们应当算成不同的三元组。 　　给定序列，请问序列中一共有多少个不同的递增三元组。 输入格式 　　输入第一行包含一个整数 n，表示序列的长度。 　　第二行包含 n 个整数 a_1, a_2, ..., a_n，表示给定的序列。 输出格式 　　输出一行，包含一个整数，表示序列中的递增三元组数量。请注意答案可能很大，可能超过 32 位二进制整数的范围，建议使用 64 位二进制整数。 样例输入 6 1 1 4 3 2 4

要解决这个问题，我们需要找到序列中所有满足 `a_i < a_j < a_k` 的三元组 `(i, j, k)` 的数量。由于序列的长度可能很大（最多 100,000），我们需要一个高效的算法。 思路 1. 预处理：我们可以通过预处理来记录每个元素左边比它小的元素个数和右边比它大的元素个数。 2. 统计：对于每个元素 `a[j]`，我们计算左边比它小的元素个数 `left[j]` 和右边比它大的元素个数 `right[j]`。然后，递增三元组的数量就是 `left[j] * right[j]` 的总和。 代码实现 ```cpp #include <iostream> #include <vector> #include <algorithm> using namespace std; int main() { int n; cin >> n; vector<int> a(n); for (int i = 0; i < n; ++i) { cin >> a[i]; } vector<int> left(n, 0); // 记录左边比a[i]小的元素个数 vector<int> right(n, 0); // 记录右边比a[i]大的元素个数 // 计算left数组 for (int i = 1; i < n; ++i) { for (int j = 0; j < i; ++j) { if (a[j] < a[i]) { left[i]++; } } } // 计算right数组 for (int i = 0; i < n - 1; ++i) { for (int j = i + 1; j < n; ++j) { if (a[j] > a[i]) { right[i]++; } } } // 计算递增三元组的总数 long long result = 0; for (int i = 0; i < n; ++i) { result += (long long)left[i] * right[i]; } cout << result << endl; return 0; } ``` 代码解释 1. 输入处理：读取序列的长度 `n` 和序列 `a`。 2. 预处理： - `left[i]` 表示在 `a[i]` 左边比它小的元素个数。 - `right[i]` 表示在 `a[i]` 右边比它大的元素个数。 3. 统计递增三元组：对于每个元素 `a[i]`，递增三元组的数量是 `left[i] * right[i]`。 4. 输出结果：输出递增三元组的总数。 优化 上述代码的时间复杂度是 `O(n^2)`，对于 `n = 100,000` 来说，可能会超时。我们可以通过使用更高效的数据结构（如树状数组或线段树）来优化 `left` 和 `right` 的计算，将时间复杂度降低到 `O(n log n)`。 注意事项 1. 数据范围：由于结果可能很大，使用 `long long` 类型来存储结果。 2. 边界条件：当 `n < 3` 时，直接输出 0，因为没有足够元素形成三元组。 3. 重复元素：题目中允许下标不同但数值相同的三元组，因此不需要去重。 通过这种方法，我们可以高效地计算出序列中递增三元组的数量。 [2025-02-25 18:35:56 | AI写代码神器 | 742点数解答]