F. MEX Queries - 题解

比赛与标签

比赛: Educational Codeforces Round 23 标签: binary search, data structures, trees, *2300 难度: *2300

喵喵的题目解读

主人你好呀~ 这道题看起来有点吓人，数字范围那么大，但是别怕，让咱来给你分析一下喵！

题目要求我们维护一个初始为空的整数集合，然后进行 n 次操作。操作有三种类型：

类型 1 (l, r): 把 [l, r] 区间里所有不在集合里的数都加进去。
类型 2 (l, r): 把 [l, r] 区间里所有在集合里的数都丢掉。
类型 3 (l, r): 对 [l, r] 区间里的数进行一次“反转”操作！在集合里的就丢掉，不在的就加进来，像一个开关一样，喵~

每次操作结束后，我们都要立刻计算并输出当前集合的 MEX。MEX 就是指最小的、没有出现在集合中的正整数。比如说，如果集合是 {2, 3, 5}，那么最小的没出现的正整数就是 1，所以 MEX 就是 1 啦！

猫娘的奇思妙想

这道题最棘手的地方就是 l 和 r 的范围可以达到 10^18！我们不可能开一个这么大的数组或者线段树来记录每个数的状态，内存会瞬间爆炸的喵！

关键突破口：离散化！

冷静下来想一想，虽然数字范围很大，但我们操作的次数 n 其实并不多（最多 10^5 次）。这意味着，真正能影响数字状态的“关键点”只有每次查询的端点 l 和 r。

我们可以发现一个规律：对于任意两个相邻的关键点 x 和 y，在 [x, y-1] 这个区间内的所有数字，它们的状态（在或不在集合里）永远是相同的！因为所有操作都是对整个 [l, r] 区间进行的，不会单独改变 [x, y-1] 中间某个数的状态。

这就给了我们一个超棒的思路：离散化！

我们收集所有查询的端点 l 和 r。为了正确表示区间 [l, r]，我们通常把 r+1 也作为一个关键点。
同时，因为我们要找的是最小正整数 MEX，所以 1 也是一个非常重要的关键点，必须加进去。
把所有这些关键点收集起来，排序并去重，得到一个坐标数组 coords。
这些坐标点就把整个 1 到 10^18 的数轴划分成了一系列“基本区间”，形如 [coords[i], coords[i+1]-1]。

线段树闪亮登场！

现在，我们不用去管 10^18 个数字了，只需要关心这 O(n) 个基本区间就够了！这不就是线段树最擅长解决的问题嘛？

我们可以建立一棵线段树，树的每个叶子节点 i 就代表第 i 个基本区间 [coords[i], coords[i+1]-1] 的状态。

节点状态:
- tree[node] = 0：表示该节点对应的所有基本区间都是“空的”（里面的数都不在集合里）。
- tree[node] = 1：表示该节点对应的所有基本区间都是“满的”（里面的数都在集合里）。
- tree[node] = -1：表示该节点对应的基本区间状态不一，有空的也有满的（混合状态）。
懒标记 (Lazy Propagation): 既然有区间修改，懒标记是必不可少的！
- lazy[node] = 0: 表示要把这个区间全部设为“空”。
- lazy[node] = 1: 表示要把这个区间全部设为“满”。
- lazy[node] = 2: 表示要把这个区间进行“反转”操作。
- lazy[node] = -1: 表示没有懒标记。
懒标记的下推也很有趣：
- 设置操作（0 或 1）会直接覆盖掉任何之前的标记。
- 反转操作（2）遇到设置操作时，会把设置操作反转（0 变 1，1 变 0）。
- 反转操作遇到另一个反转操作，两次反转就等于什么都没做，抵消掉了！

如何寻找MEX？

寻找MEX，就是寻找第一个状态为“空”的基本区间 [coords[i], coords[i+1]-1]。那么MEX的值就是这个区间的左端点 coords[i]。

我们可以在线段树上进行一次高效的“二分查找”来定位这个区间：

