MEX区间构造问题#

MEX 描述的是某个区间内 最小的未出现的非负整数 。从定义出发，如果一个区间的 MEX 等于 $x$ ，那么这个区间必须 完整包含 所有整数 $0, 1, 2, \dots, x-1$ ，否则更小的缺失值会优先成为 MEX；与此同时，整数 $x$ 不能出现在该区间中 ，否则 MEX 会被进一步推大。这两个条件，是解决所有 MEX 问题的核心约束。

进一步地，从 区间长度的角度 我们可以发现一个重要的结论：对于一个长度为 $n$ 的区间，由于其中最多只能包含 $n$ 个不同的数，因此不可能同时覆盖 $0 \sim n$ 这 $n+1$ 个整数，也就是说 MEX 的取值一定 不超过 n 。这一结论说明 MEX 的取值范围与区间长度直接关联，这为后续的枚举、构造以及状态设计提供了重要的 上界控制 。

MAC中的信息#

题目链接

Problem Statement#

给定一个包含 $n$ 个非负整数的数组 $a$ 。

你需要将该数组分割成 $k \geq 2$ 个连续的子数组，使得每个子数组的 MEX 值都相等。

如果存在这样的分割方案，请输出一种；否则，输出 $-1$ 。

Constraints#

$1 \leq t \leq 10^4$
$2 \leq n \leq 10^5$
$0 \leq a_i < n$
所有测试用例中 $n$ 的总和不超过 $2 \times 10^5$

Input#

输入包含多个测试用例：

第一行包含一个整数 $t$ ，表示测试用例的数量。
对于每个测试用例：
- 第一行包含一个整数 $n$ 。
- 第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$ 。

$t$

$n_1$

$a_{11} \quad a_{12} \quad \ldots \quad a_{1n_1}$

$\ldots$

$n_t$

$a_{t1} \quad a_{t2} \quad \ldots \quad a_{tn_t}$

Output#

对于每个测试用例：

如果不存在满足条件的分割方案，输出 -1 。
否则，第一行输出一个整数 $k$ ，表示分割的子数组数量。
接下来 $k$ 行，每行包含两个整数 $l_i, r_i$ ，表示第 $i$ 个子数组的左端点和右端点。
必须满足 $l_1 = 1, r_k = n$ ，且对于所有 $1 \leq i < k$ ，有 $l_{i+1} = r_i + 1$ 。

Sample Input#

5
2
0 0
5
0 1 2 3 4
8
0 1 7 1 0 1 0 3
3
1 1 1
10
0 5 0 3 0 1 3 2 2 0

Sample Output#

题目要点解析#

MEX区间查询问题#

我们暂时不讲解复杂的区间查询问题，而是思考这么一个基础任务：如何维护一个集合的 MEX，并且支持集合元素的 动态插入与删除 。在这种场景下，集合会随着操作实时发生变化，我们的目标是在每次插入或删除元素之后，能够 快速得到当前集合的 MEX 值 。

一种常见且直观的做法是维护当前集合中所有未出现的数。具体而言，可以使用一个 set 来存储这些数字。初始时，将 $0 \sim n$ 所有可能的数加入 set ，表示这些数最开始都没有出现在集合中。当向集合中加入一个数 $x$ 时，如果它原本在 set 中，则将其删除；当从集合中删除一个数 $x$ 时，如果该数的计数降到 $0$ ，则重新将它加入 set 。在实际实现中，通常需要配合一个 计数数组 $cnt[x]$ 来记录每个数字在集合中的出现次数，只有当某个数字的计数从 $0$ 变为 $1$ ，或从 $1$ 变为 $0$ 时，才对 set 进行相应的更新，以确保维护过程的正确性和一致性。

由于 set 中始终保存的是当前集合中未出现的数字，因此它的 最小元素 自然就是当前集合的 MEX。考虑到 set 的插入、删除以及获取最小值操作的时间复杂度均为 $O(\log n)$ ，如果集合总共经历 $q$ 次操作，那么维护整个过程的 总体时间复杂度为 $O(q \log n)$ ，可以高效地动态维护集合的 MEX。

任意区间的离线查询（一）#

在讲解完上面这个基础问题后，我们可以正式引入 MEX 区间查询的基础模型：对于一个静态数组，查询所有区间的 MEX 值。若采用暴力做法，我们可以枚举每一个左端点 $L$ ，然后让右端点 $R$ 从左到右移动。在这个过程中可以发现，随着 $R$ 的增加，区间的 MEX 是 单调不减 的，因此对于每个 $L$ ，可以在 $O(n)$ 的时间内求出所有对应的区间 MEX。对所有 $L$ 执行这一过程，总时间复杂度为 $O(n^2)$ ，本质上等价于枚举所有子数组。

