【2026】简单 mex 问题的一些小巧思及解题方法

· · 算法·理论

事实上，许多 \operatorname{mex} 问题都有一些共性的思考方向（兼思维树分支）。让我们首先明确 非负整数序列 \operatorname{mex} 的定义：

:::info[Defination 1.]{open} 一般地，我们定义非负整数 / 自然数序列的 \operatorname{mex} 为满足如下条件的自然数 x：

简而言之就是序列中最小的，没有出现过的自然数。

\textbf {Thoughts From Def.}

下述所有区间均与 \mathbb{N} 取交。

不难发现这样的定义给了我们一些启发。首先可以注意到的是两个性质：

:::success[Property 1.]{open}

:::success[Property 2.]{open}

:::success[Property 3.]{open}

我们考虑按位构造这样一个长为 n 的序列，即序列按 0, 1, 2, ...， n-1 依次填入序列，此时该序列 \operatorname{mex} 是 n。由于现在更改序列任意一个数都不会让 \operatorname{mex} 更大，故这样构造对于得到上限是最优的。 :::

下面我们通过一道例题来深入探究：P14936 「FAOI-R10」别样的 mex 大战 。

:::info[Solution & Thinking]{open} 对于这种添加数来满足条件的问题，我们可以有两种可鉴的思路：整体考虑，亦或是考虑加一项对前面的贡献。

整体考虑的思想难以连接起 \operatorname{mex} 和 \oplus 的联系，于是我们考虑正在加入第 (n + k) 项，对前 (n + k - 1) 项的影响：

此时注意到需要满足 \operatorname{mex}(a_{1..n+k-1}) \neq (\oplus_{i=1}^{n+k-1} a_i)，才能对下一项也可以如此构造。

a_{n+k} = \operatorname{mex}(a_{1..n+k-1}) \oplus (\oplus_{i=1}^{n+k-1} a_i) = \operatorname{mex}(a_{1..n+k-1})

在之后的构造中，不难发现总存在一个 \le 10^3 次的时刻使得 a_{n+k} \neq \operatorname{mex}(a_{1..n+k-1})，这一命题的证明过程略去。 :::

这道例题颇有 Ad-hoc 的韵味。场上也许我们有时候没有时间思考详细的证明过程，但最后的结论是很好想到的。

下面我们再来一道比较难的 RMQ 例题：P4137 Rmq Problem / mex

:::info[Solution & Thinking]{open} 由前述的 “性质 2” 可知 [l, r] 的 \operatorname{mex} 等价于该区间 \operatorname{mex} 最后一次出现的位置在 [l, r] 中不存在，且 [0, \operatorname{mex}) 中的整数最后一次出现的位置必然皆在 [l, r] 中。

于是我们以下标 - 元素最后出现位置建立一个二维平面坐标系，设元素 m 的坐标为 P_m(u, v)，则对于 [l, r] 区间内的 \operatorname{mex}，即为在直线 x = r 的点上寻找最小的元素 m 使得 v \lt l（元素的最后出现位置在 l 之前）。

既然涉及到了二维平面的数据处理，可以考虑遍历下标，用主席树维护最后出现位置，时间复杂度 O(n\log n)。 :::

不难发现上述的三个性质已经足够我们得心应手地应对一部分相关简单题目，但这还远远不够。由于知识点复杂，连接性较强的题目层出不穷，于是或许我们需要在深入些。

\textbf {Extend for faraway.}

根据其与数据结构等地连接性，下面我们再依据这些算法和结构给出下述两个性质：

:::success[Property 4.]{open}

:::success[Property 5.]{open} 一般地，对于长为 n 的非负整数序列 a，有下式恒成立：

\operatorname{mex}(a) + \min(a) = \max\{\operatorname{mex}(a), \min(a)\}

:::info[Proof 5.] 由于涉及到了三种运算，考虑分类讨论：

综上，原式在性质约束下恒成立。 :::

:::success[Property 6.]{open} 一般地，对于长为 n 的非负整数序列 a，设 l \le r \in (1, n)，有下式恒成立：

\operatorname{mex}(a_{l..{r+1}}) \ge \operatorname{mex}(a_{l..r})\\ \operatorname{mex}(a_{{l-1}..r}) \ge \operatorname{mex}(a_{l..r}) \end{cases}

