C++ 求解满足特定条件整数对数量：从 O(M^2) 到 O(N + M) 的优化

为了解决这个问题，我们可以利用差分数组来记录每个区间的覆盖情况，然后统计满足条件的整数对数量。具体思路如下： 1. 初始化一个差分数组 `diff`，长度为 `M+1`，用于记录每个位置的覆盖增减情况。 2. 遍历每个区间 `[L[i], R[i]]`，在差分数组的 `L[i]` 位置增加 1，在 `R[i]+1` 位置减少 1。 3. 遍历差分数组，计算前缀和得到每个位置的覆盖区间数量。 4. 统计满足条件的整数对 `(l, r)`，即对于每个位置 `r`，找到所有满足条件的 `l`，使得在 `[l, r]` 区间内没有任何一个完整的给定区间。 下面是具体的 C++ 实现代码： ```cpp #include <iostream> #include <vector> using namespace std; int main() { int N, M; cin >> N >> M; vector<int> L(N), R(N); for (int i = 0; i < N; ++i) { cin >> L[i] >> R[i]; } vector<int> diff(M + 1, 0); // 使用差分数组记录区间覆盖情况 for (int i = 0; i < N; ++i) { diff[L[i]]++; if (R[i] + 1 <= M) { diff[R[i] + 1]--; } } // 计算前缀和得到每个位置的覆盖区间数量 vector<int> prefixSum(M + 1, 0); prefixSum[0] = diff[0]; for (int i = 1; i <= M; ++i) { prefixSum[i] = prefixSum[i - 1] + diff[i]; } // 统计满足条件的整数对数量 long long count = 0; for (int r = 1; r <= M; ++r) { for (int l = 1; l <= r; ++l) { if (prefixSum[r] - (l > 0 ? prefixSum[l - 1] : 0) == 0) { count++; } } } cout << count << endl; return 0; } ``` 上述代码的时间复杂度为 O(M^2)，在 M 最大为 200,000 的情况下会超时。我们需要优化这个部分。 注意到，对于每个固定的 `r`，我们需要找到所有满足条件的 `l`，即 `prefixSum[r] - prefixSum[l-1] == 0`。这可以通过预处理 `prefixSum` 的前缀和数组（或者称为“和的和”数组）来加速查询，但在这个特定问题中，我们可以利用单调栈进一步优化。 为了简化实现并保持代码可读性，这里提供一个利用“和为零的区间数量”的另一种思路，即通过遍历 `l` 来累积和并判断，同时使用一个哈希表记录累积和出现的次数来加速查询。由于题目只需要统计数量，不需要具体区间，这种方法更为直观且易于实现。 下面是优化后的代码： ```cpp #include <iostream> #include <vector> #include <unordered_map> using namespace std; int main() { int N, M; cin >> N >> M; vector<int> L(N), R(N); for (int i = 0; i < N; ++i) { cin >> L[i] >> R[i]; } vector<int> diff(M + 2, 0); // +2 to handle edge cases smoothly unordered_map<int, int> cumSumCount; cumSumCount[0] = 1; // Initial state, no intervals covered means sum is zero once int cumSum = 0; // Use diff array to mark intervals for (int i = 0; i < N; ++i) { diff[L[i]]++; diff[R[i] + 1]--; } // Compute prefix sums using diff array for (int i = 1; i <= M + 1; ++i) { cumSum += diff[i]; cumSumCount[cumSum]++; } // Count valid (l, r) pairs long long count = 0; for (int r = 1; r <= M; ++r) { count += cumSumCount[0]; // All valid l such that sum[r] - sum[l-1] == 0 if (cumSumCount.find(cumSum - 1) != cumSumCount.end()) { count -= cumSumCount[cumSum - 1]; // Exclude intervals fully contained } } cout << count << endl; return 0; } ``` 这个优化后的代码时间复杂度为 O(N + M)，可以高效处理输入规模。 ######[AI问答 | 1197点数解答 | 2025-04-23 17:36:27]