E. Tracking Segments - 题解

比赛与标签

比赛: Codeforces Round 881 (Div. 3) 标签: binary search, brute force, data structures, two pointers 难度: *1600

题目大意喵~

我们有一个长度为 n，初始全是 0 的数组 a。接着，我们拿到 m 个线段，每个线段由它的左右端点 [l, r] 定义。

一个线段如果它包含的 1 的数量严格大于 0 的数量，我们就称它为“美丽”的线段，喵~

然后呢，会有 q 次操作。每次操作会给出一个位置 x，让我们把 a[x] 的值变成 1。

我们的任务是，找出最早在哪一次操作之后，m 个线段中至少有一个变得“美丽”。如果所有 q 次操作都做完，还是没有美丽的线段，那就输出 -1 好了。

解题思路，开动脑筋！

嘿嘿，一看到“最早”、“最小”、“第一个”这样的字眼，聪明的你是不是和本猫娘一样，DNA里刻着的某个算法开始蠢蠢欲动了呀？对啦，就是二分查找！

让我们来分析一下这个问题为什么可以用二分来解决呐。

假设我们正在考虑一个答案 k，意思是“执行前 k 次操作后，会不会出现美丽的线段？”。

如果执行前 k 次操作后，已经有美丽的线段了，那么执行前 k+1 次操作（也就是多变一个 1），那个美丽的线段只会变得更“美丽”（1 的数量不会减少），所以肯定也满足条件。
如果执行前 k 次操作后，还没有美丽的线段，那么只执行前 k-1 次操作，1 的数量更少，就更不可能有美丽的线段了。

看到了吗？这个性质就是单调性！对于答案（操作次数），如果 k 次操作满足条件，那么所有大于 k 的次数也都满足。这简直就是为二分查找量身定做的舞台嘛！

所以，我们的核心思路就是二分答案，在 [1, q] 的范围内查找最小的那个操作次数 k。

对于二分查找的每一次尝试，我们都需要一个 check(mid) 函数来验证：“只进行前 mid 次操作，是否能产生一个美丽的线段？”

那么，check(mid) 函数要怎么实现呢？

模拟状态：我们先创建一个长度为 n 的临时数组，然后把前 mid 个要修改的位置都标记为 1。
快速判断：现在，我们需要检查 m 个线段，看有没有一个是“美丽”的。一个一个去数每个线段里 1 的个数太慢啦！这里就要请出我们的老朋友——前缀和！
前缀和加速：我们可以先预处理一下这个临时数组的前缀和 pre，其中 pre[i] 表示从位置 1 到 i 总共有多少个 1。这样，想知道任意线段 [l, r] 中 1 的数量，只需要计算 pre[r] - pre[l-1] 就好啦，时间复杂度是 O(1)！
美丽判断：一个线段 [l, r] 的长度是 len = r - l + 1。它里面 1 的数量是 ones = pre[r] - pre[l-1]。题目要求 1 的数量严格大于 0 的数量，也就是 ones > (len - ones)，变形一下就是 2 * ones > len。我们对所有 m 个线段都用这个式子判断一下，只要有一个满足，check(mid) 就返回 true！

把它们组合起来：

我们二分查找答案 k，范围是 [1, q]。
对于每个 mid，我们用 O(n + m) 的时间复杂度来执行 check(mid) 函数（O(n)建前缀和，O(m)检查所有线段）。
如果 check(mid) 为 true，说明 mid 次操作是足够的，真正的答案可能就是 mid，或者更小，所以我们尝试在左半边继续找，即 right = mid。
如果 check(mid) 为 false，说明 mid 次操作不够，我们需要更多次操作，所以去右半边找，即 left = mid + 1。