简单来说，当连续子区间 [l, r] 拓展一个元素时，子序列的 \operatorname{mex} 单调不降。注意由于拓展元素会更改子区间长度，所以要注意和“性质 4”的区别。 :::info[Proof 6.] 我们不妨以方程组的第一个不等式为例，分类讨论所有可能情况：

综上，\operatorname{mex}(a_{l..{r+1}}) \ge \operatorname{mex}(a_{l..r}) 恒成立。 :::

下面我们依照上述若干个性质给出两道例题：（SGT 分治）P5631 最小mex生成树，（二维偏序 / 矩形面积并）P10169 [DTCPC 2024] mex,min,max。

接下来我们尝试考虑贪心。将边权从大到小排序，再类似 Kruskal 算法尝试构造生成树。这样的算法正确性看似确实无疑，但这里有一组构造出来的 hack 数据：

Input:
3 3
1 2 0
1 3 0
2 3 1
Answer: 1
Output: 2

即该无向图如下图所示：

按照贪心的算法的逻辑，它会连接 “2 \rightarrow 3, 1 \rightarrow 2” 或 “2 \rightarrow 3, 1 \rightarrow 3”，此时获得了错误的答案 2。所以贪心算法看来是行不通的。

由于“性质 2”的存在，不妨让我们思考枚举可能的最终答案，把权值与遍历到的可能答案相等的边全部删去，考虑剩下的边是否可以构造出一颗任意生成树。又考虑到“性质 3”，可以得到答案至多只有 w - 0 + 1 = w + 1 种可能。由此我们不难会想到一种 O(nw \log n) 的暴力做法。

考虑优化。既然我们需要删边求生成树，考虑到任意两个不同遍历到的答案所构造的生成树中有大量的边重复，也就可以考虑在删边上着力优化，即让处理这些重复边所耗费的效率尽可能小。由此我们可以发现既然权值遍历具有先后顺序，那么这些边是不是也可以顺应遍历的顺序先后出现呢？

由此，我们可以发现每条边若权值是 x，可以将这条边等效转化成在遍历过程中“在遍历 [0, x) \cup (x, w_{\max}] 区间的答案中可以出现的边”（其中 w_{\max} 表示权值最大的边的权值），并且恰好求生成树所用的并查集也支持撤销，故我们考虑使用线段树分治维护这些时刻的边，此时这个问题就迎刃而解了，做法与线段树分治模板相似，时间复杂度 O(w \log w \log n)。

本道题的思维推导树如下（由 DeepSeek R1 辅助生成）：

本道题的伪代码如下（由 DeepSeek R1 辅助生成）：

Algorithm Main:
    Input: n, m, edges[]
    Output: minimal mex value

    // 找到最大边权 W
    W ← 0
    for each edge in edges do
        W ← max(W, edge.w)

    // 答案范围是 [0, W+1]
    maxAns ← W + 1

    // 构建线段树分治结构
    segmentTree ← SegmentTree(0, maxAns)

    // 将每条边分配到对应的时间区间
    for each edge (u, v, w) in edges do
        // 边在 ans ≠ w 的时刻都存在
        // 即区间 [0, w) ∪ (w, maxAns]
        if w > 0 then
            segmentTree.insert(0, w-1, edge)
        if w < maxAns then
            segmentTree.insert(w+1, maxAns, edge)

    // 初始化可撤销并查集
    dsu ← DSU(n)

    // 深度优先遍历线段树
    result ← DFS(segmentTree.root, dsu)

    return result

Function DFS(node, dsu):
    // 记录当前状态快照
    snapshot ← dsu.saveState()

    // 加入当前节点管理的边
    for each edge in node.edges do
        dsu.unite(edge.u, edge.v)

    // 检查叶子节点（即单个ans值）
    if node.isLeaf then
        ansValue ← node.rangeStart
        if dsu.isConnected() then
            // 能够形成生成树，记录这个ans是可行的
            result ← ansValue
        else
            result ← INF
    else
        // 递归处理子节点
        leftResult ← DFS(node.left, dsu)
        rightResult ← DFS(node.right, dsu)
        result ← min(leftResult, rightResult)

    // 回溯：撤销当前节点的操作
    dsu.rollback(snapshot)

    return result

:::

::::info[Solution & Thinking]{open} 由“性质 5”可得

\operatorname{mex}(a_{l..r}) + \min(a_{l..r}) = \max\{\operatorname{mex}(a_{l..r}), \min(a_{l..r})\}

