题意简述

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

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

关键观察

1. 如果所有子段的 MEX 都等于 (x)，那么每个子段必须：
   • 包含 (0,1,\dots,x-1) 中的所有数；
   • 不包含 (x)。
2. 如果存在一个合法的划分（(k>1)），那么取第一个子段之后的所有元素作为一个整体，这个整体也必须包含 (0..x-1) 且不包含 (x)，因此它的 MEX 也是 (x)。
3. 因此，只要存在合法划分，就一定能找到一个位置 (p)（(1\le p<n)），使得前缀 ([1,p]) 的 MEX 等于后缀 ([p+1,n]) 的 MEX。我们只需要输出这两个子段即可。

算法流程

1. 特判 MEX = 0
   如果整个数组没有 (0)，则任意划分都满足 MEX = 0。直接输出两段：([1,1]) 和 ([2,n])。

2. 一般情况

   • 预处理整个数组的计数 cnt2，并求出整个数组的 MEX，记为 mex2。
   • 从左到右扫描数组，维护：
     • 前缀计数 cnt1
     • 前缀的 MEX，记为 mex1
     • 后缀计数（动态减少）以及后缀的 MEX，记为 mex2
   • 每处理一个元素 (a[i])：
     • 更新 cnt1[a[i]]++，cnt2[a[i]]--
     • 如果 cnt2[a[i]] == 0 且 (a[i] < mex2)，则令 mex2 = a[i]
     • 调整 mex2：while (mex2 && !cnt2[mex2-1]) --mex2;
     • 调整 mex1：while (cnt1[mex1]) ++mex1;
     • 如果 mex1 == mex2，则找到了分割点：前缀为 ([1, i+1])，后缀为 ([i+2, n])（注意下标从 0 开始）。
   • 如果扫描结束仍未找到，输出 (-1)。

3. 输出
   按题目要求输出子段数量和左右边界。

正确性证明

• 充分性：若找到一个位置使前后缀 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，注意防止溢出。