优化代码解决超时问题：计算所有 f(l, r) 的和

### 问题分析 原代码的时间复杂度是$O(n^3)$，因为有两层循环来枚举区间$[l, r]$，在每个区间内还需要一层循环来计算$f(l, r)$，当$n$较大时就会超时。可以通过优化$f(l, r)$的计算来降低时间复杂度。 ### 优化思路 可以先计算数组$a$和$b$对应元素乘积的前缀和，这样计算$f(l, r)$时就可以在$O(1)$时间内完成，整体时间复杂度降为$O(n^2)$。 ### 修改后的代码 ```cpp #include <iostream> #include <vector> #include <algorithm> const int MOD = 998244353; // 计算所有 f(l, r) 的和 long long calculateSum(const std::vector<int>& a, const std::vector<int>& b) { int n = a.size(); // 计算前缀和数组 std::vector<long long> prefixSum(n + 1, 0); for (int i = 0; i < n; ++i) { prefixSum[i + 1] = (prefixSum[i] + (long long)a[i] * b[i]) % MOD; } long long sum = 0; for (int l = 0; l < n; ++l) { for (int r = l; r < n; ++r) { // 利用前缀和计算 f(l, r) long long cur = (prefixSum[r + 1] - prefixSum[l] + MOD) % MOD; sum = (sum + cur) % MOD; } } return sum; } int main() { int n; std::cin >> n; std::vector<int> a(n), b(n); for (int i = 0; i < n; ++i) { std::cin >> a[i]; } for (int i = 0; i < n; ++i) { std::cin >> b[i]; } // 对 a 数组从小到大排序 std::sort(a.begin(), a.end()); // 对 b 数组从大到小排序 std::sort(b.begin(), b.end(), std::greater<int>()); long long minSum = calculateSum(a, b); std::cout << minSum << std::endl; return 0; } ``` ### 代码解释 1. **前缀和数组**：`prefixSum` 数组用于存储数组$a$和$b$对应元素乘积的前缀和，这样在计算$f(l, r)$时可以通过$prefixSum[r + 1] - prefixSum[l]$在$O(1)$时间内完成。 2. **计算所有$f(l, r)$的和**：通过两层循环枚举所有的区间$[l, r]$，利用前缀和计算每个区间的$f(l, r)$，并累加到总和中。 ### 复杂度分析 - **时间复杂度**：$O(n^2)$，主要是两层循环枚举区间$[l, r]$。 - **空间复杂度**：$O(n)$，主要是前缀和数组的空间开销。 ######[AI问答 | 767点数解答 | 2026-05-10 16:17:49]