于是原式转化成求

\max\{\operatorname{mex}(a_{l..r}), \min(a_{l..r})\} + k \ge \max(a_{l..r})

的区间个数。下面略去 (a_{l..r}) 的书写，我们分类讨论上式：

\max - \min \le k

这是好求解的，上式的含义即为子区间极差不超过常数 k。由于涉及区间计数问题，我们首要的做法应是尝试考虑偏序。

设 \operatorname{solve}(l, r) 函数来求解 [l, r] 区间内的总贡献，那么按照偏序，枚举断点 mid，这里 mid 取 \lfloor{\frac{l + r}{2}}\rfloor。递归求解 \operatorname{solve}(l, mid) 以及 \operatorname{solve}(mid+1, r)，那么我们剩下要考虑的即为跨过断点区间的贡献，下面我们思考这个问题。

设产生贡献的区间为 [p, q]，则有 p \le q, p \in [l, mid], q \in (mid, r]。若我们固定 p，让 q 从 mid+1 开始不断增大，又因为 \max 随此过程单调不降，\min 随此过程单调不增，那么可以得出此子序列的极差单调不降，由此推得发生贡献的 q 在一段连续区间内。二分出最大的 q，直接统计即可得到这部分贡献。这里有一个小优化，就是在上次二分到的 q_{lst} 往后的范围里二分。这样可以做到 O(n \log n) 的时间复杂度。

:::warning[注意题设条件] 由于 \min \ge \operatorname{mex}，到么可以推得 \operatorname{mex} = 0，所以我们二分到的区间 [p, q] 中必须不包含 0。 :::

\operatorname{mex} \ge \max - k

或者

\max - \operatorname{mex} \ge k

要求不等式区间统计的方法，主要是为整体单调性和单个运算单调性，在这里首要分析整体单调性。类似于情况 1 的讨论，设 \operatorname{solve'}(l, r) 函数来求解 [l, r] 区间内的总贡献，那么按照偏序，枚举断点 mid，这里 mid 取 \lfloor{\frac{l + r}{2}}\rfloor。递归求解 \operatorname{solve'}(l, mid) 以及 \operatorname{solve'}(mid+1, r)，那么我们剩下要考虑的即为跨过断点区间的贡献，下面我们再来思考这个问题。

设产生贡献的区间为 [p, q]，则有 p \le q, p \in [l, mid], q \in (mid, r]。若我们固定 p，让 q 从 mid+1 开始不断增大，又因为 \max 随此过程单调不降，\operatorname{mex} 随此过程单调不降，那么可以得出此子序列的 \max - \operatorname{mex} 单调性不确定，故我们无法考虑偏序（整体单调性）来解决这个问题。

接下来我们考虑单一运算单调性，即 \max, \operatorname{mex} 的运算单调性。若固定 \max 所产生的可贡献区间太繁杂，优化性质不明显，处理过程时间复杂度相当高（思考：为什么？），在这里我们不考虑。

所以留给我们的只有固定 \operatorname{mex} 了。考虑一个极短的 \operatorname{mex} 段 [l_0, r_0] 以及极长 \operatorname{mex} 段 [l_1, r_1] 满足 [l_0, r_0] \subseteq [l_1, r_1]。此时我们便有了固定 mex 的思考方向啦！只要找出最长的区间 [l', r'] 满足 [l_0, r_0] \subseteq [l', r'], [l', r'] \subseteq [l_1, r_1] 且 \max(a_{l'..r'}) - \operatorname{mex}(a_{l'..r'}) \le k，由于“性质 6”，则以左端点在极短段左端点到 l'、右端点在 r' 到极短段右端点的区间均符合要求。由于直接计算可能比较麻烦，我们考虑将符合条件的区间转化成平面坐标 (l, r), 则符合条件的区间个数就是这些点最小覆盖矩形的面积，这部分用扫描线或离散化做一部分矩形面积并就可以求得答案。 :::warning[注意题设条件] 由于 \operatorname{mex} \gt \min = 0，所以符合条件的区间内应包含至少一个零。 :::

综上，该问题的解决时间复杂度为 O(n \log n)。

本道题的思维推导树如下（由 DeepSeek R1 辅助生成）： ::::

至上述这六个性质已经足够我们完成大部分 \operatorname{mex} 题，或者某些题的 \operatorname{mex} 思考部分。