c++描述 给定长度为 N 的两个整数序列 L 和 R，以及一个整数 M。 寻找满足以下两个条件的整数对 (l,r): 1<=l<=r<=M 对于每一个1<=i<=N,区间[l,r]不完全包含区间[L i​,R i​]; 约束条件 1<=N,M<=2e5 1<=L i​<=R i​<=M 输入描述 第一行输入两个整数，分别表示N和M 接下来N行，每行输入两个整数，分别是L i​和R i​; 输出描述 打印满足条件的整数对的数量。 用例输入 1 2 4 1 2 3 4 用例输出 1 5 用例输入 2 6 5 1 1 2 2 3 3 4 4 5 5 1 5 用例输出 2 0 用例输入 3 6 20 8 12 14 20 11 13 5 19 4 11 1 6 用例输出 3 102

为了解决这个问题，我们可以利用差分数组来记录每个区间的覆盖情况，然后统计满足条件的整数对数量。具体思路如下： 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)，可以高效处理输入规模。 [2025-04-23 17:36:27 | AI问答 | 1197点数解答]