从根节点开始。
检查左子节点。如果左子节点代表的区间不是“全满”的（即 tree[left_child] != 1），说明第一个“空”的区间一定在左子树里，我们就往左走。
如果左子节点是“全满”的，说明左边所有区间都满了，那我们只能去右子树里寻找答案，于是往右走。
重复这个过程，直到到达一个叶子节点。这个叶子节点的索引 i 就是我们想要的，答案就是 coords[i] 啦！这个过程就像在树上寻宝一样，非常快，喵~

代码实现

cpp

// 完整的AC代码，添加详细注释解释关键逻辑
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <tuple>

using namespace std;

const int MAX_N = 100005;
const int MAX_COORDS = 2 * MAX_N + 5;

// 线段树节点
// state: 0 表示区间全空, 1 表示区间全满, -1 表示混合状态
int tree[4 * MAX_COORDS];
// lazy: 0 表示设置为全空, 1 表示设置为全满, 2 表示反转, -1 表示无操作
int lazy[4 * MAX_COORDS];

// 离散化后的坐标点
vector<long long> coords;

// 将懒标记应用到节点上
void apply_lazy(int node, int op) {
    if (op == 0 || op == 1) { // 设置操作 (0或1)
        tree[node] = op;
        lazy[node] = op;
    } else { // 反转操作 (op == 2)
        if (tree[node] != -1) { // 如果是纯色节点，直接反转状态
            tree[node] = 1 - tree[node];
        }
        // 更新懒标记
        if (lazy[node] == -1) { // 如果没有懒标记，就加上反转标记
            lazy[node] = 2;
        } else if (lazy[node] == 2) { // 如果已经有反转标记，两次反转等于没有，取消标记
            lazy[node] = -1;
        } else { // 如果是设置标记(0或1)，反转它
            lazy[node] = 1 - lazy[node];
        }
    }
}

// 下推懒标记到子节点
void push(int node, int start, int end) {
    if (lazy[node] == -1 || start == end) {
        return;
    }
    apply_lazy(2 * node, lazy[node]);
    apply_lazy(2 * node + 1, lazy[node]);
    lazy[node] = -1; // 清除当前节点的懒标记
}

// 从子节点合并信息到父节点
void merge(int node) {
    if (tree[2 * node] != -1 && tree[2 * node] == tree[2 * node + 1]) {
        tree[node] = tree[2 * node];
    } else {
        tree[node] = -1; // 子节点状态不一致，父节点为混合状态
    }
}

// 区间更新
void update_range(int node, int start, int end, int l, int r, int type) {
    if (start > end || start > r || end < l) {
        return;
    }
    if (l <= start && end <= r) {
        // 根据查询类型应用操作
        // type 1: add -> set to 1
        // type 2: remove -> set to 0
        // type 3: invert -> flip (2)
        apply_lazy(node, type == 3 ? 2 : (type == 1 ? 1 : 0));
        return;
    }

    push(node, start, end); // 下推懒标记
    int mid = start + (end - start) / 2;
    update_range(2 * node, start, mid, l, r, type);
    update_range(2 * node + 1, mid + 1, end, l, r, type);
    merge(node); // 更新父节点状态
}

// 单点查询（其实是查询某个基本区间的状态）
int query_point(int node, int start, int end, int idx) {
    if (start == end) {
        return tree[node];
    }
    push(node, start, end);
    int mid = start + (end - start) / 2;
    if (idx <= mid) {
        return query_point(2 * node, start, mid, idx);
    } else {
        return query_point(2 * node + 1, mid + 1, end, idx);
    }
}

