P3361 救生员高效解法：O(N log N) 事件驱动加集合维护

好的，我理解您的问题了。您的代码逻辑是正确的，但是您提到的 **“对每个区间遍历它覆盖的所有离散段”** 这一步在最坏情况下（当区间很长，覆盖很多离散段时）会导致 **O(N²）** 的时间复杂度，从而超时。 核心问题在于： - 每个区间可能覆盖 O(m) 个离散段，m 最多 2N = 200,000。 - 如果每个区间都这样做，总复杂度会变成 O(N * m) ≈ 2e10，无法承受。 我们需要一个 **O(N + m)** 的算法来统计每个区间的独占总长，而不是 O(N * m)。下面我提供一个更高效的思路。 --- ## 🧠 高效思路解析 要高效计算每个区间 `i` 的独占总长，我们不能遍历每个区间再遍历其内部的离散段。相反，我们应该**遍历每个离散段一次**，找出它属于哪个区间（如果 `cover[j] == 1`），然后把这段长度加到那个区间的 `loss` 上。 **关键问题**：如何快速知道 `cover[j] == 1` 的离散段属于哪个区间？ **解决方案**：对于每个离散段 `j`，它所对应的原始时间范围是 `[pos[j], pos[j+1])`。如果这个段只被一个区间覆盖，那么**这个唯一的区间就是 `pos[j]` 这个时间点所属的区间**。 一个时间点可能属于多个区间（因为区间可能有重叠）。我们需要一个机制来追踪“当前离散段 `j` 是由哪个区间‘独有’的”。 下面是两种可行且高效的做法： ### 方法一：利用并查集或指针追踪（推荐，简单实现） 我们可以把每个离散段 `j` 看作一个“槽位”。我们按顺序扫描： 1. **事件预处理**：对于每个区间 `i`，我们记录它覆盖的第一个离散段和最后一个离散段。 2. **扫描离散段**：遍历所有离散段 `j`。维护一个数据结构来记录当前有哪些区间正在覆盖这个段： - 我们可以使用一个 `set` 或 `multiset`（在 C++ 中是 `std::set`）来存储当前正在覆盖该段的区间索引。 - 当进入一个离散段 `j`（即 `cur` 计数发生变化时），我们先更新 `cur`。 - 然后，如果 `cur == 1`，那么这个段就属于 `set` 中的**唯一**那个区间。 - 关键在于如何更新这个 `set`： - 每个区间 `i` 有一个开始时间 `l`（对应离散下标 `l_idx`）和结束时间 `r`（对应离散下标 `r_idx`）。 - 我们可以为每个区间创建一个 **“进入”事件** 和 **“离开”事件**： - 在 `l_idx` 处：向 `set` 中添加区间 `i`。 - 在 `r_idx` 处：从 `set` 中移除区间 `i`。 - 这样，当我们扫描到离散段 `j` 时，`set` 中存储的就是所有覆盖该段的区间。 ### 方法二：使用差分数组 + 区间分配（稍复杂，但常数小） 此方法需要额外数组，容易出错，不推荐。 --- ## ✅ 改进后的 C++ 代码（O(N log N)） ```cpp #include <bits/stdc++.h> using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin >> n; vector<pair<int, int>> segs(n); vector<int> pos; for (int i = 0; i < n; i++) { cin >> segs[i].first >> segs[i].second; pos.push_back(segs[i].first); pos.push_back(segs[i].second); } // 1. 离散化 sort(pos.begin(), pos.end()); pos.erase(unique(pos.begin(), pos.end()), pos.end()); int m = pos.size(); // 2. 创建所有事件 vector<vector<pair<int, int>>> events(m); // events[i] 存储离散点 i 处的事件 (type, id) // type: 1 = 进入, -1 = 离开 for (int i = 0; i < n; i++) { int l = lower_bound(pos.begin(), pos.end(), segs[i].first) - pos.begin(); int r = lower_bound(pos.begin(), pos.end(), segs[i].second) - pos.begin(); events[l].push_back({1, i}); // 进入区间 i events[r].push_back({-1, i}); // 离开区间 i（注意是左闭右开） } // 3. 第一次扫描 + 事件处理：计算总覆盖 & 每个离散段的 cover 值为 1 时属于哪个区间 vector<long long> loss(n, 0); long long total = 0; set<int> active_intervals; // 当前正在覆盖该段的区间索引集合 int cur = 0; for (int i = 0; i < m - 1; i++) { // 处理当前位置 i 的所有事件（在进入离散段 [i, i+1) 之前处理） for (auto &ev : events[i]) { if (ev.first == 1) { // 进入 active_intervals.insert(ev.second); cur++; } else { // 离开 active_intervals.erase(ev.second); cur--; } } // 现在 cur 和 active_intervals 代表了离散段 [pos[i], pos[i+1]) 的状态 if (cur > 0) { long long seg_len = pos[i + 1] - pos[i]; total += seg_len; if (cur == 1) { // 这个段只被一个区间覆盖，所以这段长度就是那个区间的独占总长 int unique_interval = *active_intervals.begin(); loss[unique_interval] += seg_len; } } } // 4. 找出最小损失 long long min_loss = LLONG_MAX; for (int i = 0; i < n; i++) { min_loss = min(min_loss, loss[i]); } long long ans = total - min_loss; cout << ans << '\n'; return 0; } ``` --- ## 🔍 关键改动说明 1. **事件驱动**：不再遍历每个区间的所有离散段，而是为每个区间创建两个事件（进入/离开）。事件在离散点上进行处理。 2. **集合维护**：使用 `std::set<int>` 来维护当前活跃的区间索引集合。当 `cur == 1` 时，`set` 中的唯一元素就是独占总长的贡献者。 3. **扫描顺序**：我们在进入离散段 `[i, i+1)` **之前**处理所有事件。这确保了 `cur` 和 `active_intervals` 正确反映了该段的状态。 --- ## ⏱ 复杂度分析 - **时间复杂度**： - 离散化：`O(N log N)` - 创建事件：`O(N log N)`（因为使用了 `lower_bound`） - 扫描离散段 + 事件处理：`O(m + 事件处理)` - 每个事件对应一次 `set::insert` 或 `set::erase`，复杂度为 `O(log N)`。 - 每个区间产生 2 个事件，总事件数为 `2N`。 - 总复杂度为 **`O((N + m) log N) ≈ O(N log N)`**。 - **空间复杂度**：`O(N + m)`，主要是存储事件和离散化坐标。 --- ## 💡 进一步优化与建议 - **性能**：您可以考虑使用 `std::vector` 来存储事件（例如 `vector<pair<int, int>> events[2*N]`），然后按时间点排序统一处理，但这对于本题的复杂度影响不大。 - **数据结构选择**：`std::set` 在元素数较少时效率很高。如果需要极致性能，您可以尝试使用 `std::unordered_set`，但考虑到我们需要 `begin()` 来获取唯一元素，`set` 更清晰。 --- ######[AI写代码神器 | 1862点数解答 | 2026-07-14 20:38:11]