题意简述

给定一个长度为 n 的数组 a，你需要将它划分为 k>1 个非空的连续子段，使得每个子段的 MEX 都等于同一个整数。输出任意一种划分方案，或报告无解。

MEX：最小的未在子段中出现的非负整数。 例如：[0,1,7]的 MEX = 2，因为 0,1 都存在，2 不存在。 关键观察

如果所有子段的 MEX 都等于 $x$，那么每个子段必须： 包含$0,1,\dots,x-1$ 中的所有数； 不包含$x$。

如果存在一个合法的划分（k>1），那么取第一个子段之后的所有元素作为一个整体，这个整体也必须包含 0..x-1 且不包含 x，因此它的 MEX 也是 x。

因此，只要存在合法划分，就一定能找到一个位置 p（$1\le p<n$），使得前缀 [1,p] 的 MEX 等于后缀 [p+1,n] 的 MEX。我们只需要输出这两个子段即可。

正确性证明

充分性：若找到一个位置使前后缀 MEX 相等，则这两个子段已经满足条件。

必要性：假设存在一个合法划分 $S_1, S_2, \dots, S_k$（$k\ge 2$），且每个子段的 MEX $= x$。 令$p$ 为第一个子段的右端点，则 $S_1 = [1,p]$ 的 MEX $= x$。 考虑剩余部分$T = [p+1, n]$，它包含了子段 $S_2, \dots, S_k$。由于每个 $S_i$（$i\ge 2$）都包含 $0..x-1$ 且不包含 $x$，所以 $T$ 同样包含 $0..x-1$ 且不包含 $x$，因此 $T$ 的 MEX 也等于 $x$。 所以前缀$[1,p]$ 和后缀 $[p+1,n]$ 的 MEX 相等。 因此算法必然能检测到这样的分割点（不一定恰好是$p$，但至少会找到一个）。

复杂度分析

每个测试用例只需一次扫描，时间复杂度 O(n)。 使用数组计数，空间复杂度 O(n)。 所有测试用例的 n 总和不超过 10^5，因此总复杂度 $O(\sum n)$ 。

参考代码（标程）

/* Includes */
#include <bits/stdc++.h>

/* Using libraries */
using namespace std;

/* Defines */
#define fast ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define vc vector
#define pii pair <int, int>
#define int long long

void solve () {
    int n;
    cin >> n;
    vc <int> a(n);
    vc <int> cnt1(n + 1), cnt2(n + 1);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
        cnt2[a[i]]++;
    }
    int mex1 = 0, mex2 = 0;
    while (cnt2[mex2])
        ++mex2;
    for (int i = 0; i < n; ++i) {
        cnt1[a[i]]++;
        if (--cnt2[a[i]] == 0 && mex2 > a[i]) {
            mex2 = a[i];
        }
        while (mex2 && !cnt2[mex2 - 1])
            --mex2;
        while (cnt1[mex1])
            ++mex1;
        if (mex1 == mex2) {
            cout << "2\n";
            cout << 1 << " " << i + 1 << "\n";
            cout << i + 2 << " " << n << "\n";
            return;
        }
    }
    cout << "-1\n";
}

signed main() {
    fast;
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

注意事项

当整个数组的 MEX = 0 时，直接输出两段（任何划分均可），代码中已处理。 输出时注意子段边界必须合法（$l_i\le r_i$，且连续覆盖整个数组）。 使用 long long 并非必要，但题解中使用了#define int long long，注意防止溢出。