// 构建线段树，初始时所有区间都是空的
void build(int node, int start, int end) {
    tree[node] = 0; // all absent
    lazy[node] = -1;
    if (start == end) return;
    int mid = start + (end - start) / 2;
    build(2 * node, start, mid);
    build(2 * node + 1, mid + 1, end);
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;

    vector<tuple<int, long long, long long>> queries(n);
    set<long long> coord_set;
    coord_set.insert(1); // MEX最小为1，所以1是必须的关键点
    for (int i = 0; i < n; ++i) {
        cin >> get<0>(queries[i]) >> get<1>(queries[i]) >> get<2>(queries[i]);
        coord_set.insert(get<1>(queries[i]));
        coord_set.insert(get<2>(queries[i]) + 1); // r+1作为区间的右开端点
    }

    // 将set中的坐标点存入vector，完成离散化
    coords.assign(coord_set.begin(), coord_set.end());
    
    int m = coords.size();
    if (m <= 1) { // 如果只有一个坐标点1，说明没有有效区间
        for (int i = 0; i < n; ++i) cout << 1 << "\n";
        return 0;
    }

    // 我们有 m-1 个基本区间
    int num_intervals = m - 1;
    build(1, 0, num_intervals - 1);

    for (const auto& q : queries) {
        int t;
        long long l, r;
        tie(t, l, r) = q;

        // 找到 l 和 r+1 在离散化坐标中的位置
        auto it_l = lower_bound(coords.begin(), coords.end(), l);
        auto it_r = lower_bound(coords.begin(), coords.end(), r + 1);
        int l_idx = distance(coords.begin(), it_l);
        int r_idx = distance(coords.begin(), it_r);

        // 更新 [l_idx, r_idx-1] 这个范围的基本区间
        if (l_idx < r_idx) {
            update_range(1, 0, num_intervals - 1, l_idx, r_idx - 1, t);
        }

        // 寻找MEX
        // 首先检查第一个基本区间 [1, ...] 是否为空
        if (query_point(1, 0, num_intervals - 1, 0) == 0) {
            cout << 1 << "\n";
        } else {
            // 在线段树上二分查找第一个状态为0的叶子
            int mex_idx;
            if (tree[1] == 1) { // 如果整棵树都满了
                mex_idx = num_intervals;
            } else {
                int node = 1;
                int start = 0, end = num_intervals - 1;
                while (start < end) {
                    push(node, start, end);
                    int mid = start + (end - start) / 2;
                    if (tree[2 * node] != 1) { // 左子树不全为1，答案在左边
                        node = 2 * node;
                        end = mid;
                    } else { // 左子树全为1，答案在右边
                        node = 2 * node + 1;
                        start = mid + 1;
                    }
                }
                mex_idx = start;
            }
            cout << coords[mex_idx] << "\n";
        }
    }

    return 0;
}

复杂度分析

时间复杂度: O(N log N) 的说。这里 N 是查询的数量。我们有 O(N) 个坐标点，离散化排序需要 O(N log N)。对于每次查询，我们需要在线段树上进行更新和查找MEX，线段树的大小是 O(N)，所以每次操作的复杂度是 O(log N)。总的时间复杂度就是 O(N log N) 啦！
空间复杂度: O(N) 的说。我们需要存储 O(N) 个坐标点，以及一个大小为 O(N) 的线段树（包括懒标记数组）。所以空间复杂度是线性的，非常优秀喵~

猫娘的小课堂

这道题真是一道非常经典的“离散化 + 线段树”组合题，做完之后是不是感觉功力大增了呢？

核心思想: 离散化是解决“坐标范围巨大但操作次数有限”问题的神技！它能把一个看似无法处理的问题，转化为一个我们熟悉的、可以在 O(N) 规模上解决的问题。
线段树技巧:
1. 懒标记设计: 这道题的懒标记设计很考验思维。特别是“反转”操作，要仔细思考它和“设置”操作相遇时会发生什么。记住：设置的优先级更高，会覆盖一切；而两个反转会相互抵消。
2. 在树上二分: 寻找MEX的过程，本质上就是在线段树上进行二分查找。利用树的结构，我们可以快速地跳过那些已经被完全占用的区间，直奔第一个有空位的目标，效率极高！
注意事项:
- 离散化时，对于区间 [l, r]，我们通常要加入 l 和 r+1 作为关键点，这样才能用左闭右开的方式精确地表示出所有区间。
- 别忘了把 1 也加入坐标集合，因为MEX最小就是1，我们要保证第一个基本区间是从1开始的，不然就找不到正确答案啦！

希望这篇题解能帮到你哦~ 只要掌握了离散化和线段树这两个强大的工具，很多难题都会变得清晰起来的！加油，你一定可以的，喵~

F. MEX Queries - 题解 ​

比赛与标签 ​

喵喵的题目解读 ​

猫娘的奇思妙想 ​

关键突破口：离散化！ ​

线段树闪亮登场！ ​

如何寻找MEX？ ​

代码实现 ​

复杂度分析 ​

猫娘的小课堂 ​