上述做法的问题在于，不同左端点之间的信息是完全割裂的，导致出现大量的重复计算。实际上，当我们已经处理完 $L=i$ 的所有区间后，这些信息在转移到 $L=i+1$ 时并不会全部失效。将左端点从 $i$ 移动到 $i+1$ ，本质上只是从区间中删除了一个元素 $a[i]$ ，因此我们只需要分析这个删除的元素对已有 MEX 结果造成什么样的影响即可，而不需要重新计算整个区间。

为此，我们可以预处理一个 $next$ 数组，用来记录每个位置的数在右侧 第一次再次出现 的位置。当左端点从 $i$ 移动到 $i+1$ 时，对于右端点 $R \geq next[i]$ 的区间，由于区间内仍然包含一个 $a[i]$ ，因此 MEX 不会发生变化；只有当 $R < next[i]$ 时，区间内部才会真正失去了这个数，从而影响这个区间的 MEX，并且只有当原本的 MEX 大于 $a[i]$ 时，删除该数才会改变结果。结合 MEX 随 $R$ 单调不减的性质，可以在当前 MEX 数组中二分找到第一个大于 $a[i]$ 的位置 $k$ ，并将所有左端点 $L=i$ 、右端点 $R \in [k, next[i]-1]$ 的区间 MEX 统一修改为 $a[i]$ ，从而完成从 $L=i$ 到 $L=i+1$ 的高效转移。

因此，我们定义一个数组 $mex$ ，其中 $mex[i]$ 表示区间 $[0, i]$ 的 MEX 值，并使用线段树对该数组进行维护。在完成初始状态的构建后，接下来考虑如何将左端点从 $L=i$ 转移到 $L=i+1$ 。根据前面的分析，这一过程只会影响一段连续区间的取值，因此我们可以在线段树上进行二分找到第一个满足 $mex[k] > a[i]$ 的位置 $k$ ，并对区间 $[k, next[i]-1]$ 进行 区间赋值更新 ，将其统一修改为 $a[i]$ 。通过这样的区间修改，即可在对数时间内完成一次转移，总体时间复杂度为 $O(n \log n)$ ，优于一般的暴力解法。

任意区间的离线查询（二）#

我们换一种思路来处理上面这个 MEX 区间查询问题。对于一个区间 $[L, R]$ ，其 MEX 本质上是 寻找一个最小的非负整数 x，使得 x 在该区间内从未出现过 。据此，我们可以固定右端点 $R$ ，通过左端点 $L$ 进行查询判断。为辅助判断，我们引入一个 $last$ 数组，其中 $last[x]$ 表示数字 $x$ 最近一次出现的位置。这样，区间的 MEX 查询就转化为寻找最小的 $x$ ，使得 $last[x] < L$ 。然而，由于原数组不是有序的， $last$ 数组也不具备有序性，如果对每个查询都要遍历整个 $last$ 数组，就会导致时间复杂度达到 $O(n^2)$ ，显然效率不高，因此需要进一步优化。

我们考虑使用权值线段树来维护这个 $last$ 数组。线段树的下标对应 数值 x（即值域），每个叶子节点存储该数字的 $last[x]$ ，表示它最近一次出现的位置；由于我们要查找小于 L 的 last 值，每个父节点维护其区间内的最小 last 值 。这样，当我们查询某个左端点 $L$ 时，只需从根节点开始搜索：如果当前节点的 $last_{min} \geq L$ ，说明该节点管理的所有数字都在区间 $[L, R]$ 内出现过，可以直接跳过；否则优先递归访问左子树，确保能够找到 最小的 x ，使得 $last[x] < L$ 。

我们考虑按 $R$ 的大小来处理查询，并利用两数之和的思想，枚举右端点 $R$ ，同时维护左端点 $L$ 。当右端点向右移动，遇到新的数字 $a[R]$ 时，只需将对应叶子节点的 $last[a[R]]$ 更新为 $R$ ，并向上更新父节点的最小 $last$ 值。通过这种方式，每次右端点移动时的更新，以及对左端点 $L$ 的查询，都可以在 $O(\log n)$ 时间内完成，从而大幅提升整体查询效率。