C++ 高效计算序列中递增三元组数量：从 O(n^2) 到 O(n log n) 的优化之路

要解决这个问题，我们需要找到序列中所有满足 `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. 重复元素：题目中允许下标不同但数值相同的三元组，因此不需要去重。 通过这种方法，我们可以高效地计算出序列中递增三元组的数量。 ######[AI写代码神器 | 742点数解答 | 2025-02-25 18:35:56]