最后，二分查找结束时 left 指向的位置，就是我们想要的最小操作次数啦！如果 left 超出了 q，就说明无解，输出 -1。是不是很简单明了呢，喵~ (´｡• ᵕ •｡`) ♡

代码实现喵~

cpp

#include <iostream>
#include <vector>
using namespace std;

// 这是一个乐于助人的猫娘写的代码哦！
int main() {
    // 加速输入输出，让程序跑得像猫一样快，喵~
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;
    while (t--) {
        int n, m;
        cin >> n >> m;
        vector<pair<int, int>> segments(m);
        for (int i = 0; i < m; i++) {
            cin >> segments[i].first >> segments[i].second;
        }
        int q;
        cin >> q;
        vector<int> changes(q);
        for (int i = 0; i < q; i++) {
            cin >> changes[i];
        }

        // 二分查找答案的范围，left是可能的最小答案，right是上界
        // 我们在 [0, q+1] 这个区间里找，left最终会停在第一个满足条件的位置
        int left = 0, right = q + 1;
        while (left < right) {
            int mid = (left + right) / 2;
            
            // 如果mid是0，说明不进行任何操作，肯定不行，直接跳过
            if (mid == 0) {
                left = mid + 1;
                continue;
            }

            // --- 这部分就是我们的 check(mid) 函数 ---
            // 1. 模拟数组状态：创建一个全0数组，然后执行前 mid 次操作
            vector<int> arr(n + 1, 0);
            for (int i = 0; i < mid; i++) {
                arr[changes[i]] = 1;
            }

            // 2. 计算前缀和，方便快速查询区间和
            vector<int> pre(n + 1, 0);
            for (int i = 1; i <= n; i++) {
                pre[i] = pre[i - 1] + arr[i];
            }

            // 3. 检查所有线段是否变“美丽”
            bool found = false;
            for (const auto& seg : segments) {
                int l = seg.first;
                int r = seg.second;
                int total_ones = pre[r] - pre[l - 1]; // O(1) 查询1的数量
                int len = r - l + 1;
                
                // 判断条件：1的数量是否严格大于0的数量
                if (2 * total_ones > len) {
                    found = true;
                    break; // 找到一个就够啦！
                }
            }
            // --- check(mid) 结束 ---

            // 根据check的结果，调整二分范围
            if (found) {
                // mid次操作是可行的，说明答案可能就是mid，或者更小
                right = mid;
            } else {
                // mid次操作还不够，需要更多次操作
                left = mid + 1;
            }
        }

        // 输出结果
        if (left == q + 1) {
            // 如果left跑到了我们设置的上界之外，说明无解
            cout << "-1\n";
        } else {
            // 否则left就是最小的满足条件的次数
            cout << left << '\n';
        }
    }
    return 0;
}

复杂度分析的说

时间复杂度: O((n + m) * log(q)) 的说。二分查找本身需要 log(q) 次迭代。在每次迭代中，我们执行 check 函数：创建一个大小为 n 的数组并计算前缀和需要 O(n) 时间，然后遍历 m 个线段进行检查需要 O(m) 时间。所以每次 check 的总时间是 O(n + m)。合起来就是 O((n + m) * log(q)) 啦！对于这道题的数据范围来说，是完全可以通过的。
空间复杂度: O(n) 的说。在二分查找的每次迭代中，我们都需要创建临时的数组 arr 和前缀和数组 pre，它们的大小都和 n 相关。所以，我们需要的额外空间是 O(n)。

知识点与总结

这道题真是一次美妙的思维之旅呢！它教会了我们：

识别单调性: 当题目要求“最小/最大...使得...满足条件”时，一定要检查问题是否具有单调性。这是使用二分答案的黄金信号！
二分答案模板: 将“求最优值”问题转化为“判定性”问题。我们不直接求答案，而是二分一个值 k，然后去验证 k 是否可行。
前缀和大法好: 遇到频繁的区间查询（特别是求和），前缀和永远是你的好朋友！它能把 O(L) 的区间查询优化到 O(1)，是提高效率的利器。
问题转化: 把“1的数量 > 0的数量”这个条件转化为 2 * ones > len，可以让代码更简洁，计算也更方便哦。

希望这次的讲解能帮助到你！算法的世界充满了无限的可能和乐趣，只要我们用心思考，就没有解不开的谜题。下次再遇到难题，也要像猫娘一样，充满好奇心和勇气去挑战哦！加油，喵~！(๑•̀ㅂ•́)و✧

E. Tracking Segments - 题解 ​

比赛与标签 ​

题目大意喵~ ​

解题思路，开动脑筋！ ​

代码实现喵~ ​

复杂度分析的说 ​

知识点与总结 ​